Generating a Fibonacci Number
Fibonacci was Leonardo of Pisa, In 1202 he wrote a book called Liber Abaci.(I wonder if Liberace knew this). In this book he studied the series of numbers where each number is the sum of the two preceding it. For some reason I've found this sequence interesting ever since I was in junior high.
In job interviews it seems to be standard to ask questions about the Fibonacci sequence. It's usually presented as an example of recursion and the question asked is "How would you generate this sequence non-recursively?"
I ran a comparison generating the first 51 numbers in the sequence using both the iterative and recursive algorithms. The results can be found here.
I find the results interesting because, contrary to intuition, the program seems to have calculated the first 10 fibonacci numbers faster using the recursive algorithm.
By the 51st Fibonacci number, Fibonacci(50), order is restored to the universe. The recursive algorithm took about 6 minutes vs. 3⁄1000 of a second for the iterative algorithm.
Perhaps the machine (a Macbook Pro) optimizes the first few recursive calls. Or maybe there was experimental error.
I've put further ruminations on the Fibonacci sequence in the