Explore BrainMass

Explore BrainMass

    How to Convert a Recursive Procedure into Iterative

    Not what you're looking for? Search our solutions OR ask your own Custom question.

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

    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 ad1c9bdddf
    https://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

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

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

    Attachments

    ADVERTISEMENT