Scheme For Enlightenment Part Seven - A Little Fib

The Fibonacci function is another one of those defined recursively. The Fibonacci(0) is 0 and the Fibonacci(1) is 1. The Fibonacci(x) is Fibonacci(x - 1) + Fibonacci(x - 2) for integers more than 1. The Scheme implementation is straight forward.

(define (fib x)
  (if (= x 0)
      0
      (if (= x 1)
          1
          (+ (fib (- x 1)) (fib (- x 2))))))

Since there are two calls to itself, followed by addition, this is not tail recursive friendly. Also, since there are two calls to itself, and each of those calls calls itself, the number of total calls goes up faster than x. The time taken for fib(x + 1) is about 1.6 times as much as fib(x). Large x takes exponentially longer than smaller x.

Since addition, rather than multiplication is used, the answers don't become absurdly huge too quickly. The answers can be stored in a 32 bit unsigned integer for x up to 47, and a 64 bit integer can cope with the answers up to 93. With this in mind, a C version is more practical.

unsigned long long
fib(int x)
{
  if (x == 0) {
    return 0;
  }
  if (x == 1) {
    return 1;
  }
  return (fib(x - 1) + fib(x - 2));
}

This returns the same numbers for up to 93. However, fib(93) will take thousands of years to run. Yet, at this point, the Guile version and the C version can be used as a sort of benchmark. It turns out that the C version is about 100 times faster that Guile for the same x for this benchmark. Neither version requires huge amounts of memory. The call stack doesn't get very deep, nor does much go onto the stack.

The tail recursive friendly version of this function is instructive. A helper function is defined which does all the work. It is passed two additional parameters which allow it to accumulate intermediate answers. They are passed initial constant values to get it going. There's only one call to itself, and it really is the last thing the function does, so it's properly tail recursive. It produces the exact same answers as the above functions.

(define (fib-helper a b x)
    (if (= x 0)
        b
        (fib-helper (+ a b) a (- x 1))))

(define (fib x)
    (fib-helper 1 0 x))

One might expect a small constant speed improvement due to recursion. But this function isn't just a little faster, like four times faster. This function is amazingly fast. For example, (fib 93) requires an essentially unmeasurably small amount of time. That's much less than thousands of years. So what's going on?

The key is that the helper only calls itself once. For a given x, it calls itself that many times. It doesn't have exponential time, it has linear time. Well, it's not exactly linear. As x gets larger, the arithmetic takes longer because the numbers are bigger. Even so, (fib 1000) spits out all 209 digits basically without pause. This algorithm is so much better, that the original recursive version should just be scrapped. More than one Scheme tutorial demonstrates the slow recursive Fibonacci function. One made a cryptic remark that this algorithm computes Fibonacci numbers slowly. This new version was presented as tail recursive friendly, but totally failed to mention that it is a wildly different algorithm. As a point of fact, i have no idea why this function should return the same answers as the original.

This version is so much faster that a C version is pointless. Recall that (fib 93) with this version is essentially instant. The C version might be 100 times faster, but that's still instant, for a total time savings of essentially zero, best case. Actually, a best C version wouldn't do any calculation at all. If one is limited to 64 bit integers, the function can only answer 94 questions (starting with zero). The fastest version would have a small table of answers and just return one of them.