--- title: Recursion source: 'https://academia.sh/en/courses/programming-fundamentals/recursion' course: 'Programming Fundamentals' language: en updated: '2026-08-17T18:08:25+00:00' license: 'CC BY-SA 4.0' --- # Recursion The base case and the reduction step, expansion on the call stack, infinite recursion, and its cost. If a function can call another function inside its body, it can call itself as well. This is permitted by definition, and it is called **recursion**. This idea, which appears circular at first glance, becomes clear once the call stack is understood: each call has its own frame, so multiple calls to the same function can exist at once, each with independent variables. ## Two Required Parts Every recursive definition consists of two parts: **Base case:** The smallest case, answered directly without recursion. **Reduction step:** The step that transforms the problem into a smaller instance of the same problem. If either part is missing, the solution does not work. Without a base case, the calls continue indefinitely; if the reduction does not make the problem smaller, the base case is never reached. ```python def factorial(n: int) -> int: """Computes the value of n!. n must not be negative.""" if n < 0: raise ValueError("negative value") if n <= 1: # base case return 1 return n * factorial(n - 1) # reduction: n decreases to n - 1 print(factorial(5)) # 120 print(factorial(0)) # 1 ``` Writing the base case as `n <= 1` gives the correct answer for both $0$ and $1$, and guarantees that every non-negative input reaches the base case. ## Expansion on the Stack Executing the call `factorial(4)` proceeds as frames accumulate on top of one another and are then resolved in reverse order: ``` factorial(4) = 4 * factorial(3) = 4 * (3 * factorial(2)) = 4 * (3 * (2 * factorial(1))) = 4 * (3 * (2 * 1)) ← base case reached = 4 * (3 * 2) = 4 * 6 = 24 ``` The lines going upward show the calls expanding, and the lines going downward show the returns being combined. At the deepest point, four frames are on the stack at the same time; each has its own value of `n`. This is the clearest example of the frame model established in the previous course: `n` is not a single memory cell; it exists separately in the frame of each call. ## Infinite Recursion When the base case is forgotten, or when the reduction does not make the problem smaller, calls accumulate and the stack runs out. ```python def broken(n: int) -> int: return n * broken(n - 1) # no base case # broken(5) -> recursion limit exceeded error ``` This behavior was defined in the memory layout lesson of the previous course: every call adds a frame, none of them return, and the space allocated for the stack runs out. In languages with a runtime guard, a controlled error is raised; in those without one, the process is terminated. The error message typically contains the same function name hundreds of times — this is the distinctive signature of infinite recursion. ## Naturally Recursive Problems Recursion is the natural solution when the problem itself is defined recursively. The sum of a list of measurements can be defined this way: *the sum of an empty list is zero; the sum of a non-empty list is its first element plus the sum of the rest.* ```python def total(measurements: list[int]) -> int: if not measurements: # base case: empty list return 0 return measurements[0] + total(measurements[1:]) # reduction: one fewer element print(total([12, 18, 7])) # 37 print(total([])) # 0 ``` This solution is a direct translation of the definition; it is easy to read. In exchange, it copies the rest of the list on every call and opens as many frames as there are elements — a loop performing the same task works with a single frame and no copying. Where recursion is genuinely superior is in problems where the data itself branches: traversing tree structures, scanning directories with their subdirectories, divide-and-conquer algorithms. These structures are the subject of the **Data Structures** and **Algorithms** courses; most solutions there are written recursively. ## Cost and Repeated Computation Recursion has two costs: memory per frame and extra processing per call. A third, more insidious cost is **the same computation being repeated**. The direct recursive definition of the Fibonacci sequence is the canonical example of this. ```python def fib(n: int) -> int: if n < 2: return n return fib(n - 1) + fib(n - 2) print(fib(10)) # 55 ``` While computing `fib(5)`, `fib(3)` is computed twice and `fib(2)` three times. As the input grows, the number of repetitions grows exponentially; computing `fib(30)` makes more than a million calls. The solution is to store the computed values: ```python def fib_memoized(n: int, memo: dict[int, int] | None = None) -> int: if memo is None: memo = {} if n < 2: return n if n in memo: # already computed, do not recompute return memo[n] memo[n] = fib_memoized(n - 1, memo) + fib_memoized(n - 2, memo) return memo[n] print(fib_memoized(30)) # 832040 ``` The precondition for memoization is that the function always produces the same result for the same input; the result of a function that depends on state beyond its input cannot be stored this way. This technique is called **memoization**, and it is the foundation of dynamic programming; it is treated in its general form in the Advanced Algorithms course. The lesson here is that recursion gives the structure of a solution but does not bring efficiency on its own. ## Mutual Recursion Recursion is not limited to a function calling itself directly. Two functions calling each other can also form a recursive structure; this is called **mutual recursion**. ```python def is_even(n: int) -> bool: if n == 0: return True return is_odd(n - 1) def is_odd(n: int) -> bool: if n == 0: return False return is_even(n - 1) print(is_even(4), is_odd(4)) # True False ``` This example exists to illustrate the concept; the same question is answered in a single step with the remainder operator. The real use of mutual recursion is in structures where interdependent definitions are naturally mutual — parsers processing grammar rules are the typical example: an *expression* definition refers to a *term* definition, which refers back to *expression*. The base case rule applies here as well, but it becomes harder to verify: the guarantee of termination must be found not in a single function but across the entire chain of calls. ## Recursion or Loop The criteria for choosing: | Criterion | Recursion | Loop | |---|---|---| | The problem definition branches | Natural | Requires manual stack management | | Progress is linear | Pays a frame cost | Cheaper | | Depth grows with the input | Risk of hitting the stack limit | No limit | | Readability | Close to the definition | Close to the steps | The general rule: **use recursion if the problem is defined recursively, use a loop if the repetition is linear.** Every recursive solution can be converted to a loop; the conversion may require maintaining a stack manually. ## Summary - Recursion is a function calling itself; because each call has its own frame, the variables do not mix. - Every recursive definition contains a base case and a reduction step; if either is missing, the solution does not work. - Calls accumulate on the stack, expansion stops at the base case, and the returns are combined in reverse order. - Infinite recursion exhausts the stack; its signature is the repeated function name in the error message. - Recursion is natural for branching structures; a loop is cheaper for linear repetition. - Recomputing the same subproblem can produce exponential cost; memoization removes this repetition. ## Next Step In linear recursion, the frame cost appears unavoidable. The situation changes, however, when the call is the last operation in the body: opening a new frame is no longer necessary. The next lesson takes up this special form — tail recursion — and its equivalence to a loop.