Recursion

Recursive functions

Definition. A recursive function calls itself directly or through another function. A correct recursive definition has a base case that returns without further recursive calls and a progress step that moves the input toward a base case. Each active call has its own parameters and automatic local objects.

Example. Factorial obeys $0!=1$ and $n!=n(n-1)!$ for integer $n\ge1$.

Exam point. Check termination for every allowed input, not only the example input.

Call stack and activation records

Definition. Each active call has an activation record holding its parameters, local values, and return information according to the calling convention. Calls are pushed as execution descends; returns unwind in reverse order. A value computed after a recursive call remains pending in the caller's frame.

Example. In return n + f(n-1), each call waits to add its own n after the deeper call returns.

Exam point. Trace calls downward first, then evaluate pending operations while unwinding.

Solved trace. Evaluate f(4) for int f(int n){ if(n==0)return 0; return n+f(n-1); }.

1. f(4) waits for 4+f(3).
2. f(3) waits for 3+f(2); then f(2) waits for 2+f(1).
3. f(1) waits for 1+f(0); f(0) returns 0.
4. Unwind: f(1)=1, f(2)=3, f(3)=6, f(4)=10. Answer. 10.

Base cases and progress

Definition. A base case is a condition that terminates recursion with a direct result. The recursive step must reduce a well-founded measure, such as a nonnegative integer n, toward that base case. Missing or unreachable base cases cause nontermination or stack exhaustion.

Example. A countdown on positive n can recurse on n−1 until n=0.

Exam point. State the input domain; a recurrence may terminate for nonnegative integers but not for negative values.

Solved check. Does int f(int n){if(n==1)return 1; return f(n-2);} terminate for every positive integer n?

1. For odd positive n, repeated subtraction reaches 1.
2. For even n, the sequence reaches 0, then −2, −4, and continues downward.
3. The base case n==1 is never reached for even n. Answer. No; even positive inputs do not terminate.

Factorial recursion

Definition. For integer $n\ge0$, factorial is defined by $0!=1$ and $n!=n(n-1)!$. The recursive algorithm makes n multiplications for n>0 and has call depth n+1 including the base call. Large values overflow fixed-width integer types.

Example. $4!=4\cdot3\cdot2\cdot1=24$.

Exam point. Count the base call when asked for maximum stack depth.

Solved trace. Trace recursive factorial of 5 and count multiplication operations.

1. Calls are fact(5), fact(4), fact(3), fact(2), fact(1), fact(0): six active calls at deepest point.
2. fact(0) returns 1.
3. Returns multiply: 1, 2, 6, 24, 120.
4. Multiplications occur for n=1 through 5, for five total. Answer. 120; five multiplications; maximum call depth six.

Fibonacci recursion

Definition. The Fibonacci recurrence is $F_0=0,F_1=1$, and $F_n=F_{n-1}+F_{n-2}$ for n≥2. Direct recursion recomputes many subproblems and has exponential time in n; its recursion depth is linear. Memoization or iteration reduces repeated work to linear time.

Example. $F_5=5$.

Exam point. Exponential call count and linear maximum depth are different quantities.

Solved trace. Compute F4 using the direct recurrence and count calls including base cases.

1. F4 calls F3 and F2.
2. F3 calls F2 and F1; the left F2 calls F1 and F0.
3. The right F2 calls F1 and F0.
4. Total calls: F4(1), F3(1), F2 twice, F1 three times, F0 twice = 9.
5. Values give F2=1, F3=2, F4=3. Answer. F4=3 with 9 calls in this direct evaluation.

Linear and tail recursion

Definition. A recursion is linear when each call makes at most one recursive call. It is tail-recursive when the recursive call is the final operation before returning. Tail recursion may be transformed into iteration by carrying the pending computation in parameters, but C does not require compilers to optimize it.

Example. return f(n-1, acc*n); is tail-recursive if it returns that call directly.

Exam point. Tail recursion can use constant auxiliary stack only when implemented with tail-call optimization or rewritten iteratively.

Solved transformation. Convert factorial to an iterative loop and compare the result for n=4.

1. Initialize accumulator r=1.
2. For i from 2 through 4, update r←r×i.
3. Values are 2, then 6, then 24.
4. Recursive factorial also produces 24. Answer. Both compute 24; the loop uses constant auxiliary state.

Binary recursion and divide-and-conquer

Definition. A recursive function with two recursive calls can branch into a call tree. Divide-and-conquer algorithms split a problem into smaller subproblems, solve them recursively, then combine results. Running time depends on number and size of subproblems plus the combine cost.

Example. Binary search recurses on one half; merge sort recurses on two halves and merges them.

Exam point. Count call-tree levels and per-level work separately.

Solved recurrence. Solve $T(n)=2T(n/2)+n$ for n a power of two, with $T(1)=1$.

1. At each level, total combine work is n.
2. The number of levels before subproblem size reaches 1 is $\log_2n$.
3. Leaves contribute n base cases, each constant cost.
4. Total is $n\log_2n+O(n)$. Answer. $T(n)=\Theta(n\log n)$.

Binary search recursion

Definition. Binary search on a sorted array compares a key with a midpoint and recurses into at most one half. It requires a sorted range and a correct interval convention. Each step reduces the search interval by about half, so time is logarithmic and recursive stack depth is logarithmic.

Example. Searching 14 in [2,5,8,11,14,17,20] checks the middle value 11, then searches the right half.

Exam point. An unsorted array does not satisfy the algorithm's precondition.

Solved trace. Search key 19 in sorted array [3,7,10,14,18,22,27,31] using inclusive low/high indices and lower midpoint.

1. low=0, high=7; mid=3, value 14. Since 19>14, set low=4.
2. low=4, high=7; mid=5, value 22. Since 19<22, set high=4.
3. low=4, high=4; mid=4, value 18. Since 19>18, set low=5.
4. Now low>high, so key is absent. Answer. Not found after 3 comparisons.

Recursive tree traversals

Definition. Tree traversals are naturally recursive because each node has subtrees. Preorder visits node, left, right; inorder visits left, node, right; postorder visits left, right, node. The order assumes the same traversal rule is applied recursively to each child.

Example. For root A with left B and right C, preorder is A,B,C.

Exam point. Write the traversal rule before listing node order.