Recursion Vs Iteration

http://www.refactoring.com/catalog/replaceRecursionWithIteration.html


Recurse function is not a function restarting itself, it is hundreds of functions that are each unfinished with the last one calling a new recurse function.

Recursion is implemented as a method that calls itself to solve subtasks. During the recursive call the values of the local fields of the method are placed on the method stack until the subtask performed by a recursive call is completed. Thus, whenever recursive method is called, local fields are put on the method stack and used again after the recursive call is completed. The general approach to Refactoring could probably be to implement the alternative Stack that "simulates" the method stack where the local fields could be placed.

Sometimes a recursive solution doesn't preserve any local fields during the recursive call, which makes Refactoring much easier. This is the case with, so called, tail recursions. Tail recursions are recursions where the recursive call is the last line in the method. Tail recursions are generally considered a bad practice and should be replaced with Iteration. This technique is well known to the people who work on compiler implementations. A good compiler usually performs this Refactoring on the fly.

Refactoring Mechanics:

1. Determine the base case of the Recursion. Base case, when reached, causes Recursion to end. Every Recursion must have a defined base case. In addition, each recursive call must make a progress towards the base case (otherwise recursive calls would be performed infinitely). In our example the base case is n == 0.

2. Implement a loop that will iterate until the base case is reached.

3. Make a progress towards the base case. Send the new arguments to the top of the loop instead to the recursive method.

Examples and Practices:

1. Reversely output an input line

void wrt_it(void)
{
int c;
if((c=getchar()) !='\n')
wrt_it();
putchar(c);
}

void wrt_stack()
{
stack s;
char single;

while((single = getchar())!= '\n')
s.push(single);

while(!s.empty())
{
cout << s.top();
s.pop();
}

}

2. Tree Preoder Traversal

void PreorderTraversal(node *root)
{
if(root!=NULL)
{
printf("%d\n", root->value);
PreorderTraversal(root->left);
PreorderTraversal(root->right);
}

}

3. Tree Inorder Traversal
void InorderTraversal(node *root)
{
if(root!=NULL)
{
InorderTraversal(root->left);
printf("%d\n", root->value);
InorderTraversal(root->right);
}

}

4. Tree Postorder Traversal
void InorderTraversal(node *root)
{
if(root!=NULL)
{
PostorderTraversal(root->left);
PostorderTraversal(root->right);
printf("%d\n", root->value);
}

}

5. n! (pronounced "n factorial")

Recursion relation:
n!= n* (n-1)!
0!=1!=1

int Factorial(int n)
{
if(n>1) //recursive case
return Factorial(n-1)*n;
else //base case
return 1;
}




Summary: If you understand exactly how the recursive implementation implicitly started data on the stack, you can write an iterative implementation that explicitly stores data on a stack in the same fashion.