Recursion

You have probably heard the word recursion before and maybe it felt confusing or magical. It is actually one of the most elegant ideas in programming once it clicks - and this guide is going to make it click.

What Even Is Recursion?

Okay, simple version: recursion is when a function calls itself.

That is it. A function that, at some point, calls itself again.

Here is a funny real-life example. When you search “recursion” on Google, it used to say:

Did you mean: recursion

Clicking that link takes you back to the same page. That is the joke - it loops back to itself. That is recursion.

In code, recursion is useful when you have a problem that looks exactly like a smaller version of itself. Instead of writing a long loop, you just say “hey, solve the smaller version of this, and I will handle the rest.”

Tip

Think of recursion like a set of Russian nesting dolls. Each doll contains a smaller version of itself, and you keep opening them until you hit the tiny solid one at the center that cannot be opened anymore. That tiny one is your base case.

The Two Rules Every Recursive Function Must Follow

Every single recursive function in the world needs exactly two things:

Rule 1: A base case

This is the “stop” condition. Without it, the function calls itself forever and your program crashes. Think of it like the bottom rung of a ladder - you need something to land on.

Rule 2: A recursive case

This is where the function actually calls itself, but with a smaller or simpler version of the problem. You always need to be moving toward the base case, not away from it.

Caution

If you forget the base case, you will get a stack overflow error. That means the program tried to make too many function calls and ran out of memory. It is like an endless loop but worse.

Your First Recursive Function

Let us start with something super simple - printing numbers from 1 to N.

def print_numbers(n):
    if n == 0:          # Base case - stop here
        return
    print_numbers(n - 1)  # Recursive call with smaller input
    print(n)

What happens when you call print_numbers(3)?

print_numbers(3)
  └── print_numbers(2)
        └── print_numbers(1)
              └── print_numbers(0)  -> hits base case, stops
              -> prints 1
        -> prints 2
  -> prints 3

Output: 1 2 3

Notice something important: the printing happens on the way back up, not on the way down. The function goes all the way to n = 0, then comes back and prints. This “going in and coming back out” behavior is core to how recursion works.

The Call Stack - What Is Actually Happening

Every time your program calls a function, it puts that function on something called the call stack. Think of it like a stack of plates at a buffet - you add plates to the top and take from the top.

When you call print_numbers(3):

1. print_numbers(3) gets added to the stack
2. It calls print_numbers(2), which gets added on top
3. That calls print_numbers(1), added on top
4. That calls print_numbers(0), added on top
5. print_numbers(0) hits the base case and returns - it gets removed from the stack
6. Now print_numbers(1) can finish - it prints 1, gets removed
7. print_numbers(2) finishes - prints 2, gets removed
8. print_numbers(3) finishes - prints 3, gets removed

The stack grows while going in, and shrinks while coming back out. Stack overflow happens when the stack grows too large - usually because the base case is missing.

A Classic Example: Factorial

You have probably seen factorial in math class. The factorial of 5 (written 5!) means 5 × 4 × 3 × 2 × 1 = 120.

Notice how 5! is really just 5 × 4!. And 4! is 4 × 3!. It keeps shrinking until you get to 1! = 1 (or 0! = 1). That is a perfect fit for recursion.

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

Let us trace through factorial(4):

factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1 * factorial(0)
= 4 * 3 * 2 * 1 * 1
= 24

Each call waits for the one below it to finish. Once factorial(0) returns 1, the values multiply all the way back up.

How to Think About Recursive Problems

Here is the honest truth: most people try to trace through every single recursive call in their head and get lost. You do not need to do that.

The trick is called the “just trust it” method, and it works like this:

1. Assume the recursive call already works correctly - pretend you have a magic helper function that solves the smaller version perfectly.

2. Write the base case - what is the simplest possible input where you can answer without any help?

3. Write the recursive case - given that your helper works on smaller inputs, how do you combine its answer with the current step?

4. Test on a tiny example - just 2 or 3 steps, not the whole thing.

For factorial: “Assume factorial(n-1) gives me the right answer for n-1. Then factorial(n) is just n * factorial(n-1).” Done. You do not need to trace all 10 levels.

More Beginner Examples

Sum of an Array

def array_sum(arr, i=0):
    if i == len(arr):    # Base case - no more elements
        return 0
    return arr[i] + array_sum(arr, i + 1)

Think of it as: “The sum of this array is the first element plus the sum of the rest.”

Check if a String Is a Palindrome

A palindrome reads the same forwards and backwards (“racecar”, “madam”).

def is_palindrome(s, left, right):
    if left >= right:          # Base case - checked all pairs
        return True
    if s[left] != s[right]:    # Characters do not match - not a palindrome
        return False
    return is_palindrome(s, left + 1, right - 1)

You check the outermost characters first, then move inward, one pair at a time.

Print Array in Reverse

def print_reverse(arr, i):
    if i == len(arr):
        return
    print_reverse(arr, i + 1)  # Go to the end first
    print(arr[i])               # Print on the way back

By going to the end before printing, you print in reverse order - same trick as the first example.

Two Recursive Calls: Fibonacci

Fibonacci is the sequence 0, 1, 1, 2, 3, 5, 8, 13... where each number is the sum of the two before it.

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

This is called binary recursion because there are two recursive calls. Each call spawns two more calls, which each spawn two more… it looks like a tree.

Caution

The Fibonacci code above works but is very slow for large n. fib(50) would make billions of function calls. This is the kind of problem that Dynamic Programming (DP) is designed to fix - it remembers previous answers so it does not repeat work. But for understanding recursion, this example is perfect.

Recursion Trees - Visualizing What Happens

For problems with multiple recursive calls, drawing a tree helps. For fib(4):

                fib(4)
              /        \
          fib(3)        fib(2)
          /    \        /    \
       fib(2) fib(1) fib(1) fib(0)
       /    \
    fib(1) fib(0)

Each level doubles the number of calls - this is O(2ⁿ) time complexity, which is why it gets slow fast.

Time and Space Complexity

How do you measure how expensive a recursive function is?

Time complexity - count the number of function calls:

• If a function calls itself once with n-1 -> O(n) (linear)
• If it calls itself twice like Fibonacci -> O(2ⁿ) (exponential - very slow)

Space complexity - how deep does the call stack get?

• Each function call takes up memory on the stack
• A chain of n calls uses O(n) space

factorial(1000)  # Stack goes 1000 levels deep -> O(n) space

Types of Recursion (Interview Vocabulary)

You do not need to memorize these, but knowing the names helps when reading about recursion:

Type	What It Means	Example
Tail recursion	The recursive call is the very last thing the function does	tail_factorial(n, acc)
Head recursion	The recursive call happens before any other work	Work happens on the way back up
Linear recursion	Only one recursive call per function	Factorial, array sum
Binary recursion	Two recursive calls per function	Fibonacci, subsequences

Note

Python does not optimize tail recursion. Some languages like Haskell or Scheme do (it lets them avoid stack overflow for deep recursion). In Python, a very deep recursion will crash regardless of whether it is tail recursive.

Backtracking - Recursion With an Undo Button

Backtracking is a more advanced use of recursion. The idea: try something, explore the options it opens up, then undo it and try something else.

It follows a pattern called choose -> explore -> unchoose.

Here is how you would generate all permutations of a list:

def permute(nums, path, used):
    if len(path) == len(nums):
        print(path)
        return

    for i in range(len(nums)):
        if used[i]:
            continue

        used[i] = True               # Choose
        permute(nums, path + [nums[i]], used)   # Explore
        used[i] = False              # Unchoose (backtrack)

The “unchoose” step is what makes backtracking special - you put the world back to how it was before, then try a different path. It is like exploring a maze: you try one corridor, hit a dead end, and go back to the fork to try the next one.

Generating Subsequences (Very Common Interview Pattern)

A subsequence is any subset of characters in order - for the string "ab", the subsequences are "", "a", "b", "ab".

def subsequences(s, i, current):
    if i == len(s):
        print(current)
        return

    subsequences(s, i + 1, current)           # exclude current character
    subsequences(s, i + 1, current + s[i])    # include current character

At each position, you make a binary choice: include or exclude. This creates a tree with 2ⁿ leaves - one for each possible subsequence.

Recursion vs Loops - When to Use Which

Both recursion and loops can repeat work, but they shine in different situations:

	Recursion	Loops
Code clarity	Very readable for tree/graph problems	Clear for simple repetition
Memory	Uses call stack (can overflow)	Constant memory
Risk	Stack overflow if base case is wrong	Infinite loop if condition is wrong
Best for	Trees, graphs, backtracking, divide & conquer	Simple counting, array scanning

Tip

A good rule of thumb: if your problem involves a tree, a graph, or “try all possibilities”, reach for recursion. If you are just counting or scanning through a list in order, a loop is simpler and faster.

When NOT to Use Recursion

Recursion is powerful but not always the right tool:

• When the input is huge (like n > 100,000) - the call stack will overflow
• When a simple loop does the job - no need to overcomplicate it
• In Python for performance-critical code - Python’s function call overhead is high

Python’s default recursion limit is 1000 calls. You can raise it with sys.setrecursionlimit(), but that is usually a sign you should rethink your approach.

Common Mistakes (And How to Avoid Them)

Forgetting the base case - your function will run until Python throws a RecursionError. Always write the base case first.

Wrong base condition - for example, using if n == 1 when n could be 0 or negative. Make sure your base case actually covers the smallest valid input.

Not making the problem smaller - if you call recursion(n) and pass the same n to the next call, you go in circles forever. Every recursive call must move closer to the base case.

Accidentally modifying shared data - if multiple calls share the same list or dictionary and one modifies it, things get confusing fast. Use copies or pass indices instead.

The 4 Questions to Ask Before Writing Any Recursive Function

Before you write a single line of code, answer these four questions:

1. What is the smallest input where I know the answer without thinking? -> That is your base case.
2. How does the full problem break down into a smaller version of itself? -> That is your recursive case.
3. What work happens before the recursive call vs after? -> This decides the behavior.
4. How many recursive calls does each step make? -> This tells you the time complexity.

Quick Reference

Base Case

The stopping condition. Every recursive function needs one. Write it first. Without it, you get infinite recursion and a crash.

Recursive Case

Where the function calls itself with a smaller input. You must always be moving toward the base case - never away from it.

Call Stack

Each function call gets stacked in memory. The stack unwinds when the base case is hit. Too many calls = stack overflow.

Trust the Recursion

Assume the recursive call works perfectly on smaller inputs. Focus on what your current call needs to do with that result.

Binary Recursion

Two recursive calls per function. Creates a tree of calls. Used for subsequences, Fibonacci, and many backtracking problems.

Backtracking

Choose something, explore all paths from there, then undo and try the next option. Used for permutations, mazes, puzzles.

Summary

The Core Idea

• Recursion is a function calling itself on a smaller version of the same problem
• Every recursive function needs a base case (stop) and a recursive case (continue)
• The call stack stores each active function call - too many causes stack overflow
• Trust that the recursive call works, focus only on what the current call does

Classic Patterns

• Factorial / Array sum - simple linear recursion, O(n)
• Fibonacci - binary recursion, O(2ⁿ) - slow without memoization
• Palindrome check - two pointers moving inward recursively
• Subsequences - include/exclude at each step, 2ⁿ combinations
• Backtracking - choose, explore, unchoose - for permutations and puzzles

Interview Tips

• Write the base case before the recursive case, always
• Draw the recursion tree for binary recursion problems
• Count function calls to find time complexity
• Stack depth = space complexity
• For Python: recursion limit is 1000, so avoid deep recursion on large inputs
• When you see trees, graphs, or “all possibilities” - think recursion