Third chapter of my study series on Grokking Algorithms by Aditya Y. Bhargava.

If you’ve been following along, I’ve already summarized the previous chapters 👀, go back if you have any questions:

• Chapter 1 - Introduction and Binary Search
• Chapter 2 - Arrays, Linked Lists and Selection Sort
• Chapter 3 - Recursion 📍 you are here

Hey everyone! Another little summary of our beloved book 😊

This was one of the chapters that did the most to take away the feeling that programming is magic. Ready to understand recursion and stacks without fear?

In this chapter, the author explains the concept and use of recursion in a simple way, breaking it down into base case and recursive case. He suggests that at least once, you trace through a recursive function with pen and paper, step by step that’s how you truly understand how it works.

Recursion

It’s the technique where a function calls itself to solve a problem, breaking it down into smaller subproblems. Because a recursive function calls itself, it’s easy to write it incorrectly and end up in an infinite loop. For recursion to work correctly, it must have a base case to stop the calls, and a recursive case that moves the problem closer to the final solution.

How recursion works

Before showing an example, let’s understand how it works.

1. Base case: defines when the function should stop calling itself. Without it, the recursion would go on forever and cause an error.

2. Recursive case: the part where the function calls itself again, getting one step closer to the final solution each time.

A classic example is calculating the factorial of a number:

def factorial(n):
    if n == 0 or n == 1:  # Base Case
        return 1
    else:  # Recursive Case
        return n * factorial(n - 1)

print(factorial(5))  # Output: 120

In this example:

• Base Case: n is 0 or 1, so the factorial is 1
• Recursive Case: if n is greater than 1, the factorial is n * factorial(n-1)

See how it’s almost poetic each number calls the next until 1 says “okay, stop, now go back.” Then the multiplication happens on the way back up.

Stack

Imagine you’re hosting a barbecue for your friends. You have a to-do list in the form of a stack of sticky notes. When you add an item, it goes on top of the stack. When you read an item, you only read the one on top and it gets removed. So your to-do list has only two actions: push (add) and pop (remove and read).

This data structure is called a stack. It’s a simple structure and we use it all the time without even realizing it.

The call stack

Every time a function is called, the computer needs to “remember” where it left off so it can continue later. This temporary memory is organized in a call stack.

Here’s how it works:

• With each new function call, the computer pushes information about that execution (like parameters and local variables) onto the stack.
• When the function finishes, the computer pops that data and returns to the previous point.

The book’s metaphor is great think of a stack of plates in the kitchen. You can only grab (or remove) the plate on top. Functions work the same way: the last one in is the first one out (LIFO: Last In, First Out).

We can visualize this with a simple Python example:

def greet(name):
    print("Hi,", name)
    farewell()

def farewell():
    print("Goodbye!")

greet("Ana")

Execution order on the stack:

1. greet("Ana") is called → pushed onto the stack.
2. Inside it, farewell() is called → sits on top.
3. farewell() runs and is popped from the stack.
4. greet("Ana") finishes and is popped from the stack.

Everything organized, one plate at a time.

This example already shows that it’s not just recursion that uses a stack any function does. The difference is that recursion forces the stack to grow much faster.

The call stack with recursion

With recursion, the stack can grow quite a bit, because the function keeps calling itself until it hits the base case.

Simplified example with factorial(3):

The program calls factorial(3)
    - pushes factorial(3)

To solve it, it needs factorial(2)
    - pushes factorial(2)

To solve that, it needs factorial(1)
    - pushes factorial(1)

factorial(1) hits the base case and returns 1
    - pops factorial(1)

Now factorial(2) can calculate 2 × 1 = 2
    - pops factorial(2)

Finally, factorial(3) calculates 3 × 2 = 6
    - pops factorial(3)

In the end, each call can only finish after the smaller one returns. That’s why defining the base case well is so important without it, the function never stops stacking calls and eventually crashes the memory (stack overflow).

That “stack overflow” is literally where the Stack Overflow website got its name.

When I first saw this process, it felt like some kind of magic as if the computer just knew where to go back to.

That’s when I realized that understanding programming is a lot about demystifying things. It’s not a gift, it’s not genius it’s just pushing and popping, calmly. Now whenever I see a recursive function, I try to picture that stack running in the background. It brings clarity and turns “I wasn’t born for this / I’ll never get this” into “hehe, that’s actually cool” 😎

So next time you get lost in a recursive piece of code breathe. Draw the stack, follow the steps, and remember: it’s not magic, it’s just practice!!!

Fun facts 💡

1. A very common recursion outside of programming: Russian dolls (matryoshkas). Each doll holds another inside it, until the smallest one (the base case) holds nothing at all.
2. Some languages apply tail call optimization, which reuses stack frames to avoid memory overflow in very deeply recursive functions. Python, however, does not do this.
3. The call stack is invisible most of the time but you’ve already seen it working: when Python shows a traceback (that error full of arrows, showing which function the execution was in).
4. Many recursive functions can be rewritten iteratively (using for or while loops). This avoids the risk of stack overflow in cases with very deep calls.
5. To understand recursion, you must first understand recursion. 😅

Recommended exercises 👩🏻‍💻💞

Here are some practical challenges to reinforce what you learned:

LeetCode

• Merge Two Sorted Lists can be solved recursively, treating the base case as when one list reaches the end.
• Climbing Stairs a classic recursion + optimization problem (similar to Fibonacci).

Exercism

• Flatten Array receives a list that may contain sublists and needs to return everything “flattened” into a single list.
• Recursion with Python reinforces the concept and includes the “Luhn” exercise, which works well with a recursive approach.

Extra challenge

• Write a recursive function that walks through folders and files on your computer (or just a simulated nested list). That’s literally how many file systems work.

I hope you enjoyed the content! ✨💕

If you have any exercise suggestions or improvements for the explanation, let me know 🫂🌻

Compartilhar: