Why are we using the Fibonacci Sequence to teach recursion?

It seems like almost every programming book uses the Fibonacci Sequence to teach recursion. At first glance, this seems logical: to calculate the Nth Fibonacci number, you must know the two before it. To calculate the 10th number, you add the 8th and 9th together.

Recursion seems to make sense here, because if you want 10 you need 8 and 9. If you need 8 and 9, you need to calculate 6 and 7. This goes on all the way down. That makes a lot of sense and it does demonstrate recursion pretty well.

My issue is this: recursion is the worst way to calculate the Fibonacci Sequence. So yes, we are teaching students how recursion works. But we’re also teaching them a very bad use for it. I know, I know: when are programmers ever going to need to calculate Fibonacci numbers in the Real World? Maybe they will, maybe they won’t. But if they ever do need it, they’ll think back to almost every programming course they ever took and think: “Aha! I will use recursion like I learned in class.”

Why is recursion bad (in this case)?

I could go into all the theoretical math involving time complexity, but let’s just try them instead. There’s nothing like actually seeing the difference first hand.

Let’s compare two methods in Python:

import timeit
import sys

def recursive(n):
    global additions, function_calls

    function_calls += 1
    sys.stderr.write(f"Recursive({n})    \r")  # Ease user anxiety

    if n <= 0:
       return "I am not doing that."
    elif n == 1:
       # Not counting these as additions
       return 1
    elif n == 2:
       # Not counting these as additions
       return 1
    else:
       # Add my own instance's values.
       additions += 1
       return recursive(n-1) + recursive(n-2)

def iterative(n):
    global additions, function_calls

    function_calls += 1

    if n <= 0:
       return "I am still not doing that."
    elif n == 1:
       # Still not counting these as additions
       return 0
    elif n == 2:
       # Still not counting these as additions
       return 1
    else:
       a, b = 1, 1
       for i in range(n-2):
           a, b = b, a + b
           additions += 1
           sys.stderr.write(f"Iterative({i})    \r") # Ease user anxiety
       return b
    return result

n = sys.stderr.write("Please enter a value for N: ")
n = input()
n = int(n)


# Time the iterative algorithm
function_calls = additions = 0  # These will be used as global variables
start_time = timeit.default_timer()
result = iterative(n)
end_time = timeit.default_timer()
execution_time = end_time - start_time

print(f"Iterative\nResult: {result} Additions: {additions} Function calls: 1 Execution time: {execution_time}")   

# Time the recursive version
function_calls = additions = 0  # Reset our global variables
start_time = timeit.default_timer()
result = recursive(n)
end_time = timeit.default_timer()
execution_time = end_time - start_time


print(f"Recursive\nResult: {result} Additions: {additions} Function calls: {function_calls} Execution time: {execution_time}")  

As you can see, I used an iterative function first and then the recursive version second. I did them in this order so I could get results for the iterative version quickly and then the recursive results eventually. I tracked the total addition operations, function calls and execution time. I played around with various inputs but for the demonstration here I went with 25, 30 and 7718. The iterative function did pretty well:

Iterative
Result: 75025 Additions: 23 Function calls: 1 Execution time: 0.004399699973873794
Result: 832040 Additions: 28 Function calls: 1 Execution time: 0.005835500021930784

The recursive version did not do as well:

Recursive
Result: 75025 Additions: 75024 Function calls: 150049 Execution time: 24.754127599997446
Result: 832040 Additions: 832039 Function calls: 1664079 Execution time: 274.5497388999793

You can see that the iterative versions both took just a few milliseconds. The recursive version took almost 25 seconds for the 25th number (not too bad) but then just asking for 5 more made the time jump up to almost five minutes thanks to exponential growth. Asking for 50 makes it take days. When I was learning C ages ago in a DOS environment, asking for too many would give me a stack overflow pretty quickly. Thankfully, we aren’t limited to very tiny stack/heap sizes anymore so you can reasonably expect to get results for pretty high values assuming you’ve got the free time and the Sun doesn’t go out before it’s done calculating. 😉

I asked the iterative version for 7718 (it’s a strange number but I’m pretty sure) and it took about 1.5 seconds. My iterative version isn’t even the most efficient way, there are other algorithms that may do better in some cases (such as Binet’s formula). But it’s pretty clear that recursion is one of the worst ways to calculate any relatively large value.

So how should we teach recursion?

I know the Quicksort algorithm may be too complicated for a programming class that is just learning about recursion. So what’s something simple that most people know? When I took Java in college our recursion exercise was one simple thing that (at least here in the states) is widely known. The assignment was to print the lyrics of The Twelve Days of Christmas. I found this change of pace refreshing.

In The Twelve Days of Christmas, the singer is describing all the gifts their true love gave them on each day of Christmas. Each day a new gift is introduced and the quantity matches the day. Finally, on day twelve, the ridiculous amount of gifts are finally all given with the arrival of the twelve drummers drumming. Since each day repeats all of the previous days, recursion does work well for this use.

import timeit
import sys

days = ["first","second","third","fourth","fifth","sixth","seventh","eighth","ninth","tenth","eleventh","twelfth"]
gifts = ["a partridge in a pear tree.",
        "two turtle doves, and",
        "three French hens,",
        "four calling birds,",
        "five golden rings,",
        "six geese a-laying,",
        "seven swans a swimming,",
        "eight maids a milking,",
        "nine ladies dancing,",
        "ten lords a-leaping,",
        "eleven pipers piping,",
        "twelve drummers drumming,"
        ]


def recursive(n, max):
    global function_calls, days, gifts

    function_calls += 1

    if n < 0:
       return
    else:
       if max:
         print(f"\nOn the {days[n]} day of Christmas, my true love gave to me: ")

       print(gifts[n])
       recursive(n-1, False)

def iterative(n):
    global function_calls, days, gifts

    function_calls += 1

    for n in range(12):

       print(f"\nOn the {days[n]} day of Christmas, my true love gave to me: ")
       for i in range(n, -1, -1):
           print(gifts[i]);
    return

function_calls = 0  # These will be used as global variables
start_time = timeit.default_timer()

iterative(12)



end_time = timeit.default_timer()
execution_time = end_time - start_time

print(f"\n\nIterative\nFunction calls: {function_calls} Execution time: {execution_time}")

# Time the recursive version
function_calls = 0  # Reset our global variables
start_time = timeit.default_timer()
for n in range(12):
  recursive(n, True)
end_time = timeit.default_timer()
execution_time = end_time - start_time


print(f"\n\nRecursive\nFunction calls: {function_calls} Execution time: {execution_time}")

I used the same basic shell of the program and decided to time the iterative and recursive versions. This time, the recursive version actually wins:

Iterative
Function calls: 1 Execution time: 0.00044239999260753393
Recursive
Function calls: 90 Execution time: 0.0003551999689079821

I’m a bit surprised that the recursive version is faster. I would have thought the overhead of the function calls plus the repeated checking of the boolean “max” parameter to see if the heading needed to be printed would have added more time. I expected it to be pretty close, though, and close enough to justify using this to teach recursion.

In Conclusion

We talked about the Fibonacci sequence and why it’s a bad way to teach recursion since it’s not something you would actually want to use recursion for. We need to be more creative when teaching this concept. The Towers of Hanoi and The Twelve Days of Christmas are the only two I’ve seen in a programming book. How about you? Have you seen some other simple uses for recursion? How about real-world uses for the Fibonacci Sequence? Put your favorite ones in the comments: