First Year Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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:

  1. 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.
  1. 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.
  1. 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.
  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).
  1. 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.
  1. 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) + c Meaning: 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) + c Meaning: Time recurrence for naive Fibonacci. Units: abstract time. Applies when two subproblems overlap.

  • T(n) = 2·T(n − 1) + 1 Meaning: 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

  1. 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.

  1. 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).

  1. 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

  1. Define tail recursion and state whether the C standard guarantees tail-call optimization.
  2. Write the base case and recursive case for sum of digits of a non-negative integer n.
  3. 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?