What you'll learn

  1. Quick answer
  2. Every recursive function has the same two parts
  3. Do not trace it in your head
  4. What actually happens, and the limit
  5. Fibonacci, and why the naive version is unusable
  6. When recursion is the right choice
  7. FAQ

Quick Answer

A recursive function calls itself on a smaller version of the problem and stops at a base case. Write the base case first. Do not try to trace every call in your head — assume the smaller call is already correct and check that your combining step is right.

Every recursive function has the same two parts

A base case that stops, and a recursive case that moves towards it. That is the whole structure.

def fact(n):
    if n <= 1:            # base case: stop here
        return 1
    return n * fact(n - 1)  # recursive case: smaller problem

print(fact(5))            # 120

Beginners usually write the recursive case first and then bolt on a base case when it crashes. Reverse that. Ask "what is the smallest input, and what is the answer for it?" first. For factorial that is 1. Once the stopping point exists, the recursive line usually writes itself.

Do not trace it in your head

This is the single biggest reason recursion feels hard. People try to follow every call down and back up, run out of working memory around the third level, and conclude they are bad at it.

Professionals do not do that. They use the recursive leap of faith: assume the smaller call already returns the correct answer, and check only that you combine it correctly.

For fact(5), assume fact(4) correctly returns 24. Is 5 * 24 the right answer for fact(5)? Yes. Done — the function is correct, and you never traced anything.

Verify three things and you can stop worrying: the base case is right, each call genuinely moves towards it, and the combining step is right.

What actually happens, and the limit

Each call is added to the call stack and stays there until it returns. Python caps that depth deliberately:

import sys
print(sys.getrecursionlimit())   # 1000

def bad(n):
    return bad(n + 1)            # no base case

bad(0)                           # RecursionError

The limit of 1000 exists to turn runaway recursion into a clean error rather than a crash. If you hit RecursionError, the problem is almost always a missing or unreachable base case — not a limit that needs raising. Raising the limit to hide a bug turns a clear error into a hard crash.

It also means recursion depth is bounded in Python. Recursing once per element over a list of 100,000 items will not work, even if the logic is correct.

Fibonacci, and why the naive version is unusable

Fibonacci is the standard second example, and it hides something important. The obvious version calls itself twice:

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

This recomputes the same values enormously many times — fib(30) makes over a million calls, and the work roughly doubles with each increment of n. It is correct and effectively unusable.

Remembering answers you have already computed fixes it completely:

def fib(n, memo={}):
    if n in memo: return memo[n]
    if n < 2: return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(30))    # 832040, instantly

That is memoisation, and it is the entry point to dynamic programming. The lesson generalises: when a recursive solution is slow, the cause is usually recomputing the same subproblem, not recursion itself.

One caution — the mutable default memo={} is shared across calls. Here that is intentional and helpful, but it is the same mechanism that causes bugs elsewhere; see OOP in Python for where it bites.

When recursion is the right choice

Recursion wins when the data is itself recursive — trees, nested folders, nested JSON, graphs. Walking a directory tree recursively is natural; doing it with a loop means managing your own stack, which is more code and more bugs.

For simple counting or iterating over a flat list, a loop is clearer and has no depth limit. "Can it be recursive" and "should it be" are different questions, and interviewers do ask the second one.

Recursive problems worth practising: tree traversal, permutations, binary search, and directory walking. Those four cover most of what appears in interviews — see the time complexity cheat sheet for how to reason about their cost.

Frequently Asked Questions

Why do I get RecursionError? Almost always a missing or unreachable base case, so the function never stops calling itself. Check that the base case exists and that every recursive call genuinely moves towards it. Raising the recursion limit hides the bug rather than fixing it.
Is recursion slower than a loop? In Python, usually yes, because each call has overhead and consumes stack space. Recursion is chosen for clarity on recursive data structures, not for speed. Where both are equally clear, prefer the loop.
What is the difference between recursion and iteration? Iteration repeats using a loop and constant stack space. Recursion repeats by calling itself, using stack space proportional to the depth. Any recursion can be rewritten iteratively, though for tree-shaped problems the iterative version is often much harder to read.
What is memoisation? Storing the result of a call so repeated calls with the same input return instantly. It turns exponential recursive solutions like naive Fibonacci into linear ones, and it is the basic idea behind dynamic programming.
Should I use recursion in interviews? Use it when the problem is naturally recursive, such as trees. Say why you chose it, and mention the depth limitation if the input could be large. Demonstrating that you considered the trade-off matters more than which one you pick.