Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 149 ยท Functions

Recursion

Learn recursion in Python step by step - base cases, recursive cases, the call stack, RecursionError, and speeding up recursive functions with functools.cache.

A recursive function is one that calls itself. That sounds like a recipe for an endless loop, but it's a powerful way to solve problems that contain smaller copies of themselves: a folder holds folders, a comment thread holds replies that hold replies, and the factorial of 5 is just 5 times the factorial of 4.

In this lesson you'll learn how to write recursive functions that stop, how Python keeps track of the calls, what happens when recursion goes too deep, and how caching with functools.cache turns a painfully slow recursive function into a fast one.

Two essential parts

Every working recursive function has two parts:

  • A base case: an input simple enough to answer directly, without calling the function again.
  • A recursive case: a step that reduces the problem and calls the function on the smaller version.

Here's a countdown written both ways, with a loop and with recursion:

Python Countdown, recursively

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each call handles one number and hands the rest of the work to a call with n - 1. Eventually n reaches 0, the base case runs, and the calls stop. If you forget the base case, or the recursive case doesn't move toward it, the function never stops on its own.

Returning values from recursion

Recursion becomes really useful when each call returns a result that the caller combines with its own work. The factorial of n (written n!) is the product 1 ร— 2 ร— โ€ฆ ร— n, which you can define in terms of itself: n! = n ร— (n โˆ’ 1)!, with 0! = 1.

Python Factorial

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python's integers have no size limit, so factorial(20) and much larger values come out exact.

The call stack

How does Python keep track of all those half-finished calls? Each time a function is called, Python pushes a frame onto the call stack. The frame holds that call's local variables, including its own n. When a call returns, its frame is popped and the caller continues where it left off.

Adding a depth parameter lets you watch the stack grow and shrink:

Python Tracing the calls

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The calls go down until they reach the base case, then the results come back up: 1, then 2 ร— 1, then 3 ร— 2, then 4 ร— 6. Each frame has its own separate n, which is why they don't overwrite each other.

Recursion on nested data

Recursion is at its best when the data itself is nested to an unknown depth. A loop can walk a flat list, but a list that contains lists that contain lists is naturally handled by a function that calls itself for each inner list.

Python Nested structures

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In show_tree, the base case is hidden: an empty dictionary has nothing to loop over, so the call simply ends. That's common in recursive code over trees.

Recursion limits

Every frame uses memory, so Python caps how deep the stack can grow. The default limit is 1,000 frames (some environments choose a different value, so the example below prints it). Going past it raises RecursionError, which protects your program from crashing outright.

Python RecursionError

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You'll see RecursionError in two situations: a missing or unreachable base case (a bug), or a correct function whose input is simply too deep, like summing 5,000 numbers one frame at a time.

You can raise the limit with sys.setrecursionlimit(), but treat that as a last resort. Unlike some languages, Python doesn't optimize tail calls, so deep recursion stays expensive. If a problem only ever recurses in a straight line (like sum_to), a loop is the better tool:

Python
def sum_to(n: int) -> int:
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

Keep recursion for problems that branch, such as trees, nested data, and divide-and-conquer algorithms, where the depth stays small even when the amount of data is large.

Tail recursion and why Python does not optimize it

A call is a tail call when it is the very last thing a function does, with nothing left to compute afterwards. A function built that way is tail recursive; otherwise it is non-tail recursive, because the caller still has work to do once the inner call returns (like the n * in the usual factorial). Languages such as Scheme reuse the same stack frame for tail calls, so depth never grows. Python deliberately does not, which keeps tracebacks complete. Rewriting a function in tail form therefore does not save stack space in Python. Convert it to a loop instead, and carry the running result in a variable (the accumulator).

Python Non-tail, tail form and loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Memoization with functools.cache

Some recursive functions repeat the same work again and again. The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, โ€ฆ), where each number is the sum of the two before it, is the classic example. A direct recursive version calls fib(n - 1) and fib(n - 2), and each of those calls both again, so the number of calls explodes.

Memoization fixes this by remembering results: the first time fib(30) is computed, store it; next time, return the stored answer. The standard library does this for you with the functools.cache decorator (you'll learn how decorators work in Decorators):

Python Caching recursive results

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The uncached version makes about 150,000 calls for fib(24); the cached one computes each value exactly once. cache_info() shows the hits (answers reused) and misses (answers computed).

A few rules for caching:

  • Arguments must be hashable (numbers, strings, tuples), because they become dictionary keys. Lists and dicts won't work.
  • Only cache pure functions: the same arguments must always give the same result, with no side effects you rely on.
  • @cache keeps every result forever. For long-running programs, @lru_cache(maxsize=1000) keeps only the most recently used results.

Tip: Caching doesn't remove the depth limit. On an empty cache, fib(5000) still recurses 5,000 levels down before any result is stored, so it raises RecursionError. Warming the cache in steps (fib(500), fib(1000), โ€ฆ) or switching to a loop avoids that.

Thinking recursively

When you write a recursive function, don't try to trace every call in your head. Instead:

  1. Handle the base case and make sure it's correct.
  2. Trust that the recursive call returns the right answer for the smaller input.
  3. Use that answer to build the result for the current input.

For example, to reverse a string: an empty string reversed is itself (base case); otherwise, the reverse is "the reverse of everything after the first character, plus the first character".

Python
def reverse(text: str) -> str:
    if text == "":
        return ""
    return reverse(text[1:]) + text[0]

In real code you'd write text[::-1] (see Slicing), but practicing on small problems like this builds the habit of trusting the recursion.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the purpose of a base case?

    Without a reachable base case, the function keeps calling itself until Python raises RecursionError.
  2. 2. What happens when a recursive function goes about 1,000 calls deep by default?

    Python limits stack depth (see sys.getrecursionlimit()) and raises RecursionError instead of crashing. It does not perform tail-call optimization.
  3. 3. Why does @cache make a recursive Fibonacci function so much faster?

    Memoization reuses earlier answers, turning an exponential number of calls into a linear one.
  4. 4. Which function could NOT be decorated with @cache as written?

    Cached arguments must be hashable. A list isn't, so calling it raises TypeError. Pass a tuple instead.
  5. 5. For which task is recursion the most natural fit?

    Recursion fits branching, nested data. Long straight-line repetition is better as a loop, both for clarity and to avoid the depth limit.

Summary

  • A recursive function calls itself. It needs a base case that stops, and a recursive case that moves toward it.
  • Each call gets its own frame on the call stack with its own local variables; results flow back up as calls return.
  • Recursion shines on nested, branching data such as trees, nested lists and folder structures.
  • Python limits depth to about 1,000 frames and raises RecursionError beyond that. There's no tail-call optimization, so use loops for long, straight-line repetition.
  • functools.cache (or lru_cache) memoizes results of pure functions with hashable arguments, which can make repeated-work recursion dramatically faster.

Next: Higher-Order Functions, where functions take other functions as arguments and return them as results.