Don't exaggerate recursion overhead

A small pet peeve of mine is when people use the very naïve recursive implementation of the Fibonacci algorithm to show the overhead of recursion. Yes, recursion can have an overhead (depending on your environment), but it’s not nearly as much as you make it seem.

The problem, The iterative version of the Fibonacci algorithm:

def iterative_fibonacci(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b

    return a

has O(n) time complexity.

The very naïve recursive algorithm that often gets abused to show the overhead of recursion:

def naively_recursive_fibonacci(n):
    if n <= 1:
        return n

    return (naively_recursive_fibonacci(n - 1) +
        naively_recursive_fibonacci(n - 2))

has O(2^n) complexity, a few complexity classes worse and it just isn’t fair to compare it with the iterative version. The purpose of this algorithm is often just to introduce recursion, the fib(n) = fib(n - 1) + fib(n - 2) definition is easy to understand and implement, it’s not meant to actually be fast.

The performance issue isn’t with recursion but with an algorithm that isn’t meant to be performant, it’s just a teaching tool. If you actually want to compare the iterative and recursive version of the Fibonacci algorithm you should implement them in a way that they both have the same complexity:

def recursive_fibonacci(n, a = 0, b = 1):
    if n:
        return recursive_fibonacci(n - 1, b, a + b)

    return a

This recursive version is O(n) and will easily beat the former recursive version. It’s just not being taught as much since it doesn’t show the recursive definition of the Fibonacci algorithm as well.

Here is a performance benchmark of the 3 different implementations.

You’ll see that both the iterative and recursive O(n) versions easily beat the O(2^n) version, and you can even see how fast it grows with its exponential nature. Also the recursive O(n) version is still quite a bit slower than the iterative version, but there are some caveats to it. The algorithm itself could be as fast as its iterative counter part in other languages but python simply doesn’t take advantage of it for various reasons.

  • The function tail recursive, meaning that we could completely avoid creating a new frame on the call stack, but python doesn’t do tail-call optimization by design.
  • Python has a pretty decent overhead for function calls, other languages might have less. Or none at all if they make use of tail-call optimization.

I actually made a quick and dirty C++ benchmark for myself and the iterative and recursive O(n) versions were identical. C++ took complete advantage of tail-call optimization and shows that the performance issue isn’t inherent to recursion.