# Recursion

Mathematics I · Programming Elements · https://tryals.app/learn/mathematics-i/recursion

## Anatomy of Recursion

**Recursion** is a technique where a function **calls itself** on a smaller version of a problem until it reaches a directly solvable case. It parallels mathematical **induction**.

Every recursive function requires two core ingredients:

| Ingredient | Role | Example ($n!$) |
| --- | --- | --- |
| **Base case** | Stops recursion directly | $0! = 1$ |
| **Recursive case** | Shrinks problem & calls self | $n! = n \times (n-1)!$ |

To compute $3!$, the function descends to the base case, then **unwinds** upward: $3 \times 2 \times 1 = 6$.

## Rules and Pitfalls

Recursive calls must make strict **progress toward the base case**. If the subproblem does not shrink, the function **recurses forever**, triggering a **stack overflow** as pending calls pile up.

| Property | Requirement |
| --- | --- |
| **Termination** | Must reach base case |
| **Convergence** | Inputs must strictly decrease |

Proving a recursive function correct **is** an induction. The base case establishes correctness, and the recursive step ensures larger instances build correctly on smaller ones.

## Practice questions

7 of this lesson's 13 practice questions, with answers. The full set is in the app.

### 1. A recursive function calls itself, which sounds like it should never finish. Why does a correct recursion terminate, and what happens when the base case is missing?

A. Because each call takes a strictly smaller input toward a base case.
B. Because recursive calls are made on the same input, which eventually stabilises.
C. Because the compiler detects the repetition and stops it after a fixed number of calls.
D. Because each recursive call returns immediately, so no chain of calls builds up.

**Answer:** A. Because each call takes a strictly smaller input toward a base case.

**Why:** Two conditions must hold: the argument strictly decreases toward the base, and the base handles the smallest input without recursing. Remove it and the descent runs past zero, adding frames until the stack is exhausted. The parallel with induction is exact, base case, inductive hypothesis, and proving a recursion correct *is* an induction proof.

Page: https://tryals.app/practice/mathematics-i/recursion/a-recursive-function-calls-itself-which-sounds-like-it-should-never

### 2. Each definition is evaluated at n = 5. Sort by whether the recursion terminates.

**Answer:**

- Terminates: f(n) = f(n - 1) + 1, with f(0) = 0, f(n) = f(n - 2), with f(0) = 1 and f(1) = 1, f(n) = 2 * f(n - 1), with f(1) = 1
- Runs forever: f(n) = f(n) + 1, with f(0) = 0, f(n) = f(n + 1) - 1, with f(0) = 0

**Why:** d1, d3 and d5 shrink the argument and land on a base case (d3 goes 5, 3, 1). d2 never changes n and d4 increases it, so neither ever reaches 0 despite having a base case. Having a base case is not enough; the calls must reach it.

Page: https://tryals.app/practice/mathematics-i/recursion/each-definition-is-evaluated-at-n-5-sort-by-whether-the-recursion

### 3. Order what happens when a recursive factorial computes 3 factorial.

**Answer:**

1. The call for 3 needs the value for 2
2. The call for 2 needs the value for 1
3. The call for 1 needs the value for 0
4. The base case gives the value for 0 as 1
5. The results multiply back up to give 6

**Why:** The calls stack downward to the base case, which is the first value actually known, and only then does the multiplication unwind upward. Without the base case the descent never stops, the stack overflow.

Page: https://tryals.app/practice/mathematics-i/recursion/order-what-happens-when-a-recursive-factorial-computes-3-factorial

### 4. The factorial is defined by fact(n) = n * fact(n-1) with fact(0) = 1. Compute fact(5).

**Answer:** 120

**Why:** 5 * 4 * 3 * 2 * 1 = 120, with the base case contributing the final factor 1. Checking a recursive definition on a small value you can verify by hand is the same sanity check a base case performs in an induction proof.

Page: https://tryals.app/practice/mathematics-i/recursion/the-factorial-is-defined-by-fact-n-n-fact-n-1-with-fact-0-1

### 5. Computing fact(4) recursively, how many calls to fact are made in total, counting the original call and the base-case call?

**Answer:** 5

**Why:** The calls are fact(4), fact(3), fact(2), fact(1), fact(0), five in all. Each is a pending frame on the call stack, which is why a recursion that never reaches its base case exhausts memory rather than merely looping.

Page: https://tryals.app/practice/mathematics-i/recursion/computing-fact-4-recursively-how-many-calls-to-fact-are-made-in

### 6. Complete the condition for a recursion to terminate.

**Answer:** A recursive function fails to terminate when its calls **do not make the problem strictly smaller**.

**Why:** Progress is the second requirement: each call must shrink the problem so the base case is eventually reached. A definition like f(n) = f(n) + 1 has a base case that is simply never reached.

Page: https://tryals.app/practice/mathematics-i/recursion/complete-the-condition-for-a-recursion-to-terminate

### 7. A recursive Fibonacci function is elegant and unusably slow; the loop version is ugly and instant. Where does the recursive version's time actually go?

A. Into the overhead of function calls, which dominates the arithmetic
B. Into converting between recursive and iterative representations internally
C. Into recomputing the same subproblems exponentially often
D. Into stack memory, which slows access as the depth grows

**Answer:** C. Into recomputing the same subproblems exponentially often

**Why:** The tree has about 2ⁿ nodes and only n distinct values in it, so almost all the work is repetition. Adding a cache makes it linear without touching the structure, which is why the fix is memoisation rather than abandoning recursion, and why this is the standard first example of dynamic programming.

Page: https://tryals.app/practice/mathematics-i/recursion/a-recursive-fibonacci-function-is-elegant-and-unusably-slow-the-loop