Recursion

Recursion is when a function calls itself on a smaller version of the same problem until the problem is small enough to answer directly.

The two cases

• Base case: smallest input, answered directly with no recursion. This is the stopping condition.
• Recursive case: do a little work, then call yourself on a smaller input.
• Every recursive call must move strictly toward the base case.

The call stack

• Each call gets its own stack frame holding its arguments and locals.
• Last-in, first-out: the deepest call finishes first; each frame waits for the ones below it to return.
• Depth d means d live frames, so recursion costs O(depth) space.

sum_to(3) = 3 + sum_to(2)
              sum_to(2) = 2 + sum_to(1)
                            sum_to(1) = 1 + sum_to(0)
                                          sum_to(0) = 0   <- base returns
                            sum_to(1) = 1 + 0 = 1
              sum_to(2) = 2 + 1 = 3
sum_to(3) = 3 + 3 = 6

Complexity

• factorial / sum_to: O(n) time, O(n) space (stack of n frames).
• Naive fib: O(2^n) time (each call spawns two), O(n) space (one root-to-leaf path).
• Memoization stores each answer once to kill the repeated subproblems in a fanned-out tree.

Recursion vs iteration

• Iteration (a for/while loop) uses O(1) stack space and has no depth limit.
• Anything recursive can be written iteratively and vice versa.
• Recursion when the data is recursive (trees, nested folders, divide-and-conquer); iteration when just repeating a step a known number of times.

Gotchas

• No base case, or one the input skips past (n - 1 going negative past == 0; use <= 0) causes infinite recursion.
• Forgetting return on the recursive call returns None.
• Python caps depth around 1000 nested calls, then raises RecursionError.
• Redoing identical work (naive fib) means you want memoization.