Recursion Top Two-dimensional Arrays Contents

Comparing Recursion and Looping

In the 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:

    def factorial(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:

    def factorial(n):
        total = ???
        for i in range(???):
            total *= ???
        return total

Since we are accumulating a product, total should be initialized to 1.

    def factorial(n):
        total = 1
        for i in range(???):
            total *= ???
        return total

Also, the loop variable should take on all values in the factorial, from 1 to n:

    def factorial(n):
        total = 1
        for i in range(1,n+1,1):
            total *= ???
        return total

Finally, we accumulate i into the total:

    def factorial(n):
        total = 1
        for i in range(1,n+1,1):
            total *= i
        return total

The second argument to range 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:

    def gcd(a,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:

    def gcd(a,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:

    def gcd(a,b):
        while (b != 0):
            b = a % b
            a = b
        return a

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:

    def gcd(a,b):
        while (b != 0):
            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.

It should be noted that Python allows simultaneous assignment that obviates the need for the temporary variable:

    def gcd(a,b):
        while (b != 0):
            a,b = b,a % b
        return a

While this code is much shorter, it is a little more difficult to read. Moreover, other common languages do not share this feature and you are left using a temporary variable to preserve needed values when using those languages.

The Fibonacci sequence

Recall the recursive implementation for finding the nth Fibonacci number:

    def fib(n):
        if (n < 2):
            return n
        else:
            return fib(n - 1) + fib(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:

    def fib(n):
        a = 0    # the first Fibonacci number
        b = 1    # the second Fibonacci number
        for i in range(0,n,1):
            c = a + b
            a = b
            b = c
        return a

In the loop body, we see that fib is much like gcd; the second number becomes the first number and some combination of the first and second number becomes the second number. In the case of gcd, 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 0, 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.

CHALLENGE: Transforming loops into recursions

To transform an iterative loop into a recursive loop, one first identifies those variables that exist outside the loop but are changing in the loop body; these variable will become formal parameters in the recursive function. For example, the fib loop above has three (not two!) variables that are being changed during each iteration of the loop: a, b, and i47. The variable c is used only inside the loop and thus is ignored.

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

    def loop(a,b,i):
        ...

The loop test becomes an if test in the body of the loop function:

    def loop(a,b,i)
        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. The if-false block becomes the value the loop attempted to calculate:

    def loop(a,b,i):
        if (i < n):
            return loop(b,a + b,i + 1)
        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.

Next, we replace the loop with the the loop function in the function containing the original loop. That way, any non-local variables referenced in the test or body of the original loop will be visible to the loop function:

    def fib(n):
        def loop(a,b,i):
            if (i < n):
                return loop(b,a + b,i + 1)
            else:
                return a
        ...

Finally, we call the loop function with the initial values of the loop variables:

    def fib(n):
        def loop(a,b,i):
            if (i < n):
                return loop(b,a + b,i + 1)
            else:
                return a
        return loop(0,1,0)

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

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:

    def fact(n):
        total = 1
        for i in range(1,n+1,1):
            total *= i
        return total

We start, as before, by working on the loop function. In this case, only two variables are changing in the loop: total and i.

    def loop(total,i):
        ...

Next, we write the if expression:

    def loop(total,i):
        if (i < n + 1):
            return loop(total * i,i + 1)
        else:
            return total

Next, we embed the loop function and call it:

    def fact(n):
        def loop(total,i):
            if (i < n + 1):
                return loop(total * i,i + 1)
            else:
                return total
        return loop(1,1)

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,49 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.

Code

For Linux and Mac users, the code from this chapter can be found here.

For Windows users, look here (you will need to save the file as recursion-vs-loops.py).

lusth@cs.ua.edu


Recursion Top Two-dimensional Arrays Contents