Contents |

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.

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.

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.

Recall the recursive implementation for finding the *n ^{th}* 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.

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 *i*^{47}.
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.

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*).

Contents |