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: