📘 Unit II: Recursion

Complete Teaching Notes | BCA / BIT / MCA / BSc.CSIT

From a Teacher's Perspective — Theory + Programs + Exam Q&A

Unit Objectives:

Discuss the principles and characteristics of recursion.

Apply recursion to solve problems and implement algorithms efficiently.

🎓 Teacher's Note to Students

Before we begin Unit II, understand this:

Recursion is not just a programming technique — it is a way of thinking.

Many beginners fear recursion because it seems like "a function calling itself — won't it run forever?" The answer lies in one simple concept: every recursive call must move toward a stopping condition. Once you internalize that, recursion becomes one of the most elegant tools in your programming toolkit.

We will build from the ground up:

First, understand what recursion is (concepts).
Then understand why it works (principles).
Then see how it works (types and examples with stack trace).
Finally, understand where to apply it (applications).

2.1 Introduction to Recursion

What is Recursion?

In everyday life, recursion appears everywhere:

A mirror facing another mirror — creates infinite reflections.
Russian nesting dolls (Matryoshka) — open a doll to find a smaller doll inside.
A dictionary that defines a word using another word that eventually refers back.

In programming:

Recursion is a process in which a function calls itself directly or indirectly in order to solve a problem by breaking it into smaller subproblems of the same type.

A function that calls itself is called a recursive function.

The Classic Mental Model

Imagine you are standing in a line and you want to know what position you are at. You ask the person in front of you — they ask the person in front of them — and so on, until the first person says "I am at position 1." Then the answers come back: position 2, 3, 4... and finally you know your position.

That is recursion:

Each person delegates the problem to someone else (recursive call).
The first person knows the answer directly (base case).
Answers bubble back through the chain (returning values).

Recursion vs Iteration

Aspect	Recursion	Iteration
Mechanism	Function calls itself	Uses loop (for/while)
Termination	Base case	Loop condition becomes false
Code size	Generally shorter, elegant	Can be longer
Memory	Uses call stack (extra space)	O(1) auxiliary space
Speed	Slightly slower (function call overhead)	Generally faster
Problem type	Problems with recursive structure	Straightforward repetition
Debugging	Harder to trace	Easier to trace
Example	Factorial, Fibonacci, TOH	Sum of array, printing numbers

How Recursion Works Internally — The Call Stack

Every time a function is called, the system allocates a stack frame in memory to store:

Local variables
Parameters
Return address

When a recursive function calls itself, a new stack frame is pushed. When it returns, the frame is popped.

Example: Factorial of 3

factorial(3)
    │
    ├─ calls factorial(2)
    │       │
    │       ├─ calls factorial(1)
    │       │       │
    │       │       ├─ calls factorial(0) → returns 1  [BASE CASE]
    │       │       └─ returns 1 × 1 = 1
    │       └─ returns 2 × 1 = 2
    └─ returns 3 × 2 = 6

Call Stack Visualization:

│ factorial(0) │ ← top (executes first, returns to factorial(1))
│ factorial(1) │
│ factorial(2) │
│ factorial(3) │ ← bottom (called first)
└──────────────┘
    STACK

2.2 Principle of Recursion

Every correct recursive solution is built on two fundamental principles:

Principle 1: Base Case (Termination Condition)

The base case is the condition under which the function stops calling itself and returns a direct answer.

Without a base case, recursion is infinite — just like a loop without an exit condition. The base case is the simplest, smallest version of the problem that can be solved directly.

Examples of base cases:

Factorial: if (n == 0) return 1;
Fibonacci: if (n <= 1) return n;
Array sum: if (index == n) return 0;
TOH: if (n == 1) move disk directly;

Principle 2: Recursive Case (Making Progress)

The recursive case is where the function calls itself with a modified (simpler/smaller) input, moving closer to the base case with each call.

If the recursive call does not reduce the problem size, it will never reach the base case and will result in infinite recursion → Stack Overflow.

The Three Laws of Recursion

A recursive algorithm must have a base case.
A recursive algorithm must change its state and move toward the base case.
A recursive algorithm must call itself, recursively.

Characteristics of a Good Recursive Solution

Characteristic	Description
Correctness	Solves the problem accurately
Termination	Always reaches the base case
Progress	Each call reduces problem size
Trust	You assume the recursive call works correctly (Inductive Step)
Efficiency	No unnecessary recomputation (use memoization if needed)

The "Leap of Faith" Concept (For Students)

One of the hardest parts of learning recursion is trusting it. When you write:

int factorial(int n) {
    return n * factorial(n - 1);  // I trust this works for n-1
}

You must take a leap of faith — assume factorial(n-1) correctly returns (n-1)!. Your job is only to define the relationship: factorial(n) = n × factorial(n-1). The computer handles the rest through the call stack.

Recurrence Relations

Recursion is often expressed as a recurrence relation — a mathematical definition of a function in terms of itself.

Function	Recurrence Relation	Base Case
Factorial	T(n) = n × T(n-1)	T(0) = 1
Fibonacci	F(n) = F(n-1) + F(n-2)	F(0)=0, F(1)=1
Binary Search	T(n) = T(n/2) + O(1)	T(1) = O(1)
Merge Sort	T(n) = 2T(n/2) + O(n)	T(1) = O(1)

2.3 Types of Recursion

Recursion is not a single concept — it has several types based on how the function calls itself and the structure of those calls.

2.3.1 Direct Recursion

Direct recursion occurs when a function calls ITSELF directly within its own body.

This is the most common and straightforward form of recursion.

Structure:

Function A → calls → Function A (itself)

Example — Factorial (Direct Recursion):

C Program:

#include <stdio.h>

int factorial(int n) {
    // Base case
    if (n == 0 || n == 1)
        return 1;
    // Recursive case: calls itself directly
    return n * factorial(n - 1);
}

int main() {
    int num = 5;
    printf("Factorial of %d = %d\n", num, factorial(num));
    return 0;
}
// Output: Factorial of 5 = 120

Java Program:

public class DirectRecursion {

    static int factorial(int n) {
        // Base case
        if (n == 0 || n == 1)
            return 1;
        // Recursive case
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        int num = 5;
        System.out.println("Factorial of " + num + " = " + factorial(num));
    }
}
// Output: Factorial of 5 = 120

Trace of factorial(4):

factorial(4)
  = 4 × factorial(3)
      = 4 × 3 × factorial(2)
          = 4 × 3 × 2 × factorial(1)
              = 4 × 3 × 2 × 1   [BASE CASE: factorial(1) = 1]
          = 4 × 3 × 2
      = 4 × 6
  = 24

2.3.2 Indirect Recursion

Indirect recursion (also called mutual recursion) occurs when function A calls function B, and function B calls function A — forming a cycle of calls that eventually terminates.

Structure:

Function A → calls → Function B → calls → Function A → ...

This can also extend to longer chains:

A → B → C → A → B → C → ... (until base case)

Example — Checking Even/Odd using Indirect Recursion:

C Program:

#include <stdio.h>

// Forward declaration (needed in C)
int isOdd(int n);

int isEven(int n) {
    if (n == 0)
        return 1;           // 0 is even — BASE CASE
    return isOdd(n - 1);    // calls isOdd
}

int isOdd(int n) {
    if (n == 0)
        return 0;           // 0 is not odd — BASE CASE
    return isEven(n - 1);   // calls isEven
}

int main() {
    printf("Is 4 even? %s\n", isEven(4) ? "Yes" : "No");
    printf("Is 5 odd?  %s\n", isOdd(5)  ? "Yes" : "No");
    return 0;
}
// Output:
// Is 4 even? Yes
// Is 5 odd?  Yes

Java Program:

public class IndirectRecursion {

    static int isEven(int n) {
        if (n == 0) return 1;        // Base case
        return isOdd(n - 1);
    }

    static int isOdd(int n) {
        if (n == 0) return 0;        // Base case
        return isEven(n - 1);
    }

    public static void main(String[] args) {
        System.out.println("Is 6 even? " + (isEven(6) == 1 ? "Yes" : "No"));
        System.out.println("Is 7 odd?  " + (isOdd(7)  == 1 ? "Yes" : "No"));
    }
}

Trace of isEven(4):

isEven(4)
  → isOdd(3)
      → isEven(2)
          → isOdd(1)
              → isEven(0)
                  → returns 1  [BASE CASE: 0 is even]
              → returns 1
          → returns 1
      → returns 1
  → returns 1     ✓ (4 is even)

2.3.3 Linear Recursion

Linear recursion (also called single recursion) is when a function makes EXACTLY ONE recursive call per invocation.

Each level of recursion generates exactly one more call — forming a single chain (linear structure) rather than a branching tree.

Structure:

f(n) → f(n-1) → f(n-2) → ... → f(base)
       (a straight line, not branching)

Characteristics:

At most one active recursive call at any time.
The recursion tree is a straight line.
Usually results in O(n) time complexity.
Stack depth = n.

Example — Linear Recursive Sum:

C Program:

#include <stdio.h>

int linearSum(int arr[], int n) {
    if (n == 0)                          // Base case
        return 0;
    return arr[n-1] + linearSum(arr, n-1);  // ONE recursive call
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;
    printf("Sum = %d\n", linearSum(arr, n));
    return 0;
}
// Output: Sum = 15

Java Program:

public class LinearRecursion {

    static int linearSum(int[] arr, int n) {
        if (n == 0)                            // Base case
            return 0;
        return arr[n - 1] + linearSum(arr, n - 1); // ONE recursive call
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println("Sum = " + linearSum(arr, arr.length));
    }
}
// Output: Sum = 15

Trace of linearSum({1,2,3,4,5}, 5):

linearSum(arr, 5) = arr[4] + linearSum(arr, 4)
                  = 5 + arr[3] + linearSum(arr, 3)
                  = 5 + 4 + arr[2] + linearSum(arr, 2)
                  = 5 + 4 + 3 + arr[1] + linearSum(arr, 1)
                  = 5 + 4 + 3 + 2 + arr[0] + linearSum(arr, 0)
                  = 5 + 4 + 3 + 2 + 1 + 0  [BASE CASE]
                  = 15

Contrast with Binary Recursion (like Fibonacci):

Linear:  f(n) → f(n-1) → f(n-2) → ... [straight chain]
Binary:  f(n) → f(n-1) AND f(n-2)      [branches into TWO calls]

2.3.4 Tail Recursion

Tail recursion is a special case of linear recursion where the RECURSIVE CALL IS THE VERY LAST OPERATION performed by the function — nothing happens after the recursive call returns.

This is critically important because:

A tail-recursive function can be optimized by the compiler into a loop (Tail Call Optimization — TCO). No new stack frame is needed because the current frame can be reused, giving O(1) stack space instead of O(n).

Structure:

Tail Recursive:     return recursiveCall(args);     ← last thing
NOT Tail Recursive: return n * recursiveCall(args); ← multiplication AFTER call

Example 1 — Non-Tail vs Tail Factorial:

Non-Tail Recursive (regular):

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);   // MULTIPLICATION after recursive call
    // After factorial(n-1) returns, we STILL need to multiply by n
    // So the stack frame MUST be preserved → O(n) stack space
}

Tail Recursive (with accumulator):

#include <stdio.h>

// Accumulator carries the result forward
int factTail(int n, int acc) {
    if (n == 0) return acc;           // Base case: return accumulated result
    return factTail(n - 1, n * acc);  // Recursive call IS the last operation
    // Nothing happens after this return — no pending computation
}

int factorial(int n) {
    return factTail(n, 1);   // Start with accumulator = 1
}

int main() {
    printf("Factorial of 5 = %d\n", factorial(5));
    return 0;
}
// Output: Factorial of 5 = 120

Java Program:

public class TailRecursion {

    // Tail recursive version with accumulator
    static int factTail(int n, int acc) {
        if (n == 0) return acc;
        return factTail(n - 1, n * acc);  // Last operation is the call
    }

    static int factorial(int n) {
        return factTail(n, 1);
    }

    // Tail recursive sum
    static int sumTail(int n, int acc) {
        if (n == 0) return acc;
        return sumTail(n - 1, acc + n);   // Last operation is the call
    }

    public static void main(String[] args) {
        System.out.println("Factorial of 5 = " + factorial(5));
        System.out.println("Sum of 1 to 10 = " + sumTail(10, 0));
    }
}
// Output:
// Factorial of 5 = 120
// Sum of 1 to 10 = 55

Trace of factTail(4, 1):

factTail(4, 1)   → factTail(3, 4×1) = factTail(3, 4)
factTail(3, 4)   → factTail(2, 3×4) = factTail(2, 12)
factTail(2, 12)  → factTail(1, 2×12) = factTail(1, 24)
factTail(1, 24)  → factTail(0, 1×24) = factTail(0, 24)
factTail(0, 24)  → return 24  [BASE CASE]

Notice: Each call's result is directly passed to the next. No pending operations. The compiler can optimize this into a loop.

Stack Comparison:

Non-Tail (factorial(4)):              Tail (factTail(4,1)):
│ factorial(0) │ ← pop first          factTail(4,1)
│ factorial(1) │                      factTail(3,4)
│ factorial(2) │                      factTail(2,12)
│ factorial(3) │                      factTail(1,24)
│ factorial(4) │ ← pushed first       factTail(0,24) → 24
└──────────────┘                      (Compiler converts to loop!)
    5 frames                           1 frame (with TCO)

Summary of Recursion Types

Type	Description	Structure	Example
Direct	Function calls itself	A → A → A	Factorial, Fibonacci
Indirect	A calls B, B calls A	A → B → A	Even/Odd check
Linear	Exactly one recursive call	A→A→A (chain)	Array sum, Factorial
Tail	Recursive call is last operation	Optimizable to loop	factTail with accumulator

2.4 Recursion Examples

2.4.1 Tower of Hanoi (TOH)

Background and Story

The Tower of Hanoi is a classic mathematical puzzle invented by French mathematician Édouard Lucas in 1883. It is one of the best examples to illustrate recursion because the recursive solution is elegant, short, and perfectly captures the recursive thinking process.

Problem Statement

Given n disks of different sizes stacked on a source peg (largest at bottom, smallest at top), and two other pegs (auxiliary and destination), move all n disks from the source to the destination peg following these rules:

Only one disk can be moved at a time.

A disk can only be placed on a larger disk or an empty peg.

Only the top disk of any peg can be moved.

Initial State (n=3):

Source (A)      Auxiliary (B)    Destination (C)
   [1]               |                 |
  [  2  ]            |                 |
 [    3    ]         |                 |
═══════════      ═══════════       ═══════════

Goal State:

Source (A)      Auxiliary (B)    Destination (C)
    |                |               [1]
    |                |             [  2  ]
    |                |           [    3    ]
═══════════      ═══════════       ═══════════

Recursive Strategy

For n disks:

Move top (n-1) disks from Source to Auxiliary (using Destination as helper).
Move the nth (largest) disk from Source to Destination.
Move the (n-1) disks from Auxiliary to Destination (using Source as helper).

This IS recursion: "To move n disks, first move n-1 disks" — the problem reduces itself.

Recurrence:

T(1) = 1 move
T(n) = 2T(n-1) + 1 = 2ⁿ - 1 total moves

For n=3: 2³ - 1 = 7 moves

Trace for n=2 (Source=A, Auxiliary=B, Destination=C):

Step 1: Move disk 1 from A to B
Step 2: Move disk 2 from A to C
Step 3: Move disk 1 from B to C

State after each step:
Initial:   A: [1][2]   B: []   C: []
Step 1:    A: [2]      B: [1]  C: []
Step 2:    A: []       B: [1]  C: [2]
Step 3:    A: []       B: []   C: [1][2]  ✓

Trace for n=3 (7 moves):

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

C Program:

#include <stdio.h>

int moveCount = 0;

void TOH(int n, char source, char auxiliary, char destination) {
    if (n == 1) {
        // BASE CASE: Move the single disk
        printf("Move disk 1 from %c to %c\n", source, destination);
        moveCount++;
        return;
    }
    // Step 1: Move top (n-1) disks from source to auxiliary
    TOH(n - 1, source, destination, auxiliary);

    // Step 2: Move the nth (largest) disk from source to destination
    printf("Move disk %d from %c to %c\n", n, source, destination);
    moveCount++;

    // Step 3: Move (n-1) disks from auxiliary to destination
    TOH(n - 1, auxiliary, source, destination);
}

int main() {
    int n = 3;
    printf("Tower of Hanoi with %d disks:\n\n", n);
    TOH(n, 'A', 'B', 'C');
    printf("\nTotal moves = %d (should be 2^%d - 1 = %d)\n",
           moveCount, n, (1 << n) - 1);
    return 0;
}

Output:

Tower of Hanoi with 3 disks:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Total moves = 7 (should be 2^3 - 1 = 7)

Java Program:

public class TowerOfHanoi {

    static int moveCount = 0;

    static void toh(int n, char source, char auxiliary, char destination) {
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + destination);
            moveCount++;
            return;
        }
        // Step 1: Move n-1 disks from source to auxiliary
        toh(n - 1, source, destination, auxiliary);

        // Step 2: Move the largest disk
        System.out.println("Move disk " + n + " from " + source + " to " + destination);
        moveCount++;

        // Step 3: Move n-1 disks from auxiliary to destination
        toh(n - 1, auxiliary, source, destination);
    }

    public static void main(String[] args) {
        int n = 3;
        System.out.println("Tower of Hanoi with " + n + " disks:\n");
        toh(n, 'A', 'B', 'C');
        System.out.println("\nTotal moves = " + moveCount);
    }
}

Recursion Tree for TOH(3, A, B, C):

                    TOH(3, A, B, C)
                   /               \
         TOH(2, A, C, B)          TOH(2, B, A, C)
          /          \             /          \
    TOH(1,A,B,C) TOH(1,C,A,B) TOH(1,B,C,A) TOH(1,A,B,C)

Analysis:

n (disks)	Moves (2ⁿ - 1)	Time
1	1	instant
2	3	instant
3	7	instant
10	1,023	instant
20	1,048,575	seconds
64	1.8 × 10¹⁹	585 billion years at 1 move/sec!

Time Complexity: O(2ⁿ) — exponential
Space Complexity: O(n) — recursion stack depth

2.4.2 Fibonacci Series

What is the Fibonacci Series?

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Mathematical Definition:

F(0) = 0               ← Base case 1
F(1) = 1               ← Base case 2
F(n) = F(n-1) + F(n-2) ← Recursive case (for n ≥ 2)

Occurrence in Nature: Petals of flowers, spirals in sunflowers and shells, branching of trees, rabbit population growth — Fibonacci is everywhere in nature. The ratio of consecutive Fibonacci numbers approaches the Golden Ratio (φ ≈ 1.618).

Method 1: Simple Recursive Fibonacci

C Program:

#include <stdio.h>

int fibonacci(int n) {
    // Two base cases
    if (n == 0) return 0;
    if (n == 1) return 1;
    // Recursive case: TWO recursive calls (Binary Recursion)
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n = 10;
    printf("Fibonacci Series (first %d terms):\n", n);
    for (int i = 0; i < n; i++) {
        printf("F(%d) = %d\n", i, fibonacci(i));
    }
    return 0;
}

Output:

Fibonacci Series (first 10 terms):
F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34

Java Program:

public class Fibonacci {

    static int fibonacci(int n) {
        if (n == 0) return 0;      // Base case 1
        if (n == 1) return 1;      // Base case 2
        return fibonacci(n - 1) + fibonacci(n - 2);  // Recursive case
    }

    public static void main(String[] args) {
        System.out.println("Fibonacci Series (first 10 terms):");
        for (int i = 0; i < 10; i++) {
            System.out.println("F(" + i + ") = " + fibonacci(i));
        }
    }
}

Recursion Tree for fibonacci(5):

                              fib(5)
                           /         \
                       fib(4)        fib(3)
                      /     \        /    \
                  fib(3)  fib(2)  fib(2)  fib(1)
                  /   \   /   \   /   \
              fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
              /   \
          fib(1) fib(0)

Problem: Redundant Computation!

fib(3) is computed TWICE
fib(2) is computed THREE times
fib(1) is computed FIVE times

This is terribly inefficient for large n!

Analysis of Naive Recursive Fibonacci

Case	Complexity
Time	O(2ⁿ) — exponential (due to repeated subproblems)
Space	O(n) — maximum recursion stack depth

Method 2: Memoized Recursive Fibonacci (Optimization)

Memoization stores computed results to avoid redundant work. This is called Dynamic Programming (top-down approach).

C Program with Memoization:

#include <stdio.h>
#include <string.h>

#define MAX 100
int memo[MAX];

int fibMemo(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1)        // Already computed? Return stored result
        return memo[n];
    memo[n] = fibMemo(n - 1) + fibMemo(n - 2);  // Compute and store
    return memo[n];
}

int main() {
    memset(memo, -1, sizeof(memo));   // Initialize all to -1
    printf("Fibonacci Series (Memoized):\n");
    for (int i = 0; i < 10; i++) {
        printf("F(%d) = %d\n", i, fibMemo(i));
    }
    return 0;
}

Java Program with Memoization:

import java.util.Arrays;

public class FibMemoized {

    static int[] memo = new int[100];

    static int fibMemo(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (memo[n] != -1)                  // Already computed
            return memo[n];
        memo[n] = fibMemo(n-1) + fibMemo(n-2);
        return memo[n];
    }

    public static void main(String[] args) {
        Arrays.fill(memo, -1);
        System.out.println("Fibonacci with Memoization:");
        for (int i = 0; i < 10; i++) {
            System.out.println("F(" + i + ") = " + fibMemo(i));
        }
    }
}

Memoized Tree for fib(5):

fib(5)
  → fib(4)
      → fib(3)
          → fib(2)
              → fib(1) = 1
              → fib(0) = 0
              memo[2] = 1
          → fib(1) = 1
          memo[3] = 2
      → fib(2) = 1 ← RETRIEVED FROM MEMO (not recomputed!)
      memo[4] = 3
  → fib(3) = 2 ← RETRIEVED FROM MEMO
  memo[5] = 5

With memoization: Time = O(n), Space = O(n) — drastically better!

Method 3: Tail Recursive Fibonacci

public class Main {

    // Tail recursive function
    public static int fibTail(int n, int a, int b) {
        if (n == 0) return a;
        if (n == 1) return b;

        return fibTail(n - 1, b, a + b);   // tail call
    }

    // Wrapper function
    public static int fibonacci(int n) {
        return fibTail(n, 0, 1);
    }

    public static void main(String[] args) {

        for (int i = 0; i < 10; i++) {
            System.out.println("F(" + i + ") = " + fibonacci(i));
        }
    }
}

Trace of fibTail(5, 0, 1):

fibTail(5, 0, 1) → fibTail(4, 1, 1)
fibTail(4, 1, 1) → fibTail(3, 1, 2)
fibTail(3, 1, 2) → fibTail(2, 2, 3)
fibTail(2, 2, 3) → fibTail(1, 3, 5)
fibTail(1, 3, 5) → returns 5  [BASE CASE]

Time: O(n), Space: O(1) with TCO.

Comparison of Fibonacci Implementations

Method	Time	Space	Redundant Calls
Naive Recursive	O(2ⁿ)	O(n)	Yes (many)
Memoized Recursive	O(n)	O(n)	No
Tail Recursive	O(n)	O(1) with TCO	No
Iterative	O(n)	O(1)	N/A

2.5 Applications of Recursion

Recursion is not just an academic exercise — it is used throughout real software, compilers, operating systems, and algorithms.

2.5.1 Mathematical Problems

Problem	Recursive Formula
Factorial	f(n) = n × f(n-1)
Power	pow(x, n) = x × pow(x, n-1)
GCD	gcd(a,b) = gcd(b, a mod b)
Sum of digits	sum(n) = n%10 + sum(n/10)
Palindrome check	check first & last, recurse on middle

Java Program — Power using Recursion:

public class Main {

    // Simple recursion → O(n)
    public static long power(int base, int exp) {
        if (exp == 0) return 1;   // x^0 = 1
        return base * power(base, exp - 1);
    }

    // Fast power (divide & conquer) → O(log n)
    public static long fastPower(int base, int exp) {
        if (exp == 0) return 1;

        if (exp % 2 == 0) {
            return fastPower(base * base, exp / 2);
        }

        return base * fastPower(base, exp - 1);
    }

    public static void main(String[] args) {
        System.out.println("2^10 = " + power(2, 10));      // 1024
        System.out.println("2^10 = " + fastPower(2, 10));  // 1024
    }
}

C Program — GCD (Euclidean Algorithm):

public class Main {

    public static int gcd(int a, int b) {
        if (b == 0) return a;     // Base case
        return gcd(b, a % b);     // Recursive case
    }

    public static void main(String[] args) {
        System.out.println("GCD(48, 18) = " + gcd(48, 18));
    }
}

2.5.2 Sorting Algorithms

Divide and conquer sorting algorithms are inherently recursive.

Merge Sort (covered in Unit I) — O(n log n), stable sort.

Quick Sort:

public class Main {

    // Partition function
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];   // choose last element as pivot
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // place pivot in correct position
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    // Quick Sort function
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);   // Left part
            quickSort(arr, pi + 1, high);  // Right part
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        int n = arr.length;

        quickSort(arr, 0, n - 1);

        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
// Output: 1 5 7 8 9 10

2.5.3 Searching Algorithms

Binary Search (Recursive):

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int key) {
    if (low > high) return -1;          // Base case: not found
    int mid = (low + high) / 2;
    if (arr[mid] == key) return mid;    // Base case: found
    if (key < arr[mid])
        return binarySearch(arr, low, mid - 1, key);
    return binarySearch(arr, mid + 1, high, key);
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int n = 7, key = 7;
    int result = binarySearch(arr, 0, n - 1, key);
    printf("Key %d found at index %d\n", key, result);
    return 0;
}
// Output: Key 7 found at index 3

Java Binary Search:

public class BinarySearch {

    static int binarySearch(int[] arr, int low, int high, int key) {
        if (low > high) return -1;
        int mid = (low + high) / 2;
        if (arr[mid] == key) return mid;
        if (key < arr[mid]) return binarySearch(arr, low, mid - 1, key);
        return binarySearch(arr, mid + 1, high, key);
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        System.out.println("Found at: " + binarySearch(arr, 0, arr.length-1, 7));
    }
}

2.5.4 Tree Operations

Almost all tree operations are naturally recursive:

Tree traversal (Inorder, Preorder, Postorder)
Tree height calculation
Searching in BST

// Tree height using recursion
int height(struct Node* root) {
    if (root == NULL) return 0;         // Base case
    int leftH  = height(root->left);   // Recurse left
    int rightH = height(root->right);  // Recurse right
    return 1 + (leftH > rightH ? leftH : rightH);
}

2.5.5 Other Applications

Application	How Recursion Helps
File system traversal	Recursively visit directories and subdirectories
Parsing expressions	Compilers use recursive descent parsers
Backtracking	N-Queens, Sudoku solver, maze solving
Fractals	Sierpinski triangle, Mandelbrot set (self-similar structure)
Graph algorithms	DFS (Depth First Search)
Divide & Conquer	Matrix multiplication (Strassen), FFT
Permutations/Combinations	Generating all arrangements
JSON/XML parsing	Nested structures are naturally recursive

2.5.6 String Reversal using Recursion

Java Program:

public class Main {

    public static void reverse(char[] str, int start, int end) {
        if (start >= end) return;   // Base case

        // swap characters
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;

        // recursive call
        reverse(str, start + 1, end - 1);
    }

    public static void main(String[] args) {
        String input = "RECURSION";

        // Convert string to char array (since Java strings are immutable)
        char[] str = input.toCharArray();

        reverse(str, 0, str.length - 1);

        System.out.println("Reversed: " + new String(str));
    }
}
// Output: Reversed: NOISRUCER

2.5.7 Palindrome Check using Recursion

Java Program:

public class Palindrome {

    static boolean isPalindrome(String s, int start, int end) {
        if (start >= end) return true;               // Base case
        if (s.charAt(start) != s.charAt(end)) return false; // Mismatch
        return isPalindrome(s, start + 1, end - 1); // Recurse inward
    }

    public static void main(String[] args) {
        String s = "RACECAR";
        System.out.println(s + " is palindrome: " +
            isPalindrome(s, 0, s.length() - 1));
        // Output: RACECAR is palindrome: true
    }
}

📝 Quick Reference Summary

RECURSION CHEAT SHEET
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
1. ALWAYS define a BASE CASE first
2. ALWAYS ensure progress toward base case
3. TRUST the recursive call (Leap of Faith)
4. Use MEMOIZATION to avoid redundant calls
5. Use TAIL RECURSION for memory optimization

Types:     Direct | Indirect | Linear | Tail
Examples:  TOH    | Fibonacci | Sorting | Searching

Complexities:
  Factorial  → O(n) time, O(n) space
  Fibonacci  → O(2ⁿ) time (naive), O(n) with memo
  TOH        → O(2ⁿ) time, O(n) space
  Binary Search → O(log n) time, O(log n) space
  Merge Sort → O(n log n) time, O(n) space
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

🧪 PRACTICAL QUESTIONS AND ANSWERS

Section A: Short Answer Questions (2-4 Marks)

Q1. What is recursion? State two differences between recursion and iteration.

Answer:

Recursion is a process in which a function calls itself, directly or indirectly, to solve a problem by breaking it into smaller subproblems of the same type until a base condition is reached.

Feature	Recursion	Iteration
Mechanism	Function calls itself	Loop structure
Termination	Base case	Loop condition
Memory	O(n) stack space	O(1) space
Speed	Slightly slower	Faster

Q2. What is a base case? Why is it necessary in recursion?

Answer:

A base case is the condition in a recursive function where the function stops calling itself and returns a direct (trivial) answer without further recursion.

It is necessary because:

Without a base case, the function calls itself infinitely.
Infinite recursion causes stack overflow — the call stack runs out of memory and the program crashes.
The base case provides the stopping condition that allows recursive calls to return and unwind.

Example: In factorial(n), the base case is if (n == 0) return 1;

Q3. Define tail recursion. Give one example.

Answer:

Tail recursion is a special form of recursion where the recursive call is the very last operation performed by the function — no computation is done after the recursive call returns.

Example — Tail Recursive Factorial:

public class Main {

    // Tail recursive function
    public static int factTail(int n, int acc) {
        if (n == 0) return acc;
        return factTail(n - 1, n * acc);   // tail call
    }

    // Wrapper method (user-friendly)
    public static int factorial(int n) {
        return factTail(n, 1);
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println("Factorial = " + factorial(n));
    }
}

Importance: Tail-recursive functions can be optimized by the compiler (Tail Call Optimization) to run in O(1) stack space instead of O(n).

Q4. What is indirect recursion? Give an example.

Answer:

Indirect recursion (mutual recursion) is when a function A calls function B, and function B calls function A, forming a cycle that eventually terminates at a base case.

Example:

int isEven(int n) {
    if (n == 0) return 1;
    return isOdd(n - 1);   // calls isOdd
}
int isOdd(int n) {
    if (n == 0) return 0;
    return isEven(n - 1);  // calls isEven
}

Q5. What are the advantages and disadvantages of recursion?

Answer:

Advantages:

Makes code shorter, cleaner, and easier to understand.
Naturally fits problems with recursive structure (trees, graphs, TOH).
Mirrors mathematical definitions directly.
Simplifies complex problems like sorting, searching, backtracking.

Disadvantages:

Uses additional memory (call stack) — O(n) space for n calls.
Slower than iterative due to function call overhead.
Risk of stack overflow for large inputs.
Harder to trace and debug compared to loops.
May perform redundant computations (e.g., naive Fibonacci).

Section B: Long Answer / Descriptive Questions (6-10 Marks)

Q6. Explain the Tower of Hanoi problem. Write a recursive algorithm/program to solve it. Trace for n=3. What is its time and space complexity?

Answer:

Problem: Move n disks from Source (A) to Destination (C) using Auxiliary (B), one disk at a time, never placing a larger disk on a smaller one.

Recursive Strategy:

Move n-1 disks from A to B (using C as helper).
Move disk n from A to C.
Move n-1 disks from B to C (using A as helper).

C Program:

public class Main {

    public static void TOH(int n, char src, char aux, char dest) {

        if (n == 1) {
            System.out.println("Move disk 1 from " + src + " to " + dest);
            return;
        }

        TOH(n - 1, src, dest, aux);
        System.out.println("Move disk " + n + " from " + src + " to " + dest);
        TOH(n - 1, aux, src, dest);
    }

    public static void main(String[] args) {
        TOH(3, 'A', 'B', 'C');
    }
}

Trace for n=3 (7 moves):

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Complexity:

Total moves = 2ⁿ - 1 → Time Complexity: O(2ⁿ)
Recursion stack depth = n → Space Complexity: O(n)

Q7. Write a recursive program in both C and Java to generate the Fibonacci series. Analyze its time complexity. How can it be optimized using memoization?

Answer:

Recurrence: F(0)=0, F(1)=1, F(n) = F(n-1) + F(n-2)

C Program (Naive):

#include <stdio.h>

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

int main() {
    for (int i = 0; i < 10; i++)
        printf("F(%d) = %d\n", i, fib(i));
    return 0;
}

Java Program (Naive):

public class Fib {
    static int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fib(n-1) + fib(n-2);
    }
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++)
            System.out.println("F(" + i + ") = " + fib(i));
    }
}

Time Complexity (Naive): O(2ⁿ) — Each call makes 2 calls, forming an exponential tree with 2ⁿ nodes.

Memoized Version (C):

#include <stdio.h>
#include <string.h>
int memo[100];

int fibMemo(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fibMemo(n-1) + fibMemo(n-2);
}

int main() {
    memset(memo, -1, sizeof(memo));
    for (int i = 0; i < 10; i++)
        printf("F(%d) = %d\n", i, fibMemo(i));
    return 0;
}

With Memoization: Time = O(n), Space = O(n) — Each value computed only once.

Q8. Differentiate between the four types of recursion with examples.

Answer:

Type	Definition	Example
Direct	A function calls itself	`factorial(n)` calls `factorial(n-1)`
Indirect	A calls B, B calls A	`isEven()` calls `isOdd()` and vice versa
Linear	Exactly one recursive call per execution	Array sum, factorial
Tail	Recursive call is the LAST statement	`factTail(n, acc)` — no pending work after call

Key Code Comparison:

// Direct Recursion
int f(int n) { return n * f(n-1); }   // calls itself

// Indirect Recursion
int A(int n) { return B(n-1); }       // A calls B
int B(int n) { return A(n-1); }       // B calls A

// Linear Recursion (one call only)
int sum(int n) { return n + sum(n-1); } // single recursive call

// Tail Recursion (call is the last operation)
int factT(int n, int a) { return factT(n-1, n*a); } // LAST statement

Section C: Practical / Coding Questions

Q9. Write a C program using recursion to: (a) Calculate the sum of digits of a number (b) Reverse a number

Answer:

public class Main {

    // (a) Sum of digits
    public static int sumDigits(int n) {
        if (n == 0) return 0;                 // Base case
        return (n % 10) + sumDigits(n / 10);  // Last digit + rest
    }

    // (b) Reverse of a number
    public static int reverseNum(int n, int rev) {
        if (n == 0) return rev;               // Base case
        return reverseNum(n / 10, rev * 10 + n % 10);
    }

    public static void main(String[] args) {
        int num = 1234;

        System.out.println("Sum of digits of " + num + " = " + sumDigits(num));
        System.out.println("Reverse of " + num + " = " + reverseNum(num, 0));
    }
}

Trace for sumDigits(1234):

sumDigits(1234) = 4 + sumDigits(123)
                = 4 + 3 + sumDigits(12)
                = 4 + 3 + 2 + sumDigits(1)
                = 4 + 3 + 2 + 1 + sumDigits(0)
                = 4 + 3 + 2 + 1 + 0 = 10

Q10. Write a Java program to print all permutations of a string using recursion.

Answer:

public class Permutations {

    static void permute(String str, int left, int right) {
        if (left == right) {
            System.out.println(str);   // BASE CASE: one permutation
            return;
        }
        for (int i = left; i <= right; i++) {
            str = swap(str, left, i);          // Swap
            permute(str, left + 1, right);     // Recurse
            str = swap(str, left, i);          // Backtrack (unswap)
        }
    }

    static String swap(String s, int i, int j) {
        char[] c = s.toCharArray();
        char temp = c[i]; c[i] = c[j]; c[j] = temp;
        return new String(c);
    }

    public static void main(String[] args) {
        String s = "ABC";
        System.out.println("Permutations of " + s + ":");
        permute(s, 0, s.length() - 1);
    }
}

Output:

Permutations of ABC:
ABC
ACB
BAC
BCA
CBA
CAB

Q11. Trace the Tower of Hanoi for n=2 showing all peg states at each step.

Answer:

Initial State:
A: [1][2]  (1 on top of 2)
B: []
C: []

Call: TOH(2, A, B, C)
  → TOH(1, A, C, B): Move disk 1 from A to B
    State: A:[2]  B:[1]  C:[]

  → Move disk 2 from A to C
    State: A:[]   B:[1]  C:[2]

  → TOH(1, B, A, C): Move disk 1 from B to C
    State: A:[]   B:[]   C:[1][2]

Final State:
A: []
B: []
C: [1][2]  ✓ All disks moved!

Total moves = 3 = 2² - 1

Q12. What will be the output of the following code? Trace the execution.

void mystery(int n) {
    if (n == 0) return;
    mystery(n - 1);
    printf("%d ", n);
}
// Call: mystery(4)

Answer:

This is a linear recursive function. The printf happens AFTER the recursive call (not tail recursive).

Trace:

mystery(4) → mystery(3) → mystery(2) → mystery(1) → mystery(0)
                                                      returns (base case)
                                         prints 1
                             prints 2
                 prints 3
mystery(4) prints 4

Output: 1 2 3 4

The print statements execute in REVERSE order of calls — this is because printf comes after the recursive call, so it executes during the "unwinding" phase. This is a classic example to understand stack behavior.

Compare: If printf were BEFORE the recursive call:

void mystery2(int n) {
    if (n == 0) return;
    printf("%d ", n);   // before recursive call
    mystery2(n - 1);
}
// Output: 4 3 2 1

📋 Possible Exam Questions at a Glance

#	Question	Marks
1	Define recursion and state its principle	2
2	Differentiate recursion and iteration	4
3	What is base case? Why is it important?	2
4	Explain types of recursion with examples	8
5	Explain tail recursion with code example	4
6	Explain Tower of Hanoi problem with n=3 trace	10
7	Write recursive Fibonacci program and analyze complexity	8
8	What is memoization? How does it optimize Fibonacci?	6
9	Compare recursive Fibonacci with memoized version	4
10	Write recursive binary search algorithm	6
11	Applications of recursion with examples	6
12	Trace the recursion tree for fib(5)	5
13	What is indirect recursion? Write a program to demonstrate	6
14	Write recursive program for sum of digits	4
15	Analyze space and time complexity of TOH	4

LAB

Describe the principles and types of recursion, then write recursive programs for factorial, sum of N natural numbers, Fibonacci Series, and Tower of Hanoi, including recursion tracing and complexity analysis.

End of Unit II — Recursion Complete Notes with Programs in C and Java, Traces, and Exam Q&A Prepared for: BCA / BIT / MCA / BSc.CSIT | Subject: Data Structures and Algorithms

Part - 2 Recursion, Data Structure And Algorithm

📘 Unit II: Recursion

Complete Teaching Notes | BCA / BIT / MCA / BSc.CSIT

From a Teacher's Perspective — Theory + Programs + Exam Q&A

🎓 Teacher's Note to Students

2.1 Introduction to Recursion

What is Recursion?

The Classic Mental Model

Recursion vs Iteration

How Recursion Works Internally — The Call Stack

2.2 Principle of Recursion

Principle 1: Base Case (Termination Condition)

Principle 2: Recursive Case (Making Progress)

The Three Laws of Recursion

Characteristics of a Good Recursive Solution

The "Leap of Faith" Concept (For Students)

Recurrence Relations

2.3 Types of Recursion

2.3.1 Direct Recursion

2.3.2 Indirect Recursion

2.3.3 Linear Recursion

2.3.4 Tail Recursion

Summary of Recursion Types

2.4 Recursion Examples

2.4.1 Tower of Hanoi (TOH)

Background and Story

Problem Statement

Recursive Strategy

2.4.2 Fibonacci Series

What is the Fibonacci Series?

Method 1: Simple Recursive Fibonacci

Recursion Tree for fibonacci(5):

Analysis of Naive Recursive Fibonacci

Method 2: Memoized Recursive Fibonacci (Optimization)

Method 3: Tail Recursive Fibonacci

Comparison of Fibonacci Implementations

2.5 Applications of Recursion

2.5.1 Mathematical Problems

2.5.2 Sorting Algorithms

2.5.3 Searching Algorithms

2.5.4 Tree Operations

2.5.5 Other Applications

2.5.6 String Reversal using Recursion

2.5.7 Palindrome Check using Recursion

📝 Quick Reference Summary

🧪 PRACTICAL QUESTIONS AND ANSWERS

Section A: Short Answer Questions (2-4 Marks)

Section B: Long Answer / Descriptive Questions (6-10 Marks)

Section C: Practical / Coding Questions

📋 Possible Exam Questions at a Glance

LAB