# Recursion and Iterative Alternatives

Computer Science I · Programming II · https://tryals.app/learn/computer-science-i/recursion-and-iterative-alternatives

## Anatomy of Recursion

**Recursion** is when a function solves a problem by calling **itself** on a smaller version of the same problem.

Every correct recursive function contains two essential parts:

| Part | Role | Example ($n!$)
| --- | --- | --- |
| **Base Case** | Stops recursion by answering a tiny input directly | $0! = 1$
| **Recursive Case** | Breaks the problem down toward the base case | $n! = n \times (n-1)!$

Here is the classic code implementation:

```python
def factorial(n):
    if n == 0:        # base case
        return 1
    return n * factorial(n - 1)   # recursive case
```

**Common pitfall:** Forgetting the base case, or writing a recursive step that fails to shrink the input. Both cause **infinite recursion** until the **call stack** overflows in a **stack overflow**.

## The Call Stack and Iteration

Each recursive call waits for the smaller call to finish, stacking up frames: `factorial(3)` waits for `factorial(2)`, and so on, until $0! = 1$ resolves and results multiply back up.

Anything recursive can also be written **iteratively** with a loop, and vice versa. Use the comparison below to choose:

| Approach | Strengths | Weaknesses |
| --- | --- | --- |
| **Recursion** | Expresses trees and divide-and-conquer clearly | Function call overhead, memory cost on stack |
| **Iteration** | More memory-efficient for simple repetition | Can obscure naturally recursive data structures |

The choice between them is about clarity and cost, not capability. Every recursive function must have a reachable base case, and each step must make the problem strictly smaller.

## Practice questions

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

### 1. The lesson's factorial function is called as factorial(3). Order the events by when they happen in time.

**Answer:**

1. factorial(3) starts and calls factorial(2)
2. factorial(2) starts and calls factorial(1)
3. factorial(1) starts and calls factorial(0)
4. factorial(0) returns 1 without recursing
5. The waiting calls finish in turn, giving 1, then 2, then 6

**Why:** Calls stack up on the way down and unwind on the way back, so factorial(3) is the first to start and the last to finish. This is exactly why deep recursion costs memory: every suspended call keeps its frame on the call stack until the one below it returns.

Page: https://tryals.app/practice/computer-science-i/recursion-and-iterative-alternatives/the-lessons-factorial-function-is-called-as-factorial-3-order-the

### 2. Every recursive function can be rewritten as a loop, and every loop can be rewritten recursively. Why does the choice between them still matter?

A. Because recursion is always slower, so loops should be used wherever performance matters.
B. Because the compiler rejects recursion in some languages, forcing the iterative form.
C. Because one of them usually matches the shape of the problem.
D. Because recursion can express computations that loops cannot, despite the equivalence.

**Answer:** C. Because one of them usually matches the shape of the problem.

**Why:** The equivalence is real and the ergonomics differ: a tree is a node with subtrees, so a recursive traversal mirrors it, where the iterative version maintains an explicit stack. Recursion costs a frame per call and tail-call optimisation removes that where it is guaranteed, so decide on clarity, and check depth when input could be large: a million-element descent exhausts Python’s stack.

Page: https://tryals.app/practice/computer-science-i/recursion-and-iterative-alternatives/every-recursive-function-can-be-rewritten-as-a-loop-and-every-loop

### 3. A recursive function that would need a million frames crashes in Python and runs fine in a language with tail-call optimisation. What does that optimisation do?

A. Runs the recursive calls in parallel to reduce depth
B. Reuses the current stack frame, turning the recursion into a loop
C. Increases the maximum stack size to accommodate deep recursion
D. Converts the function to an iterative version automatically at compile time

**Answer:** B. Reuses the current stack frame, turning the recursion into a loop

**Why:** If nothing happens after the recursive call, the current frame has no remaining work and can be reused, so depth costs no memory. Scheme mandates it and Python deliberately declines, preferring readable stack traces, which is why deep recursion in Python is a design error rather than a style choice.

Page: https://tryals.app/practice/computer-science-i/recursion-and-iterative-alternatives/a-recursive-function-that-would-need-a-million-frames-crashes-in

### 4. Select every statement the lesson supports about choosing recursion over iteration.

A. Recursion can express naturally-recursive problems such as trees more clearly
B. Each recursive call carries overhead and occupies space on the call stack
C. Iteration is usually more memory-efficient for simple repetition
D. A recursive solution is always shorter than the iterative one
E. There are computations that recursion can do and iteration cannot

**Answer:** A. Recursion can express naturally-recursive problems such as trees more clearly; B. Each recursive call carries overhead and occupies space on the call stack; C. Iteration is usually more memory-efficient for simple repetition

**Why:** Anything recursive can be written iteratively and vice versa, so neither is more capable; the real differences are clarity for nested problems against the per-call time and stack cost. Believing recursion can do more than iteration is the misconception the lesson corrects, and 'always shorter' is a style claim the lesson never makes.

Page: https://tryals.app/practice/computer-science-i/recursion-and-iterative-alternatives/select-every-statement-the-lesson-supports-about-choosing-recursion

### 5. A recursive function that has a base case cannot recurse forever.

**Answer:** False

**Why:** False. The base case must actually be *reached*: `f(n)` calling `f(n+1)`, or calling `f(n)` unchanged, recurses forever with a perfectly good base case sitting there. Termination needs a measure that strictly decreases toward the base on every call, which is the same argument as a loop variant.

Page: https://tryals.app/practice/computer-science-i/recursion-and-iterative-alternatives/a-recursive-function-that-has-a-base-case-cannot-recurse-forever