Time Complexity of Recursive Algorithms

In this article, we’ll break down "time complexity" for recursive algorithms in a playful way: With Fun, Games, and Recursion Monsters 🧟!

Imagine you’re playing a game where you’re trapped in a giant cave. To escape, you must solve puzzles, one after another, but there’s a twist: Each puzzle leads to smaller puzzles inside it! This is recursion!

But how long will it take to solve all these puzzles? Will you escape the cave in time, or will you end up puzzling forever? This is where ”Time Complexity “ comes in to save your brain!

In this article, we’ll cover:

1. What recursion is.

2. How to figure out how long a recursive function takes.

3. Fun little mind games to understand time complexity.

4. Battling the Recursion Monster 🧟!

Ready? Bissmillaah!

---

Level 1: Understanding Recursion 🔃

What is Recursion?

Recursion happens when a function calls itself over and over until it solves the problem. Here's a simple example of recursion in python code 🐍:

def countdown(n):
    if n == 0:
        print("Boom!")
    else:
        print(n)
        countdown(n - 1)

When you call countdown(5), it goes:
5 → 4 → 3 → 2 → 1 → Boom!

In each step, the function does the same thing, calls itself, but with a smaller version of the problem (subtracting 1 from n).

PS: A stop condition needed to break from the recursive calls loop, else, we’ll be looping forever (memory leak, stack overflow!)

In the example above, this was our stop condition: if n == 0: print(‘Boom!”)

A Fun Visual:

Imagine you’re standing at the top of a staircase with n steps. With each recursive call, you walk down one step. The recursion ends when you reach the bottom (stop condition)!

---

Level 2: Facing the Recursion Monster 🧟 “Time Complexity”

Now, the fun part—how long does it take to run a recursive algorithm?

Let’s meet the Recursion Monster 🧟. Every time a function calls itself, the monster eats a "time token". Your goal is to figure out how many time tokens the monster will eat before the recursion stops. The big question is: How many steps does the recursion take?

Now that we meet the monster, let’s go and see when we’ll meet with it, and how to beat it if an encounter happens!

---

Level 3: Fun Recursion Puzzles 🧩️

Let’s play a game to see how long some recursive functions take.

🧩️Puzzle 1: The Countdown Puzzle

def countdown(n):
    if n == 0:
        print("Boom!")
    else:
        countdown(n - 1)

Question: How many calls does this recursive function make before printing Boom!?

💡Hint: Every call subtracts 1 from n.

Answer: It makes n calls before reaching 0. So, if n = 5, it calls itself 5 times, and if n = 100, it calls itself 100 times. Easy!

This function runs O(n) time (linear time).

🧩️Puzzle 2: The Famous Fibonacci Sequence

Now the Recursion Monster gets a little stronger! Consider the Fibonacci sequence, where each number is the sum of the two previous numbers:

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

Challenge: How many recursive calls does this function make for fibonacci(5)?

Time to think... 🧐

Answer:

• The function calls itself twice: once for fibonacci(n-1) and once for fibonacci(n-2).

• For every number, it does the same thing again... and again... and again.

It’s like a tree of recursive calls!

fibonacci(5)
│
├── fibonacci(4)
│   ├── fibonacci(3)
│   │   ├── fibonacci(2)
│   │   │   ├── fibonacci(1)
│   │   │   └── fibonacci(0)
│   │   └── fibonacci(1)
│   └── fibonacci(2)
│       ├── fibonacci(1)
│       └── fibonacci(0)
└── fibonacci(3)
    ├── fibonacci(2)
    │   ├── fibonacci(1)
    │   └── fibonacci(0)
    └── fibonacci(1)

If you calculate the number of calls manually, you’ll find out the time complexity is O(2^n). This is exponential time! The Recursion Monster just got huge, each level of recursion doubles the number of calls! Ruuuun 🏃‍♂️!!

PS: we notice that all ot of fuction calls with the same parameter value, got repeated! That’s really unefficient!

---

Level 4: Battling the Recursion Monster ⚔️ (And Winning, of course 😉)

Recursive algorithms can grow quickly in terms of time complexity. To kill the Recursion Monster, you can use techniques like memoization (not memorization, that’s me longs ago hahah).

Memoization Example:

Let’s make Fibonacci a bit more efficient:

// we pass the number + the hashmap that storesprevious calls results
// If you encouter a call with a param value that we already calculated it
// we use the stored result directly, without calculating again!!
def fibonacci_memo(n, memo={}):
    // checking if the param value has been calculated in the past
    if n in memo:
        // if found we return the result and quit
        return memo[n]
    // stop condition check (preventing endless loops)
    if n <= 1:
        return n
    // storing the new calculated result for future usage
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    // returning the result
    return memo[n]

Now, instead of recalculating Fibonacci numbers over and over, this version remembers them using a HashMap (constant time lookup). Memoization reduces the time complexity from O(2^n) to O(n). Boom! You’ve just defeated the Recursion Monster! 🐉

---

More Examples To Understand Time Complexity Cases

Here’s a fun mental picture of time complexity levels. Imagine, the higher you go, the more time you need to reach the top.

1. O(1) (Constant Time): You instantly jump to the answer. You’ve got a jetpack!

2. O(log n) (Logarithmic Time): You’re climbing a tower with magical stairs that disappear as you ascend. Each step halves the distance.

3. O(n) (Linear Time): You climb one step at a time, slow but steady.

4. O(n^2) (Quadratic Time): You’re walking through a maze where every step makes the maze bigger.

5. O(2^n) (Exponential Time): You’re trapped in a cave where every step doubles the number of monsters you have to fight! Run!!

---

You Win! 🏆🎉

By now, you’ve escaped the cave, solved the puzzles, and defeated the Recursion Monster. You’ve also learned how to handle recursive algorithms and calculate their time complexity.

Here’s a quick recap of what you collected :

1. Recursion is when a function calls itself.

2. Time complexity tells you how long a recursive algorithm takes.

3. Linear Recursion (like countdown) takes O(n) time.

4. Tree-like Recursion (like Fibonacci) can take O(2^n) time without memoization.

5. Memoization is a trick to speed up recursive algorithms from O(2^n) to O(n).

Now you’re ready to tackle even bigger challenges in algorithm land! Keep coding, and may the Recursion Monster never catch you 👾 haha!

🔔 Don't forget to subscribe to my blog and YouTube channel to stay updated with all the latest content, follow me on LinkedIn too, if you like to do so!