Recursion
Recursion in C: definitions, stack behavior, base/recursive cases, direct/indirect and tail recursion, recursion trees and recurrences, complexity of classic problems, with complete C programs (factorial, sum of digits, Tower of Hanoi).
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Recursion helps express problems that have natural self-similar structure, like directory traversal, tree/graph processing, parsing, and divide-and-conquer algorithms. Engineers use it to write clear solutions for tasks such as walking file systems, evaluating expressions, quicksort/mergesort, and solving combinatorial problems.
Key ideas
- Recursion: A method where a function solves a problem by calling itself on a smaller instance of the same problem. Exact definition: A function is recursive if and only if it calls itself directly or indirectly. Note: Termination conditions are required for a correct algorithm, but they are not part of the definition of recursion.
- Direct recursion: The function calls itself in its own body (e.g., f calls f).
- Indirect recursion: A cycle of function calls returns to the original function (e.g., f calls g, and g calls f). Assumption: Each function involved respects types and termination conditions.
- Base case (stopping condition): The simplest input(s) for which the answer is known and the function returns without further self-calls. Exact statement: A correct recursive algorithm must include one or more base cases that are reached in a finite number of steps for all valid inputs.
- Recursive case: The part that reduces the current problem to one or more strictly smaller subproblems, followed by combining their results. Assumption: Each recursive call moves the state closer to a base case (e.g., smaller n).
- Activation record (stack frame): The block of data pushed on the call stack when a function is called. It holds the return address, parameters, local variables, and bookkeeping data. Assumption: C implementations use a call stack to manage function calls.
- Call stack: A last-in-first-out (LIFO) memory structure used at runtime to store activation records. When the function returns, its frame is popped and control jumps to the saved return address.
- Tail recursion: A recursive call is in tail position if it is the final action of the function; i.e., the function returns directly the result of the recursive call without further computation. Definition: A function is tail-recursive if all recursive calls are in tail position.
- Head recursion: The recursive call happens before any processing in the current call (e.g., f first calls f on smaller input, then processes the result).
- Recursion tree: A conceptual tree showing how a recursive function expands into subcalls; useful for visualizing the number of calls and work per level.
- Recurrence relation: An equation defining the running time or number of operations in terms of itself for smaller inputs (e.g., T(n) = T(n−1) + c).
- Correctness by mathematical induction: A proof technique commonly used to prove a recursive algorithm is correct by showing (1) base case is correct, and (2) if correct for smaller inputs, then correct for n.
Exact statements and typical derivations universities expect:
- Factorial definition and proof sketch
- Definition: For integer n ≥ 0, factorial is defined recursively as n! = 1 if n ∈ {0,1} (base), and n! = n × (n−1)! for n ≥ 2 (recursive case).
- Termination assumption: Repeatedly decreasing n by 1 eventually reaches 1 or 0.
- Induction proof idea: Base n=0 and n=1 return 1 (true). Inductive step: Assume (n−1)! is computed correctly; then n! = n × (n−1)! is correct by definition.
- Fibonacci numbers and complexity intuition
- Definition: F(0) = 0, F(1) = 1; for n ≥ 2, F(n) = F(n−1) + F(n−2).
- Recursion tree shows duplicate subproblems. The count of calls grows exponentially; the naive recursion leads to exponential time.
- Tower of Hanoi recurrence and move count
- Problem: Move n disks from peg A to peg C using peg B, moving one disk at a time, never placing a larger disk on a smaller disk.
- Recursive strategy: Move n−1 disks from A to B; move largest disk A→C; move n−1 disks from B to C.
- Recurrence for moves: T(1) = 1; T(n) = 2·T(n−1) + 1 for n ≥ 2.
- Derivation (by induction) of closed form: Conjecture T(n) = 2^n − 1. Base: T(1) = 1 = 2^1 − 1. Inductive step: T(n) = 2·T(n−1) + 1 = 2·(2^{n−1} − 1) + 1 = 2^n − 2 + 1 = 2^n − 1.
- Stack behavior diagram students should draw and label (no images):
- Title: "Call stack during factorial(4)".
- Draw vertical boxes stacked top-to-bottom, each box labeled "Frame for fact(k)" with k = 4,3,2,1 in order of creation, the topmost being fact(1). Inside each box, label: parameters (n=k), local temporaries if any, and a field "return to" showing the caller (e.g., fact(2) returns to fact(3) at multiply step). Use arrows to show return flow from top (fact(1)) popping to bottom (main).
- Tail recursion remark in C
- Tail-recursive functions can often be optimized to run like loops, but the C language standard does not require tail-call optimization. Assumption: Whether a compiler optimizes tail calls is implementation- and build-option-dependent.
- When to prefer iteration
- If there is no clear base case or the recursion depth could be large, prefer loops to avoid stack overflow risk. For small, naturally recursive problems (trees, divide-and-conquer), recursion yields simpler, clearer code.
Formulas
For programming, remember these syntactic patterns and standard recurrences:
return_type function_name(parameter_list) { /* body */ }Meaning: Function definition syntax in C. Units: not applicable. Applies to all functions.if (base_condition) return base_value; else return combine(smaller_solution);Meaning: General recursion template with base and recursive case. Units: not applicable. Applies when designing recursive functions.unsigned long long fact(unsigned int n) { if (n <= 1) return 1ULL; return n * fact(n - 1); }Meaning: Pattern for single-branch linear recursion decreasing by 1. Units: not applicable. Applies to factorial-like problems.int sumDigits(unsigned int n) { if (n < 10) return n; return (n % 10) + sumDigits(n / 10); }Meaning: Pattern for splitting a problem into a head (last digit) and smaller subproblem (rest). Units: not applicable. Applies to digit-processing tasks.void hanoi(int n, char src, char aux, char dst) { if (n == 0) return; hanoi(n-1, src, dst, aux); /* move */ hanoi(n-1, aux, src, dst); }Meaning: Pattern for two recursive subcalls with a side-effect between. Units: not applicable. Applies to divide-and-conquer like Hanoi.T(n) = T(n − 1) + cMeaning: Time recurrence for linear recursion where each call does constant extra work. Units: time per operation (abstract). Applies to factorial, sum of digits.T(n) = T(n − 1) + T(n − 2) + cMeaning: Time recurrence for naive Fibonacci. Units: abstract time. Applies when two subproblems overlap.T(n) = 2·T(n − 1) + 1Meaning: Number of moves in Hanoi. Units: moves. Applies for Hanoi with n disks.Tail recursion: return f(smaller_input);Meaning: The recursive call is the last operation. Units: not applicable. Applies when transforming recursion to loop is possible.
Worked examples
- Program: Factorial using recursion (with overflow guard at 20!)
Complete C code:
#include <stdio.h>
unsigned long long fact(unsigned int n) {
if (n <= 1) return 1ULL; // base case: 0! = 1, 1! = 1
return n * fact(n - 1); // recursive case
}
int main(void) {
unsigned int n;
if (scanf("%u", &n) != 1) return 0;
if (n > 20) {
printf("Error: n>20 causes overflow in unsigned long long.\n");
return 0;
}
printf("%llu\n", fact(n));
return 0;
}
Sample input:
5
Exact output:
120
Notes: 20! fits in unsigned long long; 21! does not. Time complexity is O(n); space complexity is O(n) due to call stack depth.
- Program: Sum of digits of a non-negative integer using recursion
Complete C code:
#include <stdio.h>
int sumDigits(unsigned int n) {
if (n < 10) return (int)n; // base case: single digit
return (int)(n % 10) + sumDigits(n / 10); // recursive case: last digit + sum of rest
}
int main(void) {
unsigned int n;
if (scanf("%u", &n) != 1) return 0;
printf("%d\n", sumDigits(n));
return 0;
}
Sample input:
2048
Exact output:
14
Notes: Works for any unsigned int input. Time complexity is O(d) where d is the number of digits; stack depth is also O(d).
- Program: Tower of Hanoi moves using recursion
Complete C code:
#include <stdio.h>
void hanoi(int n, char src, char aux, char dst) {
if (n == 0) return; // base: no disks -> no moves
hanoi(n - 1, src, dst, aux); // move top n-1 from src to aux
printf("%c -> %c\n", src, dst); // move largest from src to dst
hanoi(n - 1, aux, src, dst); // move n-1 from aux to dst
}
int main(void) {
int n;
if (scanf("%d", &n) != 1) return 0;
if (n < 0) return 0; // ignore negative cases
hanoi(n, 'A', 'B', 'C');
return 0;
}
Sample input:
3
Exact output:
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
Notes: Number of lines equals 2^n − 1; time complexity is O(2^n); recursion depth is O(n).
Model theory question example (how to answer succinctly):
- Question: "Explain with a recursion tree and a stack diagram how the recursive factorial works for n=4. Prove its correctness and find time complexity."
- Model answer outline: Define factorial recursively; draw stack diagram as described above; show recursion tree with nodes labeled fact(4), fact(3), …, fact(1); prove correctness by induction on n; establish T(n) = T(n−1)+c ⇒ T(n) ∈ O(n). Conclude with space complexity O(n).
Common mistakes
- Not making progress toward the base case (e.g., calling f(n) inside f(n) without decreasing n).
- Changing the parameter after the recursive call rather than before, causing infinite recursion or wrong answers.
- Assuming C always optimizes tail recursion; writing deep tail-recursive code and expecting constant stack space.
- Using types too small for results (e.g., int for 20! or Fibonacci numbers), causing overflow.
- Printing prompts in exam code but not matching sample I/O exactly; or mixing input parsing with leftover newlines.
- Forgetting to return the combined result (e.g., computing recursive call but not adding/multiplying with current contribution).
- Using global variables unintentionally across recursive calls, causing state to leak between branches.
- Mislabeling pegs or order in Tower of Hanoi, breaking the constraint "never place a larger disk on a smaller one".
For your exam
- Short notes: Call stack and activation record; recursion tree; advantages and disadvantages of recursion vs iteration. Include a labeled diagram description for the stack.
- Derivations: Derive T(n) for factorial, Fibonacci, and Hanoi; solve Hanoi recurrence to 2^n − 1 by induction; argue O(n), O(φ^n), O(2^n) complexities respectively. State assumptions clearly.
- Programs: Write and dry-run recursive factorial, power function (x^n), sum of digits, GCD (Euclid’s algorithm), binary search (recursive), Tower of Hanoi. Include base and recursive cases, correct types, and sample I/O.
- Diagrams: Draw the recursion tree for Fibonacci(5) and the stack frames for factorial(4). Label nodes (function name and argument) and show return flow.
- What full marks answers include: Correct base and recursive cases; termination argument; clear, minimal code that compiles; correct sample input and exact output; a brief complexity analysis; and a neat, labeled diagram when requested.
Quick check
- Define tail recursion and state whether the C standard guarantees tail-call optimization.
- Write the base case and recursive case for sum of digits of a non-negative integer n.
- State the recurrence and closed-form solution for the number of moves in Tower of Hanoi with n disks.
Answers: (1) Tail recursion: the recursive call is the last operation in the function; the C standard does not guarantee tail-call optimization. (2) Base: if n < 10 return n; Recursive: return (n % 10) + sumDigits(n / 10). (3) T(1) = 1; T(n) = 2·T(n−1) + 1 for n ≥ 2; solution T(n) = 2^n − 1.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?