How to Convert a Recursive Procedure into Iterative

Recursive Procedure: A recursive procedure is a method or a function that calls itself over and over again as long as it satisfies the recursive conditionm[1][2]. Recursive procedures are easier to design as they more closely reflect the modeling technique and mathematical properties. Interestingly, examples of recursive are present in nature. Fractals and flower petal patterns are two such examples.

The Fibonacci sequence is a popular example of recursion[3]:
[base cases]
Fib(0) is 1
Fib(1) is 1
For all integers n > 1: Fib(n) is (Fib(n-1) + Fib(n-2)) [recursive definition]

We can write a simple C code snippet for this definition.

fibonacci(int n){ //Begin Procedure Fibonacci.
int i;
//base cases
if (n == 0)
return 1;
if (n == 1)
return 1;
//recursive definition
return fibonacci(n-1) + fibonacci(n-2);
} //End procedure Fibonacci

The next step is to write it as an iterative procedure as follows:

using the C code snippet example as before, we can define the factorial(n) recursively as

int fibonacci (int n) {

int i;
int last = 1;
int lastbutone = 1;
int result = 1;

if (n==0 || n==1)
{
return 1;
}

for(i=2; i<= n; i++) {
result = last + lastbutone;
lastbutone= last;
last = result;
}
return result;
}

Although recursive procedures are simple and close to mathematical definitions, they pose real problems when implemented in computers, since they must make use of temporary memory called stacks (or registers). This is necessary to keep the intermediate values between the calls. Another issue that can cause potential problems is the repetitive calling of functions. Normally, when a function is called a number of machine level operation (including pushing and popping of function pointers) must be done, which requires a certain amount of time. When a large number of function calls are made, these add up to a significant delay in processing. All of these problems are solved easily using the iterative procedure where a fixed number of variables, (usually) a single call to a function, and a well defined loop (for or while) can give the desired results.

[1] Johnsonbaugh, Richard. Discrete Mathematics. Prentice Hall. ISBN 0-13-117686-2. 2004.
[2] Hofstadter, Douglas. Gödel, Escher, Bach: An Eternal Golden Braid. Basic Books. ISBN 0-465-02656-7. 1999.
[3] http://en.wikipedia.org/wiki/Factorial

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!