Recursion

Loops aren’t the only way to express iteration, lets look at another approach.

The classic example is Fibonacci:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

non-recursive calls are called Base cases, a recursive call chain which always results in a call to a base case will always terminate.

Worked Example

If we wanted to calculate F(5)

F(5) = F(4) + F(3)
    F(4) = F(3) + F(2)
        F(3) = F(2) + F(1)
        
            F(2) = F(1) + F(0)
            F(2) = 1 + 0 = 1
                F(1) = 1
                F(0) = 0
            
            F(1) = 1
            
        F(3) = F(2) + F(1)
        F(3) = 1 + 1
        F(3) = 3
    
    F(4) = F(3) + F(2)
    F(4) = 2 + 1 
    F(4) = 3

F(5) = F(4) + F(3)
F(5) = 3 + 2
F(5) = 5

---

Last updated 0001-01-01