Fibonacci | Recursively or Not?

You’re probably all aware of the Fibonacci number sequence. Starting with 0 and 1, the next number is determined by the sum of the previous two numbers, so the sequence begins:

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

This is a mathematical concept, and it is defined by a “recurrence relation” (that’s a fancy way of saying that each number (or ‘term’) is generated from a previously calculated value), of:

Fn = Fn-1 + Fn-2

with “seed” or starting values of:

F0 = 0 and F1 = 1.

So, as you can imagine, this seems to lend itself nicely to programmatic recursion. Here’s a little program that will give you the 40th number in the Fibonacci sequence, using recursion:

Read more