Python Recursion

The recursive step reduces the problem and calls the function again. "Reduce" is the key word: each call must move closer to the base case, usually by passing a smaller number, a shorter list or a sub-part of a structure.

def ribbon_total(boxes):
    if boxes == 0:
        return 0
    return boxes + ribbon_total(boxes - 1)   # one fewer box each call

Here a stack of 4 boxes needs 4 + ribbon_total(3), which needs 3 + ribbon_total(2), and so on. If the step passed the same value again, ribbon_total(boxes), no call would ever get closer to the base case.

A useful way to design the step is to trust the recursion: assume the function already works correctly for the smaller input, and only ask "how do I build the answer for this input from that?" That mental shortcut is called the recursive leap of faith, and it keeps you from trying to trace every level in your head.

The base case is the input simple enough to answer without another call: zero boxes, an empty list, a single character, a leaf node in a tree. It must be checked before the recursive call, and every possible input must eventually reach it.

def ribbon_total(boxes):
    if boxes < 0:
        raise ValueError("boxes cannot be negative")
    if boxes == 0:
        return 0
    return boxes + ribbon_total(boxes - 1)

Without the first check, ribbon_total(-1) would call itself with -2, -3 and so on, never reaching 0. Python stops runaway recursion with RecursionError: maximum recursion depth exceeded, by default after about 1,000 nested calls. Validating input before recursion starts, as above, turns a confusing crash into a clear message. Some problems have more than one base case, such as Fibonacci, where both 0 and 1 return directly.

Each function call gets its own frame on the call stack, with its own local variables. A recursive call pauses the current frame until the deeper one returns:

ribbon_total(3)
  3 + ribbon_total(2)            waiting
        2 + ribbon_total(1)      waiting
              1 + ribbon_total(0)  waiting
                    returns 0
              returns 1
        returns 3
  returns 6

On the way down, each frame remembers its own boxes value. On the way back up, each one adds its value to the result it receives.

Every waiting frame uses memory, which is why Python limits the depth. sys.getrecursionlimit() shows the limit, usually 1000. You can raise it with sys.setrecursionlimit(), but very deep recursion can still crash the interpreter, so treat that as a last resort. Python does not perform tail-call optimisation, so even a recursive call written as the last operation still adds a frame.

After the recursive call returns, the current step combines its own contribution with that result, and must return the combined value:

def longest_word(words):
    if len(words) == 1:
        return words[0]
    rest_best = longest_word(words[1:])
    return words[0] if len(words[0]) >= len(rest_best) else rest_best

Forgetting the return in front of a recursive call is the most common recursion bug. The deeper calls compute the right answer, but the outer call discards it and returns None.

The combining step is where recursion shines for branching structures. A folder's size is its files' sizes plus the size of each sub-folder; a tree's height is one plus the taller subtree. Writing those with loops requires managing your own stack, while recursion mirrors the shape of the data directly.

Task: trace the ribbon total and reject negative counts before starting recursion. Add a depth parameter so each call prints its level, and raise ValueError for negative input.

def ribbon_total(boxes, depth=0):
    if boxes < 0:
        raise ValueError("boxes cannot be negative")
    print("  " * depth + f"ribbon_total({boxes})")
    if boxes == 0:
        return 0
    return boxes + ribbon_total(boxes - 1, depth + 1)

print(ribbon_total(3))

ribbon_total(3)
  ribbon_total(2)
    ribbon_total(1)
      ribbon_total(0)
6

The indentation shows each frame waiting for the one below it. For the worked check, recursive descent is terminated by a reachable base case: a condition that every input eventually meets and that returns without another call.

The sys.setrecursionlimit documentation explains the depth limit, and functools.lru_cache covers memoisation. Continue with recursive problem solving and trees and binary search trees. Practise with the Python exercises and Python quiz.