Unit 3: Recursion & Advanced Techniques

Opening Hook — The Invisible Power Behind Every Search

Learning Outcomes — Bloom's Taxonomy Mapped (12 Outcomes)

Concept Explanation — Recursion & Advanced Techniques from Scratch

1. Introduction to Recursion

Plain English: Recursion is when a function calls itself to solve a smaller version of the same problem. Imagine you're standing in a queue and want to know your position. You ask the person in front, "What's your position?" They ask the person in front of them, and so on — until the first person says "I'm #1." Then the answers cascade back: #2, #3, #4... That's recursion.

Technical Definition: A recursive function is a function that calls itself with modified arguments, working toward a base case that terminates the recursion. Every recursive function has exactly two components:

Factorial Example — The "Hello World" of Recursion

The factorial of n (written n!) is: n! = n × (n-1) × (n-2) × ... × 1, with 0! = 1.

C++
// Recursive Factorial in C++
#include <iostream>
using namespace std;

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

int main() {
    cout << "5! = " << factorial(5) << endl;
    return 0;
}

Python
# Recursive Factorial in Python
def factorial(n):
    # Base case
    if n == 0:
        return 1
    # Recursive case
    return n * factorial(n - 1)

print(f"5! = {factorial(5)}")

How the Call Stack Works — ASCII Stack Diagram

When factorial(4) is called, each recursive call is pushed onto the call stack. When the base case is reached, results pop back up:

2. Base Condition — The Emergency Brake of Recursion

The base case is the most critical part of any recursive function. It's the condition that says "STOP — don't call yourself again." Without it, the function calls itself infinitely until the program crashes.

What Happens Without a Base Case?

C++
// ❌ DANGEROUS: No base case!
void infinite(int n) {
    cout << n << " ";
    infinite(n - 1);  // Never stops!
}
// Output: 5 4 3 2 1 0 -1 -2 ... CRASH!
// Error: Stack Overflow (Segmentation Fault)

Stack Overflow Error: Each recursive call creates a new stack frame in memory. Without a base case, frames pile up endlessly until the stack memory is exhausted. On most systems, the default stack size is 1–8 MB, which allows roughly 10,000–100,000 recursive calls before crashing.

Rules for Writing Good Base Cases

3. Solving Problems Using Recursion

The Recursive Thinking Pattern: Every recursive solution follows this mental model:

1. Assume the recursive call magically gives the correct answer for a smaller input
2. Use that answer to build the solution for the current input
3. Define the base case where you know the answer directly

Problem 1: Fibonacci Numbers

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21... Each number is the sum of the two preceding ones.

C++
// Recursive Fibonacci
int fib(int n) {
    if (n <= 0) return 0;       // Base case 1
    if (n == 1) return 1;       // Base case 2
    return fib(n-1) + fib(n-2); // Recursive case
}

Python
# Recursive Fibonacci
def fib(n):
    if n <= 0: return 0
    if n == 1: return 1
    return fib(n-1) + fib(n-2)

Recursion Tree for fib(5)

Problem 2: Power(x, n) — Two Approaches

C++
// Naive: O(n) time
double power_naive(double x, int n) {
    if (n == 0) return 1;
    return x * power_naive(x, n - 1);
}

// Optimised: O(log n) time — using divide and conquer
double power_fast(double x, int n) {
    if (n == 0) return 1;
    double half = power_fast(x, n / 2);
    if (n % 2 == 0)
        return half * half;
    else
        return half * half * x;
}

Problem 3: Sum of Digits

Python
# Sum of digits of a number
def sum_digits(n):
    if n == 0: return 0             # Base case
    return (n % 10) + sum_digits(n // 10)  # Last digit + sum of rest

print(sum_digits(9876))  # 9+8+7+6 = 30

4. Classic and Modern Approaches

Classic Recursion: A function calls itself directly to solve progressively smaller instances. Examples: factorial, fibonacci, sum-of-digits. The pattern is straightforward — each call reduces the problem by a small amount (usually by 1).

Divide and Conquer: A more powerful pattern where the problem is split into independent subproblems of roughly equal size, solved recursively, and then combined. This often leads to O(n log n) algorithms instead of O(n²).

Binary Search — Recursive Version

C++
// Recursive Binary Search — O(log n)
int binarySearch(int arr[], int low, int high, int target) {
    if (low > high) return -1;        // Base case: not found
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid; // Found!
    if (arr[mid] > target)
        return binarySearch(arr, low, mid - 1, target);
    else
        return binarySearch(arr, mid + 1, high, target);
}

Python
# Recursive Binary Search
def binary_search(arr, low, high, target):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, low, mid - 1, target)
    else:
        return binary_search(arr, mid + 1, high, target)

5. Direct vs Indirect Recursion

Direct Recursion: A function calls itself directly. This is the most common form — factorial, fibonacci, binary search all use direct recursion.

Indirect Recursion: Function A calls function B, and function B calls function A back. The recursion happens through a chain of two or more functions.

Direct Recursion Example

C++
// Direct: function calls itself
void countdown(int n) {
    if (n == 0) {
        cout << "Go!" << endl;
        return;
    }
    cout << n << "... ";
    countdown(n - 1);  // Calls ITSELF
}

Indirect Recursion Example

C++
// Indirect: A calls B, B calls A
void funcB(int n);  // Forward declaration

void funcA(int n) {
    if (n <= 0) return;
    cout << n << " ";
    funcB(n - 1);   // A calls B
}

void funcB(int n) {
    if (n <= 1) return;
    cout << n << " ";
    funcA(n / 2);   // B calls A
}
// funcA(10) → prints: 10 9 4 3 1

6. Tail vs Non-Tail Recursion

Tail Recursion: A recursive call is in tail position when it is the very last operation in the function — nothing is done after the recursive call returns. Compilers can optimise tail-recursive functions into loops (called Tail-Call Optimisation / TCO), eliminating stack frame overhead.

Non-Tail Recursion: After the recursive call returns, there's still work to do (like multiplication in factorial). Each call must keep its stack frame alive until the child returns.

Comparison: Non-Tail vs Tail Factorial

C++
// NON-TAIL Recursive Factorial
// After factorial(n-1) returns, we still multiply by n
int factorial_nontail(int n) {
    if (n == 0) return 1;
    return n * factorial_nontail(n - 1);  // ❌ multiplication AFTER call
}

// TAIL Recursive Factorial
// The recursive call is the LAST operation — result is accumulated
int factorial_tail(int n, int acc = 1) {
    if (n == 0) return acc;
    return factorial_tail(n - 1, n * acc);  // ✅ call is LAST operation
}

Python
# Non-tail factorial
def fact_nontail(n):
    if n == 0: return 1
    return n * fact_nontail(n - 1)  # multiply AFTER return

# Tail factorial (Python doesn't optimise this, but conceptually correct)
def fact_tail(n, acc=1):
    if n == 0: return acc
    return fact_tail(n - 1, n * acc)  # call is LAST

7. Memory Allocation in Recursion

Every recursive call creates a new stack frame in the program's call stack. Each frame contains:

• Local variables of the function
• Function parameters
• Return address (where to go back after the function completes)
• Saved registers

Stack Frame Diagram for factorial(3)

Why Stack Overflow Happens: If n = 1,000,000 and you call factorial(1000000), the program needs 1 million stack frames × ~50 bytes each = ~50 MB. But the stack is only ~1 MB. Result: Stack Overflow — the program crashes.

8. Advantages & Disadvantages — Recursion vs Iteration

9. Backtracking

Backtracking is a refined form of recursion where you build a solution incrementally, one piece at a time, and abandon ("backtrack") a path as soon as you determine it cannot lead to a valid solution. Think of it as exploring a maze: walk forward, hit a dead end, go back to the last junction, try another path.

The N-Queens Problem

Problem: Place N queens on an N×N chessboard such that no two queens threaten each other (no two in the same row, column, or diagonal).

Complete Board Trace for 4-Queens

N-Queens Code

C++
#include <iostream>
#include <vector>
using namespace std;

bool isSafe(vector<vector<int>> &board, int row, int col, int n) {
    // Check column above
    for (int i = 0; i < row; i++)
        if (board[i][col]) return false;
    // Check upper-left diagonal
    for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--)
        if (board[i][j]) return false;
    // Check upper-right diagonal
    for (int i=row-1, j=col+1; i>=0 && j<n; i--, j++)
        if (board[i][j]) return false;
    return true;
}

bool solveNQueens(vector<vector<int>> &board, int row, int n) {
    if (row == n) return true;  // All queens placed!
    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col, n)) {
            board[row][col] = 1;           // Place queen
            if (solveNQueens(board, row+1, n))
                return true;
            board[row][col] = 0;           // BACKTRACK: remove queen
        }
    }
    return false;  // No valid position in this row
}

int main() {
    int n = 4;
    vector<vector<int>> board(n, vector<int>(n, 0));
    if (solveNQueens(board, 0, n)) {
        for (auto &row : board) {
            for (int cell : row)
                cout << (cell ? "Q " : ". ");
            cout << endl;
        }
    }
    return 0;
}

Sudoku Solver Concept

A Sudoku solver uses the same backtracking pattern: find an empty cell, try digits 1–9, check validity (row, column, 3×3 box), recurse to next cell. If no digit works, backtrack to the previous cell and try the next digit. The recursion tree can have up to 9⁸¹ nodes, but constraint checking prunes most branches early.

Subset Sum Problem

Problem: Given a set of integers and a target sum, find if any subset sums to the target.

C++
bool subsetSum(vector<int> &arr, int idx, int target) {
    if (target == 0) return true;       // Found a valid subset!
    if (idx < 0 || target < 0) return false;
    // Include arr[idx] OR exclude it
    return subsetSum(arr, idx-1, target-arr[idx])  // Include
        || subsetSum(arr, idx-1, target);          // Exclude
}

Generating All Permutations

C++
void permute(vector<int> &arr, int start, int end) {
    if (start == end) {
        for (int x : arr) cout << x << " ";
        cout << endl;
        return;
    }
    for (int i = start; i <= end; i++) {
        swap(arr[start], arr[i]);        // Choose
        permute(arr, start + 1, end);    // Explore
        swap(arr[start], arr[i]);        // Un-choose (backtrack)
    }
}

Recursion Tree for Permutations of {1, 2, 3}

10. Memoization — Caching Recursive Results

The Problem: Look at the Fibonacci recursion tree above. fib(3) is computed 2 times. fib(2) is computed 3 times. For fib(50), there are over 2⁵⁰ ≈ 10¹⁵ redundant calls. This is catastrophically slow.

The Solution — Memoization: Store the result of each subproblem the first time it's computed. If the same subproblem is encountered again, return the cached result instead of recomputing. This is called memoization (from "memo" — a note to yourself).

Fibonacci Without vs With Memoization

C++
#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<int, long long> memo;

long long fib_memo(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo.count(n)) return memo[n];  // Return cached result
    memo[n] = fib_memo(n-1) + fib_memo(n-2);  // Compute & store
    return memo[n];
}

int main() {
    cout << "fib(50) = " << fib_memo(50) << endl;
    return 0;
}

Python
# Memoized Fibonacci using dictionary
def fib_memo(n, memo={}):
    if n <= 0: return 0
    if n == 1: return 1
    if n in memo: return memo[n]
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(f"fib(50) = {fib_memo(50)}")

11. Classic Recursive Problems

Problem 1: Next Happy Number

C++
#include <iostream>
#include <unordered_set>
using namespace std;

int sumOfSquares(int n) {
    if (n == 0) return 0;
    int digit = n % 10;
    return digit * digit + sumOfSquares(n / 10);
}

bool isHappy(int n, unordered_set<int> &seen) {
    if (n == 1) return true;
    if (seen.count(n)) return false;  // Cycle detected
    seen.insert(n);
    return isHappy(sumOfSquares(n), seen);
}

int nextHappy(int n) {
    int candidate = n + 1;
    while (true) {
        unordered_set<int> seen;
        if (isHappy(candidate, seen)) return candidate;
        candidate++;
    }
}

int main() {
    cout << "Next happy after 6: " << nextHappy(6) << endl;
    cout << "Next happy after 19: " << nextHappy(19) << endl;
    return 0;
}

Complexity: Time: O(k × log n) per candidate, where k is the cycle length. Space: O(log n) for the set.

Problem 2: Sum String

C++
#include <iostream>
#include <string>
using namespace std;

string addStrings(string a, string b) {
    string result;
    int carry = 0, i = a.size()-1, j = b.size()-1;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        result = char(sum % 10 + '0') + result;
        carry = sum / 10;
    }
    return result;
}

bool checkSum(string s, int len1, int len2) {
    string s1 = s.substr(0, len1);
    string s2 = s.substr(len1, len2);
    string sum = addStrings(s1, s2);
    int sumLen = sum.size();
    if (len1 + len2 + sumLen > s.size()) return false;
    if (s.substr(len1 + len2, sumLen) != sum) return false;
    if (len1 + len2 + sumLen == s.size()) return true;
    return checkSum(s.substr(len1), len2, sumLen);
}

bool isSumString(string s) {
    int n = s.size();
    for (int i = 1; i < n; i++)
        for (int j = 1; i+j < n; j++)
            if (checkSum(s, i, j)) return true;
    return false;
}

int main() {
    cout << isSumString("12358132134") << endl;  // 1
    cout << isSumString("1111112223") << endl;   // 1
    return 0;
}

Complexity: Time: O(n³) in worst case. Space: O(n) for string operations.

Problem 3: Water Overflow (Champagne Tower)

C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

double champagneTower(int poured, int query_row, int query_glass) {
    vector<vector<double>> tower(101, vector<double>(101, 0.0));
    tower[0][0] = (double)poured;

    for (int row = 0; row <= query_row; row++) {
        for (int col = 0; col <= row; col++) {
            double overflow = (tower[row][col] - 1.0) / 2.0;
            if (overflow > 0) {
                tower[row+1][col]   += overflow;
                tower[row+1][col+1] += overflow;
            }
        }
    }
    return min(1.0, tower[query_row][query_glass]);
}

int main() {
    cout << "Row 2, Glass 1 (pour 4): " << champagneTower(4, 2, 1) << endl;
    cout << "Row 1, Glass 0 (pour 2): " << champagneTower(2, 1, 0) << endl;
    return 0;
}

Complexity: Time: O(row²). Space: O(row²) for the 2D array.

Learn by Doing — 3-Tier Lab Structure

C++
#include <iostream>
using namespace std;

int factorial(int n) {
    cout << "Called factorial(" << n << ")" << endl;
    if (n == 0) {
        cout << "  Base case! Returning 1" << endl;
        return 1;
    }
    int result = n * factorial(n - 1);
    cout << "  factorial(" << n << ") = " << result << endl;
    return result;
}

int main() {
    cout << "Answer: " << factorial(5) << endl;
    return 0;
}

C++
int fib(int n, int depth = 0) {
    for(int i=0;i<depth;i++) cout << "  ";  // Indent for depth
    cout << "fib(" << n << ")" << endl;
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib(n-1, depth+1) + fib(n-2, depth+1);
}

Input
5 3 0 | 0 7 0 | 0 0 0
6 0 0 | 1 9 5 | 0 0 0
0 9 8 | 0 0 0 | 0 6 0
------+-------+------
8 0 0 | 0 6 0 | 0 0 3
4 0 0 | 8 0 3 | 0 0 1
7 0 0 | 0 2 0 | 0 0 6
------+-------+------
0 6 0 | 0 0 0 | 2 8 0
0 0 0 | 4 1 9 | 0 0 5
0 0 0 | 0 8 0 | 0 7 9

Problem Set — Practice Problems

Tracing Problems — Draw the Recursion Tree (5)

Programming Problems (8)

Industry Application Problems (3)

Interview Problems (3)

MCQ Assessment Bank — 30 Questions (Bloom's Mapped)

Remember / Identify (Q1–Q5)

Understand / Explain (Q6–Q10)

Apply / Implement (Q11–Q15)

int f(int n) {
    if (n <= 1) return n;
    return f(n-1) + f(n-2);
}
cout << f(7);

int mystery(int n) {
    if (n == 0) return 0;
    return (n % 10) + mystery(n / 10);
}

Analyze / Compare (Q16–Q20)

Evaluate / Judge (Q21–Q25)

Create / Design (Q26–Q30)

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

Short Answer Questions (8)

Long Answer Questions (3)

Syllabus Lab

Industry Spotlight — A Day in the Life

Earn With It — Competitive Coding Tutoring

⏱️ Time to First Earning: 3–4 weeks (complete labs, build GitHub portfolio, register on SuperProf/Fiverr)

Chapter Summary

Earning Checkpoint — Are You Ready to Monetise?

✅ Unit 3 complete. Ready for Unit 4: Dynamic Programming!

[QR: Link to EduArtha video tutorial — Recursion & Advanced Techniques]