Recursion is one of the most elegant and powerful tools in programming. It allows you to write clean, concise solutions to complex problems — from file systems to graph traversals, and from combinatorics to AI decision trees.

What is Recursion?

Recursion is a process where a function calls itself to solve smaller subproblems of the original problem.

Two Essential Parts:

Base Case – the condition that stops recursion.
Recursive Case – the condition where the function keeps calling itself.

Basic Example:

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

How Recursion Works Internally

Every recursive call is pushed onto the call stack, and it remains there until its base case is hit. After that, results are returned in reverse order as the stack unwinds.

Real-Life Applications of Recursion

Mathematical Functions – factorial, Fibonacci, GCD
Data Structures – linked lists, trees, graphs
File System Traversals – searching directories
Dynamic Programming – memoization & optimization
Backtracking – pathfinding, puzzles, permutations

Recursive Traversal in Data Structures

Let’s explore how recursion makes it easy to traverse complex data structures.

1. Binary Tree Traversals (Inorder, Preorder, Postorder)

Inorder (Left, Root, Right)

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

Preorder and Postorder (just change order)

2. Depth-First Search (DFS) in Graph

void dfs(int node, vector<bool>& visited, vector<vector<int>>& graph) {
    visited[node] = true;
    cout << node << " ";

    for (int neighbor : graph[node]) {
        if (!visited[neighbor])
            dfs(neighbor, visited, graph);
    }
}

Example:

Graph:

0 → 1, 2
1 → 3
2 → 4

DFS output from 0: 0 1 3 2 4

Backtracking — Solving Problems Recursively with Pruning

Backtracking is a method of exploring all possibilities and backtracking when an invalid path is encountered.

Template:

void backtrack(args...) {
    if (solution found) {
        process();
        return;
    }

    for (choices...) {
        makeChoice();
        backtrack(next args...);
        undoChoice();  // backtrack
    }
}

Backtracking Examples

1. Generating All Subsets

void generateSubsets(vector<int>& nums, int index, vector<int>& current, vector<vector<int>>& result) {
    if (index == nums.size()) {
        result.push_back(current);
        return;
    }

    // Exclude
    generateSubsets(nums, index + 1, current, result);

    // Include
    current.push_back(nums[index]);
    generateSubsets(nums, index + 1, current, result);
    current.pop_back();  // Backtrack
}

2. N-Queens Problem

Place N queens on an N×N board such that no two queens attack each other.

bool isSafe(vector<string>& board, int row, int col, int n) {
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
        if (col - row + i >= 0 && board[i][col - row + i] == 'Q') return false;
        if (col + row - i < n && board[i][col + row - i] == 'Q') return false;
    }
    return true;
}

void solveNQueens(int row, vector<string>& board, vector<vector<string>>& result, int n) {
    if (row == n) {
        result.push_back(board);
        return;
    }

    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col, n)) {
            board[row][col] = 'Q';
            solveNQueens(row + 1, board, result, n);
            board[row][col] = '.';  // Backtrack
        }
    }
}

3. Rat in a Maze

Move from top-left to bottom-right of a grid with only right and down moves, avoiding blocked cells.

void findPaths(vector<vector<int>>& maze, int x, int y, int n, string path, vector<string>& result) {
    if (x < 0 || y < 0 || x >= n || y >= n || maze[x][y] == 0)
        return;

    if (x == n - 1 && y == n - 1) {
        result.push_back(path);
        return;
    }

    maze[x][y] = 0;  // Mark as visited

    findPaths(maze, x + 1, y, n, path + "D", result);
    findPaths(maze, x - 1, y, n, path + "U", result);
    findPaths(maze, x, y + 1, n, path + "R", result);
    findPaths(maze, x, y - 1, n, path + "L", result);

    maze[x][y] = 1;  // Backtrack
}

When Not to Use Recursion

When you’re facing tight memory limits (deep recursion = stack overflow).
When a simple loop would do the job faster (e.g., iterating through an array).

Comparison: Recursion vs Iteration

Aspect	Recursion	Iteration
Code Simplicity	More elegant, cleaner	May be verbose
Memory Usage	Uses stack, can overflow	Memory efficient
Performance	Slightly slower due to call overhead	Usually faster
Use Case	Tree/Graph problems, backtracking	Linear traversals, simple loops

Practice Questions

Write a recursive function to compute the nth Fibonacci number.
Solve the Tower of Hanoi problem for 4 disks.
Implement DFS using recursion for an undirected graph.
Generate all permutations of the string "ABC".
Solve the N-Queens problem for n = 8 and print one valid board.
Use recursion to count paths in a grid from (0,0) to (n-1,n-1) avoiding obstacles.
Write a recursive function to reverse a linked list.
Use recursion to traverse a directory structure (simulate with strings/arrays).

📌 Final Thoughts

Recursion is more than just an elegant tool — it’s the foundation for many powerful algorithms. From tree traversals and graph exploration to solving complex constraint-based puzzles, recursion lets you break down problems into their core components.

Learning to write clean, optimized recursive solutions (and knowing when not to use recursion) will level up your problem-solving skills immensely.

Mastering Recursion in C++ — With Real Applications, Traversals & Backtracking