Recursion Cheat Sheet

5 min readJan 22, 2024

Hello, it’s me with yet another update to share about my journey in strengthening my CS background. In this blog, I will share about my recent learnings on recursion.

The following summary is based on a Youtube playlist on Recursion created by the incredibly talented Harsha Suryanarayana. I hope you find it helpful and, as always, feel free to export and reference the cheat sheet I have created as needed.

What is recursion?

Recursion: a concept where a function calls itself to solve a problem

Principles of Recursion:

Base case: defines the smallest instance of a problem and is essential to prevent infinite calling and ensure termination.
Recursive case: manipulates the problem to approach base case; involves calling itself to advance towards a solution.

Matryoshka Doll

A coworker of mine shared the following recursion analogy. Imagine a set of Matryoshka Dolls, where each doll contains a smaller doll inside. The process of opening each doll corresponds to the recursive nature of a function calling itself.

Outer Doll (Initial Problem): the largest doll represents the initial problem you want to solve.
Opening the Doll (Recursive Call): when you open a doll, you find a smaller doll inside, symbolizing a recursive call to a smaller instance of the problem.
Smallest Doll (Base Case): the smallest doll is the base case, representing the simplest form of the problem that doesn’t need further decomposition.
Closing the Doll (Returning): Once the innermost doll is reached, you close it and return, signifying the resolution of the smallest subproblem.
Repeating the Process: the process repeats as you open each doll, solve a smaller problem, and finally close it until you reach the outermost doll.

Why use Recursion?

Elegance and Readability: recursive solutions provide a more readable representation of problems, making code easier to read.

Natural Representation of Problems: recursive solutions mirror the natural structure of certain problems.

Divide and Conquer: recursion breaks down complex problems into simpler sub problems, making them more manageable.

Factorial — A Simple Recursion

Lets take a look at a simple recursion example. Solving for a factorial can be written as,

A recursive solution can be written,

def factorial(n):
    if n == 0:  # base case
        return 1
    else:  # recursive case
        return n * factorial(n - 1)

Stack Memory in Recursion

Recursion utilizes stack memory to manage function calls. Each recursive call adds a new stack frame to the top of the stack.

Continuing with our factorial example, the following illustrates how the stack memory is allocated.

When F(3) makes a recursive call for F(2), a new stack frame for F(2) is added to the top of F(3) and the execution of F(3) is temporarily paused. Similarly, when F(2) makes a recursive call for F(1), a new stack frame for F(1) is added to the top of F(2) and the execution of F(2) is temporarily paused.

The stack is a data structure with LIFO (last-in, first-out). This means that the last item to be placed will be the first to removed. When the execution of F(1) is complete, its stack frame will be popped from the stack and execution will resume for F(2) and so on.

Complexity Analysis of Recursive Programs

Time Complexity: measurement of how the time taken by the program grows as the input grows.

Space Complexity: measurement of how the memory consumed by the program grows with the input.

Factorial Complexity Analysis

Time Complexity (O(n)):

Each recursive call processes a single operation.
The number of recursive calls is directly proportional to the input n.
Time complexity grows linearly with the input size.

Space Complexity (O(n)):

Each recursive call adds a new stack frame to the call stack.
The maximum depth of the call stack is n.
Space complexity grows linearly with the input size.

Fibonacci Sequence — A Recursive Approach

Now lets take a look at a recursive approach to solving a fibonacci sequence problem. Solving for a fibonacci sequence can be written as,

A recursive solution can be written,

def fib(b):
    if n <= 1:  # base case
        return n
    else:  # recursive case
        return fib(n - 1) + fib(n - 2)

The recursion tree for this solution would look like,

Fibonacci Recursion Tree (Recursive Approach)

Pros:

Concise code.

Cons:

Exponential time complexity: O(2^n)
Redundant calculations. F(3) is calculated twice. F(2) is calculated 3 times!

Fibonacci Sequence — An Iteratice Approach

Now lets take a look at an iterative approach to solving a fibonacci sequence problem.

def fib(n):
    if n <= 1:
        return n
    f1, f2 = 0, 1
    for i in range(2, n):
        f = f1 + f2
        f1 = f2
        f2 = f
    return f

The recursion tree for this solution is as follows,

Fibonacci Recursion Tree (Iterative Approach)

Pros:

Linear time complexity: O(n)
No redundant calculations. Calculates each only once!

Cons:

Longer code.

Recursion with Memoization

Recursion with memoization: an optimization technique where the results of function calls are stored in memory and reused to avoid redundant computations.

Lets see how we can use recursion with memoization to solve for a fibonacci sequence,

def fib(n, memo={}):
    if n <= 1:  # base case
        return n

    if n not in memo:  # recursive case
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)

    return memo[n]

memo is a dictionary used to store already computed Fibonacci values.
Before making a recursive call, the function checks whether the value for the current n is already in memo
If yes, the value is retrieved from memo instead of recalculating it
Significantly reduces the time complexity and prevents redundant calculations