Comparing Recursion and Looping
| Contents |

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.

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.

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.

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.

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

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.

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); }

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.

Comparing Recursion and Looping
| Contents |