Skip to content
Tutorials Center
My learning

Topics

Lesson 61 of 225 ยท Recursion and Backtracking

Recursion Patterns

Learn the main shapes of recursion in Python: linear, binary, tail and mutual recursion, plus how to turn recursion into a loop with an explicit stack.

Once you know what recursion is, the next step is to notice that recursive functions come in a few recognisable shapes. The shape tells you the number of calls, the depth of the stack, and therefore the time and space cost, before you have written a single line.

In this lesson you will meet four shapes (linear, binary, tail and mutual recursion), learn why "tail recursion" does not give you a free speedup in Python, convert a recursive function into a loop with an explicit stack, and pick up a tracing trick that makes any recursive function easy to debug.

Shape 1: linear recursion

A linear recursive function makes at most one recursive call per run. The calls form a single chain, like a line of dominoes. factorial, the list sum and string reversal from the last lesson are all linear.

TEXT
total([4, 8, 15])
  total([8, 15])
    total([15])
      total([])      <- chain of n + 1 calls

With n items, there are about n calls and a stack depth of n. Time is O(n) if each call does constant work; space is O(n) because of the stack.

A useful variant is a linear recursion that searches and stops early. Here is a recursive linear search that returns the index of a target, or -1:

Python Linear recursion: search

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.

Shape 2: binary recursion

A binary recursive function makes two recursive calls. The calls form a tree instead of a chain. The famous example is the Fibonacci sequence, where each number is the sum of the previous two:

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

Count the boxes: fib(4) makes 9 calls, and the number of calls roughly multiplies by 1.6 each time n goes up by one. That is exponential growth. Run it and count:

Python Binary recursion: Fibonacci and call counts

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 call count explodes (15 calls for fib(5), 21,891 for fib(20)) even though the stack never goes deeper than n. The reason is that the same sub-problems are solved again and again: fib(2) appears three times in the tree above. Storing results fixes this, and it is the main idea behind dynamic programming. With the standard library it is one line:

Python Fixing binary recursion with a cache

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 value of n is now computed only once, so fib(20) needs 21 calls and fib(30) adds just 10 more. Binary recursion is not always exponential, though. When the two calls work on different halves of the data, as in merge sort, there is no overlap and the total stays small; see Divide and Conquer.

Shape 3: tail recursion

A call is a tail call when it is the very last thing the function does: its result is returned unchanged, with nothing left to do afterwards. Compare:

TEXT
not a tail call:   return n * factorial(n - 1)     <- still has to multiply
tail call:         return factorial(n - 1, n * acc) <- nothing left to do

Tail-recursive functions usually carry an extra accumulator parameter holding the answer built so far:

Python Tail recursion with an accumulator

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.

Some languages notice that nothing is left to do and reuse the current stack frame, so tail recursion costs O(1) space there. Python does not do this. A tail-recursive Python function still pushes one frame per call and still raises RecursionError at depth 1,000:

Python Tail calls are not optimised (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.

So in Python, treat tail recursion as a way of thinking that makes it easy to convert a function to a loop (below), not as an optimisation.

Shape 4: mutual recursion

In mutual recursion, function A calls function B and B calls A. It shows up when a problem has two alternating states, such as parsing nested expressions, or this tiny example that decides if a number is even or odd:

Python Mutual recursion

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 reduces n and hands over to the other function. The same base-case rules apply: every chain of calls must end in a base case. (In real code you would write n % 2 == 0; the example is only about the shape.)

From recursion to iteration

Because the call stack is just a stack, you can always replace recursion with a loop and a stack you manage yourself. There are two situations.

Case 1: tail recursion becomes a plain loop. The parameters become variables, and the recursive call becomes assigning new values:

TEXT
def factorial(n, acc=1):          def factorial(n):
    if n == 0: return acc             acc = 1
    return factorial(n-1, acc*n)      while n > 0:
                                          acc *= n
                                          n -= 1
                                      return acc

Case 2: non-tail recursion needs an explicit stack. The function must remember pending work. Take the nested-list sum, where lists can contain lists to any depth. The recursive version:

Python Recursive and iterative nested sum

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 print 21. The iterative version never fails with RecursionError, because its stack is a list on the heap, limited only by memory. This conversion is exactly what depth-first search does on very large graphs.

A debugging trick: trace with indentation

When a recursive function misbehaves, a decorator that prints entry and exit with indentation shows the whole tree of calls, without touching the function body:

Python A tracing decorator

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.

Because the recursive call inside fib refers to the global name fib, which is now the decorated version, every call is traced.

Choosing a shape: the cost table

Shape Calls Max depth Typical cost
Linear n n O(n) time, O(n) space
Binary, overlapping (naive Fibonacci) about 1.6^n n exponential time; fixed by caching
Binary, splitting (merge sort) about 2n log n O(n log n) time
Tail n n in Python O(n) time, O(n) space (O(1) as a loop)
Mutual n n like linear

Common mistakes

  • Expecting tail-call optimisation in Python. It does not exist; convert to a loop yourself.
  • Forgetting the accumulator's starting value (using acc = 0 for a product gives 0).
  • Binary recursion on overlapping sub-problems without caching.
  • Mutating a shared list that an outer call is still using. Pass copies, or undo changes, as shown in Backtracking.
  • Over-converting. If recursion is clear and the depth is small (a balanced tree is only about log n deep), keep it.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which function is an example of binary recursion?

    Binary recursion makes two recursive calls per run, and fib calls itself twice.
  2. 2. What does Python do with a tail call?

    Python does not implement tail-call optimisation, so a tail-recursive function can still raise RecursionError.
  3. 3. Why is naive recursive fib(n) so slow?

    fib(n - 1) and fib(n - 2) share sub-problems, so the number of calls grows exponentially. A cache makes each value computed once.
  4. 4. How can you avoid RecursionError on a very deep nested structure?

    A list used as a stack lives on the heap, so its depth is limited by memory rather than by the interpreter's call-stack limit.
  5. 5. In the tail-recursive factorial(n, acc), what is acc?

    The accumulator carries the partial product down the calls, so when n reaches 0 the answer is already in acc.

Summary

  • Linear recursion makes one call per run (a chain); binary makes two (a tree); tail recursion ends with the recursive call; mutual recursion alternates between functions.
  • Naive binary recursion with overlapping sub-problems is exponential; functools.cache (or dynamic programming) removes the repetition.
  • Python does not optimise tail calls: rewrite them as loops when depth could be large.
  • Any recursion can become iteration with an explicit stack.
  • A tracing decorator with indentation makes recursive behaviour visible.

Next: Divide and Conquer