Recursion Part II: Fibonacci

Fibonacci sequence example

Image: Bored Panda

Let’s continue talking about recursion. Last week I confessed that it was one of the most difficult concepts for me to understand and gave an example of calculating factorial. As promised, this week we move on to more interesting examples of using recursion.

I doubt there are people in the civilized world who haven’t heard about the Fibonacci sequence and the Golden ratio. The fact that a pretty simple to calculate sequence of numbers govern everything in nature and art is truly mind-blowing, and that is why we care about it (remember, we cared about factorials because n! is a number of ways we can arrange n objects on a line).

Fibonacci sequence follows a simple rule: you start with 0 and 1 and calculate the following number by adding two preceding numbers together. As a result, you get something like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34… The actual mathematical formula is given by:

Essentially, that’s all we need to know to calculate the entire sequence, so the code shouldn’t be difficult as well:

def fibonacci(n):
 if n == 0:
  return 0
 elif n == 1:
  return 1
 else:
  return fibonacci(n-1) + fibonacci(n-2)

Of course, it would be smarter to simplify the if and elif statements, but we get the general idea:

def fib(n):
 if n in range(2):
  return n
 else:
  return fib(n-1) + fib(n-2)

This function can be used to either calculate the Nth number in the Fibonacci sequence (say, fib(5) — >5 ), or to generate the sequence of a certain length:

list(fib(i) for i in range(10))

But how exactly does the function know what to return if we ask it to return fib(n-1)+fib(n-2) if it doesn’t even know what fib is in case if a given number is greater than 2? It needs some self-awareness, after all! Well, just as in the factorial example, it needs to take small steps to calculate numbers in the parenthesis, (n-1) and (n-2), until it hits the first if-statement and reaches 1. The function may not know what fib(n) is, but given a number n it can certainly calculate the two preceding numbers. Here is an illustration of the logic process when a given n is equal to 5. On each node the function keeps ‘asking itself’ wether or not is is equal to 1 until the answer is yes:

Once the calculations result in an actual number, the only thing that’s left to do is to add them up, because this is essentially all we need!

Note: discussion of Fibonacci numbers can be endless and the problem can be looked at from many many different points of view, but I am just using this example to talk more about the concept of recursion and how I wrapped my brain around it. Next week I’ll talk about Towers of Hanoi and how the game can be won by counting in binary.

Resources:

SciShow

Numberphile