Understanding Recursion By Dropping It Eventually

Recursion, a junior developer’s nightmare!

As hard as it is for a human, it is similarly taxing to the computer as well.

When you write a recursive function, the computer has to maintain a call stack that keeps track of all the recursive calls’ execution context.

This makes recursion a memory-intensive task.

If you call a recursive function sufficiently multiple times, the computer can get overwhelmed and throw a Stack Overflow error!

That’s a way for the computer to panic and shout that it cannot keep track of the execution contexts anymore.

Things are flowing out of the call stack!

To understand this better, let’s take a problem and solve it using recursion and then our plain old iteration.

Problem Statement

Find the Nth Fibonacci number

What Are Fibonacci Numbers?

In mathematics, Fibonacci numbers form a sequence where each number is the sum of the preceding ones.

Solution With Recursion

Given a number n, we need to write a function that returns the n th Fibonacci number.

Recursion offers an easy and elegant solution to this problem.

To go on with the recursion solution, we need to consider:

• Base case(s)
• Recursive step to reach the base case

In Python, the function with base cases can be written as follows.

def findNthFibonacci(n):
    #Base Case 1
    if n < = 0: 
        raise ValueError("n should be more than 0")

    #Base Case 2
    elif n == 1:
        return 0

    #Base Case 3
    elif n == 2:
        return 1

The function findNthFibonacciwill immediately return to these if n ≤ 2

Next, we need a recursive step that leads to a base case.

def findNthFibonacci(n):
    #Base Case 1
    if n < = 0: 
        raise ValueError("n should be more than 0")

    #Base Case 2
    elif n == 1:
        return 0

    #Base Case 3
    elif n == 2:
        return 1

    #Recursive Step
    else:
        return findNthFibonacci(n-1) + findNthFibonacci(n-2)

Pretty elegant, isn’t it?

Unfortunately, when we dig deep, we find that this algorithm runs in:

• Time complexity of O (2^n) because the recursive step calls the function itself twice in each step
• Space complexity of O (n) because the recursive step stores the execution contexts in a call stack that will grow proportionately to n

How to optimize the solution?

Optimization

We see that we are repeating steps many times when we solve this problem with the above solution.

What happens if we store the result of the computations in a data structure that we can access values from in constant time?

Sure!

Method 1: Memoization

Memoization is the process of storing computation results in temporary memory (cache) and retrieving it the next time it’s required instead of computing it again.

For this, we will create a dictionary /hash map called memo that will store the 1st and 2nd Fibonacci numbers by default.

If we find the value of nth Fibonacci number in this dictionary, we will return it (in constant time).

Else, we will compute the result and add it to this dictionary before we return it.

def findNthFibonacci(n, memo:{1:0, 2:1}):

    if n in memo:
        return memo[n]

    else:
        memo[n] = findNthFibonacci(n-1, memo) + findNthFibonacci(n-2, memo)
        return memo[n]

This algorithm runs in:

• Time complexity of O (n) because the recursive step calculates each Fibonacci number once and then stores it in the dictionary memo
• Space complexity of O (n) because the recursive step stores each Fibonacci number in the dictionary memothat will grow proportionately to n . Also, the recursive step stores the execution contexts in a call stack that will grow proportionately to n .

Method 2: Iteration

To make our solution the most efficient, we will return back to our plain old Iteration.

Let’s write an iterative solution to the problem.

def findNthFibonacci(n):
    firstFib, secondFib = 0, 1

    for _ in range(n-1):
        firstFib, secondFib = secondFib, (firstFib + secondFib)
    
    return firstFib

This solution stores the first and second Fibonacci numbers in two local variables firstFib and secondFibinside the function.

We will loop n-1 times and will keep changing the values of firstFib and secondFib till we reach the n th Fibonacci number stored in firstFib .

Hope this makes understanding Recursion easy for you!

Thanks for reading!

If you found this article useful, you can check out my other articles here: