PadhaikoAll subjects

Recursion

Data Structure and Algorithms (ENCT 252)

Open in the Padhaiko app

2.4 Recursion

2.4.1 Concept of recursion

Definition

Recursion

Recursion is a problem-solving and programming technique in which a function calls itself—either directly or indirectly—to solve smaller instances of the same problem until a trivial base problem is reached.

Every valid recursive function requires two essential parts:

  1. Base Case: A non-recursive terminating condition whose answer is known directly. Without a reachable base case, the function recurses indefinitely until the call stack overflows.
  2. Recursive Case: A self-call operating on a strictly smaller or simpler subproblem that converges monotonically toward the base case.
Recursive Factorial Function in CC
int factorial(int n) {
    if (n <= 1)             /* Base case: 0! = 1, 1! = 1 */
        return 1;
    return n * factorial(n - 1);   /* Recursive case */
}

Mathematically, this mirrors the recurrence relation:

2.4.2 Recursion and stack

When a program invokes a function, the CPU and runtime system allocate an activation record (stack frame) on the system call stack. Each stack frame stores:

Because the most recently invoked recursive call must finish and return first before its caller can resume, function calls strictly follow LIFO order—making the stack the exact data structure required to execute recursion.

Call Stack Frame Layout During factorial(3)Text
  Top -> +-----------------------------+
         | factorial(1): returns 1     |  <-- Base case reached
         +-----------------------------+
         | factorial(2): 2 * [pending] |  <-- Waits for factorial(1)
         +-----------------------------+
         | factorial(3): 3 * [pending] |  <-- Waits for factorial(2)
         +-----------------------------+
         | main()                      |
         +-----------------------------+

If recursion depth exceeds the fixed call-stack limit (for example, due to a missing base case or nested calls), the program terminates with a Stack Overflow.

2.4.3 Recursion vs iteration

Both recursion and iteration (for, while, do-while loops) repeat computations, yet they trade memory and call overhead against structural clarity.

Iterative Factorial Function in CC
int factorial_iter(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}
AspectRecursionIteration
MechanismFunction calls itself repeatedlyLoop constructs (for, while, do-while) repeat a code block
Memory Usage stack frames for recursion depth fixed memory (single set of loop variables)
Execution SpeedSlower due to stack-frame creation, argument passing, and return jumpsFaster with zero function-call overhead
TerminationStops when the base case is satisfiedStops when the loop condition becomes false
Code ClarityConcise and natural for trees, DFS, Divide & Conquer, TOHStraightforward for linear counting; complex for branching problems
Failure ModeStack Overflow on excessive depth or missing base caseInfinite loop if loop variable does not progress

2.4.4 Execution of recursive calls

Every non-tail recursive call executes in two distinct phases:

  1. Winding (Calling) Phase: Execution moves downward from the initial call toward the base case, pushing a new activation record onto the call stack at each call. Statements written before the recursive call execute during winding.
  2. Unwinding (Returning) Phase: Once the base case returns a concrete value, frames are popped one by one from the stack in LIFO order. Each caller completes its pending operations (such as n * returned_value) and statements written after the recursive call execute during unwinding.

2.4.5 Types of recursions

Recursive functions are categorized by how they call themselves and where the recursive call appears:

Definition

Classification of Recursion

  1. Direct Recursion: A function f() calls itself directly inside its own body (f() -> f()).
  2. Indirect (Mutual) Recursion: Function f() calls another function g(), which in turn calls f() (f() -> g() -> f()).
  3. Tail Recursion: The recursive call is the very last operation executed in the function, leaving no pending computation after the call returns. Because nothing remains to be done in the caller's frame, optimizing compilers can replace the call with a loop jump (Tail Call Optimization, stack space).
  4. Non-Tail (Head) Recursion: Further work (such as multiplication or addition) remains to be performed after the recursive call returns (e.g., return n * factorial(n - 1);).
  5. Tree Recursion: A function makes two or more recursive calls within its body, creating a branching tree of calls whose total count often grows exponentially (e.g., naive fibonacci(n) or Tower of Hanoi).
Tail Recursion vs. Tree Recursion in CC
/* Tail recursion: accumulator carries the partial product */
int tail_factorial(int n, int acc) {
    if (n <= 1)
        return acc;
    return tail_factorial(n - 1, n * acc);   /* Last operation: no pending work */
}

/* Tree recursion: two recursive calls per invocation */
int fibonacci(int n) {
    if (n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
Tail Recursion vs. Tree Recursion
FeatureTail RecursionTree Recursion
Recursive Calls per FrameSingle call as the final statementMultiple calls inside the function body
Call StructureLinear chain of callsBranching tree of calls
Stack Memory with tail-call optimization; otherwise stack depth; exponential total calls
Typical ExamplesTail-recursive factorial, Euclid's gcd(a, b)Recursive fibonacci(n), Tower of Hanoi, tree traversals

2.4.6 Applications of recursion: Tower of Hanoi

The Tower of Hanoi (TOH) is a classic recursive puzzle demonstrating how a multi-step problem decomposes cleanly into smaller identical subproblems.

Problem Setup and Rules

Recursive Algorithm for Disks

  1. Base Case (): Move the single disk directly from S to D.
  2. Recursive Case ():
    • Recursively move the top disks from S to I using D as auxiliary: TOH(n - 1, S, I, D).
    • Move the largest (-th) disk directly from S to D.
    • Recursively move the disks from I to D using S as auxiliary: TOH(n - 1, I, D, S).
Recursive Tower of Hanoi Program in CC
#include <stdio.h>

void TOH(int n, char S, char D, char I) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", S, D);
        return;
    }
    TOH(n - 1, S, I, D);
    printf("Move disk %d from %c to %c\n", n, S, D);
    TOH(n - 1, I, D, S);
}

int main(void) {
    int n = 3;
    TOH(n, 'A', 'C', 'B');
    return 0;
}

Minimum Number of Moves

Each call with disks performs two sub-calls of size plus direct disk move, giving the recurrence:

Unrolling this recurrence yields moves ( time, call-stack space).

Other major applications of recursion include tree and graph traversals (pre-order, in-order, post-order, DFS), divide-and-conquer sorting (Merge Sort, Quick Sort), backtracking puzzles (-Queens, Sudoku), and dynamic programming.


Worked Examples

Example 1

1

Trace the call stack (winding and unwinding phases) for factorial(4) using the recursive definition factorial(n) = n * factorial(n - 1) with base case factorial(1) = 1.

Winding phase (pushing activation records onto the stack): Each call pauses at n * factorial(n - 1) and pushes a new frame until n == 1:

  1. main() calls factorial(4) frame (n = 4, pending: 4 * ?) pushed.
  2. factorial(4) calls factorial(3) frame (n = 3, pending: 3 * ?) pushed.
  3. factorial(3) calls factorial(2) frame (n = 2, pending: 2 * ?) pushed.
  4. factorial(2) calls factorial(1) frame (n = 1) pushed; base case met, returns 1.

Unwinding phase (popping frames in LIFO order):

Call Stack Winding & Unwinding Trace for factorial(4)
EventActive Stack Frames (bottom -> top)Returned Value
Push factorial(4)[main, fac(4)]—
Push factorial(3)[main, fac(4), fac(3)]—
Push factorial(2)[main, fac(4), fac(3), fac(2)]—
Push factorial(1) (base)[main, fac(4), fac(3), fac(2), fac(1)]1
Pop fac(1) resume fac(2)[main, fac(4), fac(3), fac(2)]2 * 1 = 2
Pop fac(2) resume fac(3)[main, fac(4), fac(3)]3 * 2 = 6
Pop fac(3) resume fac(4)[main, fac(4)]4 * 6 = 24
Pop fac(4) resume main[main]24
Answer:

factorial(4) reaches a peak stack depth of frames beyond main() and returns .

Example 2

2

Construct the recursion tree for fibonacci(5) (with base cases fibonacci(0) = 0 and fibonacci(1) = 1), determine the returned value, and count the total number of function calls made.

Drawing the tree-recursion call structure: Each node F(k) with branches into F(k - 1) on the left and F(k - 2) on the right:

Recursion Tree for fibonacci(5)Text
                        F(5)
                      /      \
                  F(4)        F(3)
                 /    \      /    \
             F(3)     F(2)  F(2)  F(1)
            /    \    /  \   /  \
         F(2)  F(1) F(1) F(0) F(1) F(0)
         /  \
      F(1)  F(0)

Counting calls per argument value:

  • F(5): call
  • F(4): call
  • F(3): calls
  • F(2): calls
  • F(1): calls (each returns )
  • F(0): calls (each returns )

Total calls calls.

Evaluating bottom-up from the leaves:

Answer:

fibonacci(5) returns and requires total function calls (demonstrating redundant subproblem evaluations such as F(2) computed times).

Example 3

3

Construct the recursion tree and show the complete sequence of disk moves for the Tower of Hanoi problem with disks moving from rod A (Source) to rod C (Destination) via rod B (Auxiliary).

Building the recursion tree for TOH(3, A, C, B): In TOH(n, S, D, I), the left branch executes TOH(n - 1, S, I, D), the middle prints the move of disk n from S to D, and the right branch executes TOH(n - 1, I, D, S):

Recursion Tree for TOH(3, A, C, B)Text
                          TOH(3, A->C, aux B)
                        /          |          \
         TOH(2, A->B, C)     [Move 3: A->C]     TOH(2, B->C, A)
         /      |      \                        /      |      \
  TOH(1,A->C) [2:A->B] TOH(1,C->B)       TOH(1,B->A) [2:B->C] TOH(1,A->C)

Tracing all moves in execution order (in-order traversal of the tree):

Tower of Hanoi Move Trace for n = 3 Disks
Move #Disk MovedActionRod ARod BRod C
Initial—Start configuration[3, 2, 1][][]
Disk A -> C[3, 2][][1]
Disk A -> B[3][2][1]
Disk C -> B[3][2, 1][]
Disk A -> C[][2, 1][3]
Disk B -> A[1][2][3]
Disk B -> C[1][][3, 2]
Disk A -> C[][][3, 2, 1]
Answer:

All disks move from rod A to rod C in moves: 1: A->C, 2: A->B, 1: C->B, 3: A->C, 1: B->A, 2: B->C, 1: A->C.


Exercises

Exercises

Question 1

Explain how a recursive algorithm uses the stack data structure to manage intermediate states, illustrating your answer with the calculation of factorial(5).

Role of the call stack in recursion: Each recursive invocation creates a new activation record on the runtime call stack holding the parameter n, local variables, and the return address. Because inner calls must finish before outer callers can multiply by n, frames are pushed during the winding phase and popped in LIFO order during the unwinding phase.

Stack trace for factorial(5):

  • Winding (pushes): fac(5) fac(4) fac(3) fac(2) fac(1) (peak depth: frames).
  • Base case: fac(1) returns 1.
  • Unwinding (pops):
    • fac(2) computes and returns 2.
    • fac(3) computes and returns 6.
    • fac(4) computes and returns 24.
    • fac(5) computes and returns 120.
Answer:

The runtime call stack preserves each call's parameters and pending computations in LIFO activation records; factorial(5) pushes frames down to factorial(1) = 1 and unwinds to return .

Question 2

Distinguish between recursion and iteration. Write both recursive and iterative C functions to find the -th Fibonacci number () and compare their time and space efficiencies.

Key differences:

  • Control mechanism: Recursion uses self-calling functions and the call stack; iteration uses explicit loops (for/while) and local state variables.
  • Memory & overhead: Recursion consumes stack frames with function-call overhead; iteration uses space and executes faster.

C implementations:

Recursive vs. Iterative Fibonacci in CC
int fib_rec(int n) {
    if (n <= 1) return n;
    return fib_rec(n - 1) + fib_rec(n - 2);
}

int fib_iter(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c = 0;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Efficiency comparison:

  • fib_rec(n) recomputes overlapping subproblems exponentially, taking time and stack space.
  • fib_iter(n) computes each term once in a single loop, taking time and space.
Answer:

Recursive Fibonacci runs in time, stack space, whereas iterative Fibonacci runs in time, space without function-call overhead.

Question 3

Explain direct, indirect, tail, and tree recursion with a short C code snippet for each.

Definitions and C examples:

  1. Direct Recursion: A function calls itself directly (countdown(n) calls countdown(n - 1)).
  2. Indirect Recursion: even(n) calls odd(n - 1) and odd(n) calls even(n - 1).
  3. Tail Recursion: The recursive call is the final action with no pending arithmetic or post-processing.
  4. Tree Recursion: A function makes multiple recursive calls per invocation, creating a call tree.
Four Types of Recursion in CC
/* 1. Direct */
void countdown(int n) {
    if (n <= 0) return;
    printf("%d ", n);
    countdown(n - 1);
}

/* 2. Indirect */
int isOdd(int n);
int isEven(int n) { return (n == 0) ? 1 : isOdd(n - 1); }
int isOdd(int n)  { return (n == 0) ? 0 : isEven(n - 1); }

/* 3. Tail */
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

/* 4. Tree */
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
Answer:

Direct recursion calls itself (countdown), indirect recursion cycles across functions (isEven/isOdd), tail recursion makes the recursive call its final operation (gcd), and tree recursion spawns two or more recursive branches (fib).

Question 4

Draw the recursion tree for fibonacci(4) (where fibonacci(0) = 0, fibonacci(1) = 1), and find both the final value and the total number of function calls.

Constructing the recursion tree for F(4):

Recursion Tree for fibonacci(4)Text
                 F(4)
               /      \
           F(3)        F(2)
          /    \      /    \
       F(2)   F(1)  F(1)   F(0)
       /  \
    F(1)  F(0)

Counting calls and evaluating bottom-up:

  • Calls: F(4) (), F(3) (), F(2) (), F(1) (), F(0) () total calls.
  • Values: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2, F(4) = 2 + 1 = 3.
Answer:

fibonacci(4) returns and executes total function calls.

Question 5

Write the recursive algorithm for the Tower of Hanoi (TOH) problem with disks, derive the recurrence for the minimum number of disk moves , and calculate the exact number of moves required for disks.

Recursive TOH algorithm:

  1. If , move disk from S to D and return.
  2. Recursively move disks from S to I using D.
  3. Move disk from S to D.
  4. Recursively move disks from I to D using S.

Deriving the move-count formula :

Computing for disks:

Answer:

The Tower of Hanoi requires moves; for disks, moves are required.

Question 6

Convert the non-tail recursive function sumN(n) (which computes ) into a tail-recursive C function using an accumulator, and compute the result for . Why does tail recursion allow stack space under compiler optimization?

Comparing non-tail and tail-recursive versions in C:

Non-Tail vs. Tail-Recursive Sum of First n Natural NumbersC
/* Non-tail recursive: addition happens AFTER recursive call returns */
int sumN_nontail(int n) {
    if (n <= 0) return 0;
    return n + sumN_nontail(n - 1);
}

/* Tail recursive: accumulator holds running total; no pending operation */
int sumN_tail(int n, int acc) {
    if (n <= 0) return acc;
    return sumN_tail(n - 1, acc + n);
}

Tracing sumN_tail(10, 0) and tail-call optimization:

  • Calling sumN_tail(10, 0) passes (9, 10) -> (8, 19) -> ... -> (0, 55), returning 55 (matching ).
  • Because no arithmetic or state update occurs after sumN_tail(n - 1, acc + n) returns, an optimizing compiler overwrites the current stack frame's parameters (n = n - 1, acc = acc + n) and jumps back to the start of the function—reusing a single frame ( stack space).
Answer:

The tail-recursive function sumN_tail(n, acc) returns acc when and otherwise returns sumN_tail(n - 1, acc + n). For , sumN_tail(10, 0) returns ; with tail-call optimization, the compiler reuses the same stack frame in space.

Past exam questions for Data Structure and Algorithms

← Definition of stack and its operations · Array implementation of…Queues →