# How to Convert a Recursive Procedure into Iterative

Find an example or a recursive procedure and represent it as an iterative procedure. what challenges would you face and how can we resolve it?

Â© BrainMass Inc. brainmass.com December 24, 2021, 8:08 pm ad1c9bdddfhttps://brainmass.com/math/discrete-math/convert-recursive-procedure-iterative-251275

## SOLUTION This solution is **FREE** courtesy of BrainMass!

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

https://brainmass.com/math/discrete-math/convert-recursive-procedure-iterative-251275