2
Recursion vs. Iteration

Neither recursion nor iteration is a superior technique in general. In fact, any recursive code can be written as iterative code with a loop and a stack. Recursion doesn’t have some special power enabling it to perform calculations that an iterative algorithm cannot. And any iterative loop can be rewritten as a recursive function.

This chapter compares and contrasts recursion and iteration. We’ll look at the classic Fibonacci and factorial functions and see why their recursive algorithms have critical weaknesses. We’ll also explore the insights a recursive approach can yield by considering an exponent algorithm. Altogether this chapter shines light on the supposed elegance of recursive algorithms and shows when a recursive solution is useful and when it is not.

Calculating Factorials

Many computer science courses use factorial calculation as a classic example of a recursive function. The factorial of an integer (let’s call it n) is the product of all integers from 1 to n. For example, the factorial of 4 is 4 × 3 × 2 × 1, or 24. An exclamation mark is the math notation for factorials, as in 4!, which means the factorial of 4. Table 2-1 shows the first few factorials.

Factorials are used in all sorts of calculations—for example, finding the number of permutations for something. If you want to know the number of ways that exist to order four people—Alice, Bob, Carol, and David—in a line, the answer is the factorial of 4. Four possible people can be first in line (4); then for each of those four options, three remaining people can be second in line (4 × 3); then two people can be third in line (4 × 3 × 2); and the last person left will be fourth in line (4 × 3 × 2 × 1). The number of ways people can be ordered in line—that is, the number of permutations—is the factorial of the number of people.

Now let’s examine both an iterative and a recursive approach to calculating factorials.

The Iterative Factorial Algorithm

Calculating factorials iteratively is fairly straightforward: multiply the integers 1 up to and including n in a loop. Iterative algorithms always use a loop. A factorialByIteration.py program looks like this:

Python

def factorial(number):
    product = 1
    for i in range(1, number + 1):
        product = product * i
    return product
print(factorial(5))

And a factorialByIteration.html program looks like this:

JavaScript

<script type="text/javascript">
function factorial(number) {
    let product = 1;
    for (let i = 1; i <= number; i++) {
        product = product * i;
    }
    return product;
}
document.write(factorial(5));
</script>

When you run this code, the output displays the calculation for 5! like this:

120

There’s nothing wrong with the iterative solution for calculating factorials; it’s straightforward and gets the job done. But let’s also take a look at the recursive algorithm for insights into the nature of factorials and recursion itself.

The Recursive Factorial Algorithm

Notice that the factorial of 4 is 4 × 3 × 2 × 1, and the factorial of 5 is 5 × 4 × 3 × 2 × 1. So you could say that 5! = 5 × 4!. This is recursive because the definition of the factorial of 5 (or any number n) includes the definition of the factorial of 4 (the number n – 1). In turn, 4! = 4 × 3!, and so on, until you must calculate 1!, the base case, which is simply 1.

The factorialByRecursion.py Python program uses a recursive factorial algorithm:

Python

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
      ❶ return number * factorial(number - 1)
print(factorial(5))

And the factorialByRecursion.html JavaScript program with equivalent code looks like this:

JavaScript

<script type="text/javascript">
function factorial(number) {
    if (number == 1) {
        // BASE CASE
        return 1;
    } else {
        // RECURSIVE CASE
      ❶ return number * factorial(number - 1);
    }
}
document.write(factorial(5));
</script>

When you run this code to calculate 5! recursively, the output matches the iterative program’s output:

120

To many programmers, this recursive code looks strange. You know that factorial(5) must compute 5 × 4 × 3 × 2 × 1, but it’s hard to point to the line of code where this multiplication is taking place.

The confusion arises because the recursive case has one line ❶, half of which is executed before the recursive call and half of which takes place after the recursive call returns. We aren’t used to the idea of only half of a line of code executing at a time.

The first half is factorial(number - 1). This involves calculating number - 1 and making a recursive function call, causing a new frame object to be pushed to the call stack. This happens before the recursive call is made.

The next time the code runs with the old frame object is after factorial(number - 1) has returned. When factorial(5) is called, factorial(number - 1) will be factorial(4), which returns 24. This is when the second half of the line runs. The return number * factorial(number - 1) now looks like return 5 * 24, which is why factorial(5) returns 120.

Figure 2-1 tracks the state of the call stack as frame objects are pushed (which happens as recursive function calls are made) and frame objects are popped (as recursive function calls return). Notice that the multiplication happens after the recursive calls are made, not before.

When the original function call to factorial() returns, it returns the calculated factorial.

Why the Recursive Factorial Algorithm Is Terrible

The recursive implementation for calculating factorials has a critical weakness. Calculating the factorial of 5 requires five recursive function calls. This means five frame objects are placed on the call stack before the base case is reached. This doesn’t scale.

If you want to calculate the factorial of 1,001, the recursive factorial() function must make 1,001 recursive function calls. However, your program is likely to cause a stack overflow before it can finish, because making so many function calls without returning would exceed the maximum call stack size of the interpreter. This is terrible; you would never want to use a recursive factorial function in real-world code.

The iterative factorial algorithm, on the other hand, will complete the calculation quickly and efficiently. The stack overflow can be avoided using a technique available in some programming languages called tail call optimization. Chapter 8 covers this topic. However, this technique further complicates the implementation of the recursive function. For calculating factorials, the iterative approach is the simplest and most direct.

Calculating the Fibonacci Sequence

The Fibonacci sequence is another classic example for introducing recursion. Mathematically, the Fibonacci sequence of integers begins with the numbers 1 and 1 (or sometimes, 0 and 1). The next number in the sequence is the sum of the previous two numbers. This creates the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, and so on, forever.

If we call the latest two numbers in the sequence a and b, you can see in Figure 2-2 how the sequence grows.

Let’s explore some code examples of both the iterative and recursive solutions for generating Fibonacci numbers.

The Iterative Fibonacci Algorithm

The iterative Fibonacci example is straightforward, consisting of a simple for loop and two variables, a and b. This fibonacciByIteration.py Python program implements the iterative Fibonacci algorithm:

Python

def fibonacci(nthNumber):
  ❶ a, b = 1, 1
    print('a = %s, b = %s' % (a, b))
    for i in range(2, nthNumber):
      ❷ a, b = b, a + b # Get the next Fibonacci number.
        print('a = %s, b = %s' % (a, b))
    return a

print(fibonacci(10))

This fibonacciByIteration.html program has the equivalent JavaScript code:

JavaScript

<script type="text/javascript">
function fibonacci(nthNumber) {
  ❶ let a = 1, b = 1;
    let nextNum;
    document.write('a = ' + a + ', b = ' + b + '<br />');
    for (let i = 2; i < nthNumber; i++) {
      ❷ nextNum = a + b; // Get the next Fibonacci number.
        a = b;
        b = nextNum;
        document.write('a = ' + a + ', b = ' + b + '<br />');
    }
    return a;
};

document.write(fibonacci(10));
</script>

When you run this code to calculate the 10th Fibonacci number, the output looks like this:

a = 1, b = 1
a = 1, b = 2
a = 2, b = 3
--snip--
a = 34, b = 55
55

The program needs to track only the latest two numbers of the sequence at a time. Since the first two numbers in the Fibonacci sequence are defined as 1, we store 1 in variables a and b ❶. Inside the for loop, the next number in the sequence is calculated by adding a and b ❷, which becomes the next value of b, while a obtains the previous value of b. By the time the loop is finished, b contains the nth Fibonacci number, so it is returned.

The Recursive Fibonacci Algorithm

Calculating Fibonacci numbers involves a recursive property. For example, if you want to calculate the 10th Fibonacci number, you add the ninth and eighth Fibonacci numbers together. To calculate those Fibonacci numbers, you add the eighth and seventh, then the seventh and sixth Fibonacci numbers. A lot of repeat calculations occur: notice that adding the ninth and eighth Fibonacci numbers involves calculating the eighth Fibonacci number again. You continue this recursion until you reach the base case of the first or second Fibonacci number, which is always 1.

The recursive Fibonacci function is in this fibonacciByRecursion.py Python program:

def fibonacci(nthNumber):
    print('fibonacci(%s) called.' % (nthNumber))
    if nthNumber == 1 or nthNumber == 2: ❶
        # BASE CASE
        print('Call to fibonacci(%s) returning 1.' % (nthNumber))
        return 1
    else:
        # RECURSIVE CASE
        print('Calling fibonacci(%s) and fibonacci(%s).' % (nthNumber - 1, nthNumber - 2))
        result = fibonacci(nthNumber - 1) + fibonacci(nthNumber - 2)
        print('Call to fibonacci(%s) returning %s.' % (nthNumber, result))
        return result

print(fibonacci(10))

This fibonacciByRecursion.html file has the equivalent JavaScript program:

<script type="text/javascript">
function fibonacci(nthNumber) {
    document.write('fibonacci(' + nthNumber + ') called.<br />');
    if (nthNumber === 1 || nthNumber === 2) { ❶
        // BASE CASE
        document.write('Call to fibonacci(' + nthNumber + ') returning 1.<br />');
        return 1;
    }
    else {
        // RECURSIVE CASE
        document.write('Calling fibonacci(' + (nthNumber - 1) + ') and fibonacci(' + (nthNumber - 2) + ').<br />');
        let result = fibonacci(nthNumber - 1) + fibonacci(nthNumber - 2);
        document.write('Call to fibonacci(' + nthNumber + ') returning ' + result + '.<br />');
        return result;
    }
}

document.write(fibonacci(10) + '<br />');
</script>

When you run this code to calculate the 10th Fibonacci number, the output looks like this:

fibonacci(10) called.
Calling fibonacci(9) and fibonacci(8).
fibonacci(9) called.
Calling fibonacci(8) and fibonacci(7).
fibonacci(8) called.
Calling fibonacci(7) and fibonacci(6).
fibonacci(7) called.
--snip--
Call to fibonacci(6) returning 8.
Call to fibonacci(8) returning 21.
Call to fibonacci(10) returning 55.
55

Much of the code is for displaying this output, but the fibonacci() function itself is simple. The base case—the circumstances where recursive calls are no longer made—occurs when nthNumber is 1 or 2 ❶. In this case, the function returns 1 since the first and second Fibonacci numbers are always 1. Any other case is a recursive case, so the value that is returned is the sum of fibonacci(nthNumber - 1) and fibonacci(nthNumber - 2). As long as the original nthNumber argument is an integer greater than 0, these recursive calls will eventually reach the base case and stop making more recursive calls.

Remember how the recursive factorial example had a “before the recursive call” and “after the recursive call” part? Because the recursive Fibonacci algorithm makes two recursive calls in its recursive case, you should keep in mind that it has three parts: “before the first recursive call,” “after the first recursive call but before the second recursive call,” and “after the second recursive call.” But the same principles apply. And don’t think that because a base case is reached, no more code remains to run after either recursive call. The recursive algorithm is finished only after the original function call has returned.

You might ask, “Isn’t the iterative Fibonacci solution simpler than the recursive Fibonacci solution?” The answer is “Yes.” Even worse, the recursive solution has a critical inefficiency that is explained in the next section.

Why the Recursive Fibonacci Algorithm Is Terrible

Like the recursive factorial algorithm, the recursive Fibonacci algorithm also suffers from a critical weakness: it repeats the same calculations over and over. Figure 2-3 shows how calling fibonacci(6), marked in the tree diagram as fib(6) for brevity, calls fibonacci(5) and fibonacci(4).

This causes a cascade of other function calls until they reach the base cases of fibonacci(2) and fibonacci(1), which return 1. But notice that fibonacci(4) is called twice, and fibonacci(3) is called three times, and so on. This slows the overall algorithm with unnecessarily repeated calculations. This inefficiency gets worse as the Fibonacci number you want to calculate gets larger. While the iterative Fibonacci algorithm can complete fibonacci(100) in less than a second, the recursive algorithm would take over a million years to complete.

Converting a Recursive Algorithm into an Iterative Algorithm

Converting a recursive algorithm into an iterative algorithm is always possible. While recursive functions repeat a calculation by calling themselves, this repetition can be performed instead by a loop. Recursive functions also make use of the call stack; however, an iterative algorithm can replace this with a stack data structure. Thus, any recursive algorithm can be performed iteratively by using a loop and a stack.

To demonstrate this, here is factorialEmulateRecursion.py, a Python program that implements an iterative algorithm to emulate a recursive algorithm:

callStack = [] # The explicit call stack, which holds "frame objects". ❶
callStack.append({'returnAddr': 'start', 'number': 5}) # "Call" the "factorial() function". ❷
returnValue = None

while len(callStack) > 0:
    # The body of the "factorial() function":

    number = callStack[-1]['number'] # Set number parameter.
    returnAddr = callStack[-1]['returnAddr']

    if returnAddr == 'start':
        if number == 1:
            # BASE CASE
            returnValue = 1
            callStack.pop() # "Return" from "function call". ❸
            continue
        else:
            # RECURSIVE CASE
            callStack[-1]['returnAddr'] = 'after recursive call'
            # "Call" the "factorial() function":
            callStack.append({'returnAddr': 'start', 'number': number - 1}) ❹
            continue
    elif returnAddr == 'after recursive call':
        returnValue = number * returnValue
        callStack.pop() # "Return from function call". ❺
        continue

print(returnValue)

The factorialEmulateRecursion.html program holds the equivalent JavaScript:

<script type="text/javascript">
let callStack = []; // The explicit call stack, which holds "frame objects". ❶
callStack.push({"returnAddr": "start", "number": 5}); // "Call" the "factorial() function". ❷
let returnValue;

while (callStack.length > 0) {
// The body of the "factorial() function":
    let number = callStack[callStack.length - 1]["number"]; // Set number parameter.
    let returnAddr = callStack[callStack.length - 1]["returnAddr"];

    if (returnAddr == "start") {
        if (number === 1) {
            // BASE CASE
            returnValue = 1;
            callStack.pop(); // "Return" from "function call". ❸
            continue;
        } else {
            // RECURSIVE CASE
            callStack[callStack.length - 1]["returnAddr"] = "after recursive call";
            // "Call" the "factorial() function":
            callStack.push({"returnAddr": "start", "number": number - 1}); ❹
            continue;
        }
    } else if (returnAddr == "after recursive call") {
        returnValue = number * returnValue;
        callStack.pop(); // "Return from function call". ❺
        continue;
    }
}

document.write(returnValue + "<br />");
</script> 

Notice that this program doesn’t have a recursive function; it doesn’t have any functions at all! The program emulates recursive function calls by using a list as a stack data structure (stored in the callStack variable ❶) to mimic the call stack. A dictionary storing the return address information and nthNumber local variable emulates a frame object ❷. The program emulates function calls by pushing these frame objects onto the call stack ❹, and it emulates returning from a function call by popping frame objects off the call stack 35.

Any recursive function can be written iteratively this way. Although this code is incredibly difficult to understand and you’d never write a real-world factorial algorithm this way, it does demonstrate that recursion has no innate capability that iterative code does not have.

Converting an Iterative Algorithm into a Recursive Algorithm

Likewise, converting an iterative algorithm into a recursive algorithm is always possible. An iterative algorithm is simply code that uses a loop. The code that is repeatedly executed (the loop’s body) can be placed in a recursive function’s body. And just as the code in the loop’s body is executed repeatedly, we need to repeatedly call the function to execute its code. We can do this by calling the function from the function itself, creating a recursive function.

The Python code in hello.py demonstrates printing Hello, world! five times by using a loop and then also using a recursive function: