Skip to content
Tutorials Center
My learning

Topics

Lesson 60 of 225 ยท Recursion and Backtracking

Recursion

Learn recursion in Python from scratch: base case, recursive case, the call stack traced step by step, factorial, sum, power, reverse and the RecursionError limit.

A recursive function is a function that calls itself. That sounds like a trap, a dictionary entry that says "recursion: see recursion", but it works because every call is given a smaller version of the problem, and at some point the problem becomes so small that the answer is obvious. Recursion is the natural way to solve problems that are made of smaller copies of themselves: trees, nested folders, parentheses, puzzles, and almost every divide-and-conquer algorithm.

If you have never used recursion, do not worry. In this lesson you will build the idea from a real-life picture, learn the two parts every recursive function needs, watch the call stack work, write five classic functions, and learn what happens when recursion goes too deep.

The Russian-doll picture

Imagine a set of nested dolls and you want to know how many dolls there are. You open the outer doll. If there is nothing inside, the answer is 1. Otherwise, the answer is 1 plus however many dolls are inside, and you find that by asking the same question about the smaller set.

TEXT
count(doll_1)
  = 1 + count(doll_2)
          = 1 + count(doll_3)
                  = 1 + count(doll_4)   <- nothing inside: answer is 1

Two things made that work, and they are the two parts of every recursive function:

  • Base case: the smallest problem, answered directly without any further recursion ("nothing inside, so 1").
  • Recursive case: the bigger problem, expressed using a smaller version of the same problem ("1 plus the count of the inside").

If you forget the base case, the function calls itself forever (in practice, until Python stops it). If the recursive case does not make the problem smaller, you have the same problem again.

Your first recursive function: factorial

The factorial of n, written n!, is n * (n-1) * ... * 1. Notice that 5! = 5 * 4!. That is the recursive case. The base case is 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.

Read the function out loud: "the factorial of 0 is 1; the factorial of anything else is n times the factorial of n - 1". That is exactly the mathematical definition, which is one reason recursion is so pleasant: when the problem is defined recursively, the code mirrors the definition.

What really happens: the call stack

Python keeps a call stack. Every time a function is called, Python pushes a new frame holding that call's arguments and local variables. When the call returns, its frame is popped. With recursion, many frames for the same function exist at once, each with its own n.

Here is factorial(3) as a picture. Calls go down; results come back up.

TEXT
factorial(3)            waits for factorial(2)
  factorial(2)          waits for factorial(1)
    factorial(1)        waits for factorial(0)
      factorial(0)      returns 1          <- base case
    factorial(1)        returns 1 * 1 = 1
  factorial(2)          returns 2 * 1 = 2
factorial(3)            returns 3 * 2 = 6

The stack grows to four frames, then shrinks as each call finishes. Nothing is multiplied until the base case is reached: the multiplications are pending work that waits on the stack. Let us make the invisible visible by printing with indentation that follows the depth.

Python Watching the call stack

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 "called" lines go deeper and deeper; the "returns" lines unwind in the opposite order. This "go down, then come back up" shape is the heart of recursion, and it is why a recursive function can do work either before the recursive call (on the way down) or after it (on the way up).

When a recursive function confuses you, do not try to follow every call in your head. Instead use the leap of faith: assume the recursive call returns the correct answer for the smaller problem, and only check that (1) the base case is right and (2) your step turns that answer into the answer for the current problem. This is the same logic as mathematical induction.

A recipe for writing recursive functions

  1. Define what the function returns in one sentence, for any valid input. ("total(nums) returns the sum of the list nums.")
  2. Find the base case(s): the smallest inputs, answered directly. For lists that is usually the empty list; for numbers it is 0 or 1.
  3. Find the recursive case: assume the function works on a smaller input, and use its result to build the answer for yours.
  4. Check progress: every recursive call must be closer to a base case than the call that made it.

Example: sum of a list

The sum of an empty list is 0. The sum of a longer list is its first item plus the sum of the rest.

Python Sum of a list, two ways

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.

Both versions give 108. The first is simpler to read, but nums[1:] copies the rest of the list at every call, so it does O(n) work per call and O(nยฒ) overall. The second passes an index and copies nothing, which makes it O(n). This is a very common recursion trap: slicing inside recursion is secretly expensive.

Example: power

Computing x to the power n means multiplying x by itself n times. Recursively, x^n = x * x^(n-1) and x^0 = 1:

Python Power by repeated multiplication

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.

It takes 11 calls for n = 10: one per decrease of n plus the base case, so O(n) time. There is a much faster recursive idea (halve the exponent each time) that you will meet in Divide and Conquer.

Example: reversing a string

To reverse a string, put the first character after the reversed rest:

Python Reverse a string and test a palindrome

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.

Notice reverse has the recursive call before the work (adding the first character), so characters are appended while the stack unwinds. is_palindrome has two base cases and a quick exit (return False) that avoids deeper calls once a mismatch is found.

Recursion has a limit

Every frame uses memory, so Python limits how deep the stack can go. The default limit is 1,000 frames, and passing it raises RecursionError. A function with no reachable base case, or one that does not shrink its input, hits that limit quickly:

Python Missing base case (fails on purpose)

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 function keeps calling itself with smaller and smaller numbers (3, 2, 1, 0, -1, ...) until the stack is full, then Python raises the error instead of crashing the machine. The fix is a base case: if n < 0: return.

You can read and change the limit with sys.getrecursionlimit() and sys.setrecursionlimit(...), but raising it is usually the wrong cure. Very deep recursion can crash the interpreter, and a loop or an explicit stack is safer. Recursion Patterns shows how to convert deep recursion to iteration.

Python does not optimise recursion. A loop that runs a million times is fine; a recursive function that goes a million deep is not. If the depth can grow with the size of the input (a list with 100,000 items), prefer iteration.

Complexity of recursive functions

Two numbers matter:

Quantity How to find it
Time (number of calls) x (work per call, not counting the recursive calls)
Space the maximum depth of the call stack x the size of one frame (plus any extra data)

For factorial(n): n + 1 calls, constant work each, so time is O(n); the stack is n + 1 frames deep, so space is O(n) too. The same function written as a loop uses O(1) space. More complex shapes are analysed in Recurrences and the Master Theorem and Space Complexity.

Common mistakes

  • No base case, or one that is never reached. Check that every path through the function eventually hits it, including odd inputs such as negative numbers (factorial(-1) never reaches 0).
  • Not returning the recursive result. Writing factorial(n - 1) without return or without using the value is a classic bug: the function silently returns None.
  • Slicing or copying at each level, which turns O(n) into O(nยฒ).
  • Recomputing the same thing, as the naive Fibonacci does. Caching fixes that; see Memoization.
  • Using recursion where a loop is clearer. Simple counting or summing is usually better as a for loop in Python. Reach for recursion when the data or problem is itself recursive.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the two essential parts of every recursive function?

    The base case stops the recursion with a direct answer, and the recursive case reduces the problem to a smaller one of the same kind.
  2. 2. What happens if a recursive function never reaches its base case?

    Each call adds a stack frame, so Python eventually hits its recursion limit (1,000 by default) and raises RecursionError.
  3. 3. How many calls does factorial(5) make, counting the call for 0?

    It calls factorial(5), (4), (3), (2), (1) and (0): six calls in total.
  4. 4. Why is total(nums[1:]) inside the recursion costly?

    A slice creates a new list, so n calls that each copy up to n items cost O(nยฒ) overall. Passing an index avoids the copies.
  5. 5. What is the space complexity of a recursive factorial(n)?

    At the deepest point there are n + 1 frames on the stack, so the space is O(n), even though no list is created.

Summary

  • A recursive function calls itself on a smaller version of the problem. It needs a base case (direct answer) and a recursive case (progress toward the base case).
  • Each call gets its own stack frame; results are combined as the stack unwinds.
  • Use the leap of faith: trust the smaller call, and verify the base case and the combining step.
  • Time is the number of calls times the work per call; space is the maximum stack depth.
  • Python's default limit is 1,000 frames; deep recursion should become a loop or an explicit stack.
  • Avoid slicing inside recursion; pass indexes instead.

Next: Recursion Patterns