Recursion is the topic that intro programming students most often say they "get" and then lose points on. The idea is simple: a function repeats work by calling itself. The exam questions are not simple, because they ask what gets printed, in what order, and which exception stops the program. This post compares recursion with iteration the way Encodr's free Intro to Computer Science deck does in unit 12, using programs you can run to check every claim.

Two ways to repeat

Iteration repeats with a loop and a running variable. Recursion repeats by having a function call itself. For many problems both give the same answer. Here is factorial both ways:

```python def fact_iter(n): result = 1 for i in range(2, n + 1): result *= i return result

def fact_rec(n): return 1 if n <= 1 else n * fact_rec(n - 1)

print(fact_iter(5), fact_rec(5)) # 120 120 ```

A recursive function needs two parts. The base case is the input where it stops calling itself, here n <= 1. The recursive case calls itself on a smaller input, and every call must move its argument closer to the base case. Leave out the base case, or never approach it, and the recursion never ends.

What the call stack does

Each function call gets its own frame holding its own parameters and local variables. The frames of unfinished calls wait on the call stack, and the most recent call returns first (last in, first out). That is why results come back in reverse order. Trace this one on paper before you read the output:

```python def show(n): if n == 0: return show(n - 1) print("n is", n)

show(3)

n is 1

n is 2

n is 3

```

show(3) calls show(2) before it prints anything, which calls show(1), which calls show(0). That one returns, and then the prints happen on the way back up: 1, then 2, then 3. A common exam mistake is to expect the prints in the order of the calls (3, 2, 1). The print comes after the recursive call, so the prints run in reverse.

The frames also explain a classic true or false question. A recursive call does not reuse the local variables of the call that made it, because every call has its own n.

RecursionError

Every recursive call adds a stack frame, and Python limits the depth. Run this one:

```python def total_rec(n): return 0 if n == 0 else n + total_rec(n - 1)

print(total_rec(500)) # 125250 print(total_rec(10000)) # RecursionError ```

Python's default limit is about 1000 nested calls, so 500 works and 10,000 raises RecursionError. The limit exists to stop infinite recursion from overflowing the C stack and crashing Python. A loop that runs 100,000 times does not hit it, because the limit applies to nested calls and not to iterations.

Two more facts the exam likes:

• Python does not eliminate tail calls. A function whose last action is the recursive call, like count(5000) that returns count(n - 1), still raises RecursionError.
• sys.setrecursionlimit(n) raises the limit, but a very high value can crash Python, so it is not a fix for deep recursion.

The shape of the calls: chain or tree

Factorial makes one call per invocation, so the calls form a chain. Fibonacci makes two, so they form a tree. The recursive version is short:

``python def fib(n): if n < 2: return n return fib(n - 1) + fib(n - 2) ``

The base cases are fib(0) = 0 and fib(1) = 1. The trouble is the number of calls. Counting them with a counter variable gives:

The call count grows exponentially, which is what the course means by "naive recursive Fibonacci makes an exponential number of calls". A loop does n additions:

```python def fib_iter(n): a, b = 0, 1 for _ in range(n): a, b = b, a + b return a

print(fib_iter(9)) # 34 ```

The recursive version can be repaired by storing results in a dictionary, which is called memoization. With that fix, fib(50) returns 12,586,269,025, the same as the loop gives, without the explosion of repeated work. For how growth rates are classified, see Big-O notation explained for beginners.

When to use which

• Use a loop when the repetition is straightforward and the depth could be large. Loops have no depth limit.
• Use recursion when the problem is naturally self-similar, such as the digit sum of a number: n % 10 is the last digit and n // 10 drops it, with the base case n < 10. The course's digit_sum(6721) returns 16, the sum 1 + 6 + 7 + 2.
• Watch for several calls per invocation. One call per level is a chain and usually fine. Two or more makes a tree that can blow up without memoization.

How to practice

Trace first, run second. Write the call order on paper, predict the output and any exception, then run the code and find the exact line where you were wrong. Predicting before you check is more effective than just reading solutions, and the Intro to Computer Science practice questions include two recursion questions to start with. For a plan that spreads the course over the weeks you have, try the study schedule generator. The rest of the course is outlined in what's in Intro to Computer Science, and how to study for Intro to Computer Science covers tracing in more depth.