Why calculating Fibonacci using binary recursion is just plain moronic

The Fibonacci sequence is a series of numbers of the form:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…

It is derived such that each number is the sum of the two preceding ones, starting from F(0)=0 and F(1)=1. Or in equation form: F(n) = F(n-1) + F(n-2).

The original formula for the Fibonacci series lends itself to a natural, if somewhat naïve, example of binary recursion, which is probably the most notorious implementation found in the literature. The algorithm works by returning one if n = 1 or 2, and the sum of  f(n-1)  and f(n-2) if n>2 . Represented as a recursive function in C, this looks like:

int fib_binary(int n) {
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else
      return fib_binary(n-1) + fib_binary(n-2);
}

This algorithm certainly generates the correct answer, but what is its computational cost, i.e. how long does it take?  If n is less than two, the function halts almost immediately. However for larger values of n, there are two recursive calls of the algorithm. This implies that the running time of the algorithm grows at exponential time, or f(n)=2^0.694n, which for n=200 is 2^140 operations. 

To understand how this is possible, consider the Fibonacci call tree for calculating the 5th Fibonacci number, which just happens to be 5. Notice how many times F₁ is called?

fibonacci_tree

The biggest problem with using binary recursion to calculate the Fibonacci numbers is the time spent re-calculating already calculated Fibonacci numbers. For example, when calculating f(40) using recursion, f(39) is calculated once,  f(35) is calculated 8 times, f(1) is calculated 102,334,155 times, and  f(0) is calculated 63,245,986 times. All up there is a total of 331,160,281 function calls. The calculation of f(40) actually takes an average of 900 milliseconds (on my MacBook Pro with a 2.9 GHz Intel Core i5).

This is an interesting analysis, rarely made in textbooks. Few textbooks discuss alternatives to binary recursion for Fibonacci. Indeed, the use of Fibonacci numbers to illustrate binary recursion is a good example of when not to use recursion.

For anyone interested in Fibonacci numbers, there is a whole journal available online, The Fibonacci Quarterly.

One thought on “Why calculating Fibonacci using binary recursion is just plain moronic

  1. tmcglinn says:

    I made a templated function for this situations, which first checks a cache for the given parameters and only otherwise does it execute the given function.

    https://github.com/TamaMcGlinn/FuncTest/blob/master/cached_function.hpp

    You still have to modify the recursive function, to only call the cached version of the function though:

    “`
    int fib(int n) {
    if (n < 2) return n;
    //return fib(n – 1) + fib(n – 2); // naieve recursive way, for reference
    return cached_function(n – 1) + cached_function(n – 2);
    }
    “`

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.