Recursion Patterns Top MatricesComparing Recursion and Looping Contents

Comparing Recursion and Looping

You can download the functions defined or used in this chapter with the following commands:

    wget troll.cs.ua.edu/ACP-C/recursionLoop.c
    wget troll.cs.ua.edu/ACP-C/recursionLoop.h

These files will help you run the test code listed in this chapter.

Converting Recursions to Iterative loops

In previous chapters, we learned about repeatedly evaluating the same code using both recursion and loops. Now we compare and contrast the two techniques by implementing the three mathematical functions from the chapter on recursion: factorial, fibonacci, and gcd, with loops.

Factorial

Recall that the factorial function, written recursively, looks like this:

    int
    factorial(int n)
        {
        if (n == 0)
            return 1;
        else
            return n * factorial(n - 1);
        }

We see that is a form of the accumulate pattern. So our factorial function using a loop should look something like this:

    int
    factorialLoop(int n)
        {
        int i;
        int total = ???;
        for (i = ???; i < ???; i += ???)
            {
            total *= ???;
            }
        return total;
        }

Since we are accumulating a product, it makes sense that total should be initialized to 1. Also, since we need to multiply all the values from from 1 to n to compute the factorial, it makes sense to have the loop variable i take on all those values:

    int
    factorialLoop(int n)
        {
        int i;
        int total = 1;
        for (i = 1; i < n+1; ++i)
            {
            total *= ???;
            }
        return total;
        }

Finally, we accumulate i into the total:

    int
    factorialLoop(int n)
        {
        int i;
        int total = 1;
        for (i = 1; i < n+1; ++i)
            {
            total *= i;
            }
        return total;
        }

The limit on the for loop is set to n+1 instead of n because we want n to be included in the total.

Now, compare the loop version to the recursive version. Both contain about the same amount of code, but the recursive version is easier to ascertain as correct.

The greatest common divisor

Here is a slightly different version of the gcd function, built using the following recurrence:

gcd(a,b) is a if b is zero
gcd(a,b) is gcd(b,a % b) otherwise

The function allows one more recursive call than the version shown previously. By doing so, we eliminate the need for the local variable remainder. Here is the implementation:

    int
    gcd(int a,int b)
        {
        if (b == 0)
            return a;
        else
            return gcd(b,a % b);
        }

Let's turn it into a looping function. This style of recursion doesn't fit any of the patterns we know, so we'll have to start from scratch. We do know that b becomes the new value of a and a % b becomes the new value of b on every recursive call, so the same thing must happen on every evaluation of the loop body. We stop when b is equal to zero so we should continue looping while b is not equal to zero. These observations lead us to this implementation:

    int
    gcdLoop(int a,int b)
        {
        while (b != 0)
            {
            a = b;
            b = a % b;
            }
        return a;
        }

Unfortunately, this implementation is faulty, since we've lost the original value of a by the time we perform the modulus operation. Reversing the two statements in the body of the loop:

    {
    b = a % b;
    a = b;
    }

is no better; we lose the original value of b by the time we assign it to a. What we need to do is temporarily save the original value of b before we assign a's value. Then we can assign the saved value to a after b has been reassigned:

    int
    gcdLoop(int a,int b)
        {
        while (b != 0)
            {
            int temp = b;
            b = a % b;
            a = temp;
            }
        return a;
        }

Now the function is working correctly. But why did we temporarily need to save a value in the loop version and not in the recursive version? The answer is that the recursive call does not perform any assignments so no values were lost. On the recursive call, new versions of the formal parameters a and b received the computations performed for the function call. The old versions were left untouched.

The Fibonacci sequence

Recall the recursive implementation for finding the nth Fibonacci number:

    int
    fibonacci(int n)
        {
        if (n < 2)
            return n;
        else
            return fibonacci(n - 1) + fibonacci(n - 2);
        }

For brevity, we have collapsed the two base cases into a single base case. If n is zero, zero is returned and if n is one, one is returned, as before.

Let's try to implement fib using an iterative loop. As before, this doesn't seem to fit a pattern, so we start by reasoning about this. If we let a be the first Fibonacci number, zero, and b be the second Fibonacci number, one, then the third fibonacci number would be a + b, which we can save in a variable named c. At this point, the fourth Fibonacci number would be b + c, but since we are using a loop, we need to have the code be the same for each iteration of the loop. If we let a have the value of b and b have the value of c, then the fourth Fibonacci number would be a + b again. This leads to our implementation:

    int
    fibonacciLoop(int n)
        {
        int i;          //the loop variable
        int a = 0;      //the first Fibonacci number
        int b = 1;      //the second Fibonacci number
        for (i = 0; i < n; ++i) //n steps
            {
            int c = a + b;
            a = b;
            b = c;
            }
        return a;
        }

In the loop body, we see that fibonacciLoop is much like gcdLoop; the second number becomes the first number and some combination of the first and second number becomes the second number. In the case of gcdLoop, the combination was the remainder and, in the case of fib, the combination is sum. A rather large question remains, why does the function return a instead of b or c? The reason is, suppose fib was called with a value of zero, which is supposed to generate the first Fibonacci number. The loop does not run in this case and the value of a is returned, which is zero, as required. If a value of one is passed to fib, then the loop runs exactly once and a gets the original value of b, which is one. The loop exits and this time, one is returned, as required. So, empirically, it appears that the value of a is the correct choice of return value. As with factorial, hitting on the right way to proceed iteratively is not exactly straightforward, while the recursive version practically wrote itself.

Transforming loops into recursions

Transforming a recursive function to a loop sometimes takes a good deal of thought, but going the other way is somewhat easier. To transform an iterative loop into a recursive loop, one first identifies those variables that exist outside the loop but are referenced by the loop; these variable will become formal parameters in the recursive function. One then builds a helper function that has these "outside" variables as formal parameters. Finally, one builds a wrapper function that calls the helper with the initial values of the "outer" variables.

Fibonacci

For an example conversion, the fibonacciLoop function defined previously has a loop; that loop has four "outside" variables that are referenced by the for loop: a, b, i 50, and n. The variable c is used only inside the loop and thus is ignored.

Given this, we start out our recursive function like so:

    int
    fibonacciHelper(int a,int b,int i,int n)
        {
        ...
        }

If our original function was named XXX, we will name this new function XXXHelper. The original loop test becomes an if test in the body of the fibonacciHelper function:

    int
    fibonacciHelper(int a,int b,int i,int n)
        {
        if (i < n)
            ...
        else
            ...
        }

The if-true block becomes the recursive call. The arguments to the recursive call encode the updates to the loop variables. On the other hand, the if-false block becomes the value the loop attempted to calculate:

    int
    fibonacciHelper(int a,int b,int i,int n)
        {
        if (i < n)
            return fibonacciHelper(b,a + b,i + 1,n);
        else
            return a;
        }

Remember, a gets the value of b and b gets the value of c which is a + b. Since we are performing recursion with no assignments, we don't need the variable c anymore. The loop variable i is incremented by one each time. Because n is unchanged by the original loop, is is unchanged in the recursive call.

Next, we define a function with the same signature as the original function. We change the name, affixing the number 2, to remind us that this version works via a different sort of recursion compared to the original recursive fibonacci function. The body of this new function returns a call to the helper function:

    int
    fibonacci2(int n)
        {
        return fibonacciHelper(???,???,???,n);
        }

To complete our task, we fill out the arguments to the helper function with the initial values of the variables referenced by the original loop:

    int
    fibonacci2(int n)
        {
        return fibonacciHelper(0,1,0,n);
        }

Since a starts at 0, b starts at 1, and i starts at zero for the original loop, we pass those values in the initial call to the helper function. As before, since n never changes, we simply pass n along to the helper.

Note that this recursive function looks nothing like our original fibonacci. However, it suffers from none of the inefficiencies of the original version and yet it performs no assignments.51 The reason for its efficiency is that it performs the exact calculations and number of calculations as the iterative loop-based function.

Factorial

For more practice, let's convert the iterative version of factorial into a recursive function using this method. We'll again end up with a different recursive function than before. For convenience, here is the loop version:

    int
    factorialLoop(int n)
        {
        int i;
        int total = 1;
        for (i = 1; i < n+1; ++i)
            {
            total *= i;
            }
        return total;
        }

We start, as before, by working on the helper function. In this case, only three outside variables are referenced by the loop: total, i, and n:

    int
    factorialHelper(int total,int i,int n)
        {
        ...
        }

Next, we write the if statement:

    int
    factorialHelper(int total,int i,int n)
        {
        if (i < n + 1)
            return factorialHelper(total * i,i + 1,n);
        else
            return total;
        }

Next, we define the recursive factorial function, which calls the helper:

    int
    factorial2(int n)
        {
        return factorialHelper(1,1,n);
        }

Which way to go?

The moral of this story is that any iterative loop can be rewritten as a recursion and any recursion can be rewritten as an iterative loop. Moreover, in good languages,52 there is no reason to prefer one way over the other, either in terms of the time it takes or the space used in execution. To reiterate, use a recursion if that makes the implementation more clear, otherwise, use an iterative loop.

lusth@cs.ua.edu


Recursion Patterns Top MatricesComparing Recursion and Looping Contents