Algorithms that convert recursive functions to iterative form & vice versa

This is an example of how to convert an algorithm in recursive form

into iterative form:

addElementRecursive --> addElementIterative

and

showTreeRecursive --> showTreeIterative.

public class Tree<Element extends Comparable><Element>>{

private Node root;

public Tree(Element element){

root = new Node(element);

}

public void addElementRecursive(Element element ){

addElementRecursive(element, root);

}

protected void addElementRecursive(Element element, Node node ){

if ( element.compareTo(node.element) < 0){

if( node.leftNode == null ){

node.leftNode = new Node(element);

}else{

addElementRecursive(element, node.leftNode);

}

}else{

if( node.rightNode== null ){

node.rightNode= new Node(element);

}else{

addElementRecursive(element, node.rightNode);

}

}

}

protected void addElementIterative(Element element){

Node node = root;

while( true ){

if ( element.compareTo(node.element) < 0){

if( node.leftNode!= null ){

node = node.leftNode;

}else{

node.leftNode = new Node(element);

break;

}

}else{

if( node.rightNode != null ){

node = node.rightNode;

}else{

node.rightNode = new Node(element);

break;

}

}

}

}

public void showTreeRecursive(){

System.out.print("Recursive algorithm [ ");

showTreeRecursive(root);

System.out.print(" ]\n");

}

public void showTreeRecursive(Node node){

if( node != null){

showTreeRecursive(node.leftNode);

System.out.print(node.element + " ");

showTreeRecursive(node.rightNode);

}

}

public void showTreeIterative(){

SimpleStack<Node> stack = new SimpleStack<Node>();

stack.push(root);

System.out.print("Iterative algorithm [ ");

while(!stack.empty()){

Node node = stack.pop();

stack.push(node.leftNode);

System.out.print(node.element + " ");

stack.push(node.rightNode);

}

System.out.print(" ]\n");

}

private class Node{

Node leftNode;

Node rightNode;

Element element;

Node(Element element){

this.element = element;

}

}

private class SimpleStack<StackElement>{

Node head;

class Node{

Node next;

StackElement element;

Node(StackElement element, Node next){

this.element = element;

this.next = next;

}

}

boolean empty(){

return ( head == null );

}

void push(StackElement element){

if(element!= null){

head = new Node(element, head);

}

}

StackElement pop(){

if( !empty() ){

StackElement elem = head.element;

head = head.next;

return elem;

}

return null;

}

}

public static void main(String[] args){

Tree<Integer> treeRecursive = new Tree<Integer>(0);

treeRecursive.addElementRecursive( 1);

treeRecursive.addElementRecursive(-1);

treeRecursive.addElementRecursive( 2);

treeRecursive.addElementRecursive(-2);

treeRecursive.showTreeRecursive();

Tree<Integer> treeIterative = new Tree<Integer>(0);

treeIterative.addElementIterative( 1);

treeIterative.addElementIterative(-1);

treeIterative.showTreeIterative();

}

}

raindropa at 2007-7-13 21:04:22 >

> I have math algorithms in recursive form and I want

> information on how to convert it to transform it into

> iterative for faster execution.

>

> I also want information on how to convert iterative

> to recursive algorithms so the code would be more

> readable.

>

> Thank you

Google "Tail recursion optimization" for the most common form of recursive->iterative conversion.

RadcliffePikea at 2007-7-13 21:04:22 >