Recursion and Backtracking

Recursion

Recursion is a programming technique where a function calls itself repeatedly until a base condition is met. In other words, it is the process of solving a problem by breaking it down into smaller instances of the same problem. Recursion is used to solve problems that can be naturally expressed in terms of smaller subproblems. It is commonly used in data structures like trees and graphs, sorting algorithms, and many other applications.


#include <iostream>

int factorial(int n) {
    // base case
    if (n == 0) {
        return 1;
    }
    // recursive case
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    int n = 6;
    std::cout << "Factorial of " << n << " is " << factorial(n) << '\\n';
    return 0;
}

In the above code example, the factorial function calls itself with the argument n - 1 until the base case n == 0 is met. The base case returns 1, which is then multiplied by all the previously returned values.

There are two types of recursion: direct recursion and indirect recursion.

Direct Recursion

In direct recursion, a function calls itself directly.

Consider the following example:


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

The sum function calls itself recursively, passing n - 1 as an argument.

Indirect Recursion

In indirect recursion, two or more functions call each other in a circular chain.

Consider the following example:


void functionA(int n);
void functionB(int n);

void functionA(int n) {
    if (n == 0) {
        return;
    }
    std::cout << "Function A called with argument " << n << '\\n';
    functionB(n - 1);
}

void functionB(int n) {
    if (n == 0) {
        return;
    }
    std::cout << "Function B called with argument " << n << '\\n';
    functionA(n - 1);
}

int main() {
    functionA(3);
    return 0;
}

In the functionA and functionB, they call each other recursively, eventually stopping when n == 0.

Note that in indirect recursion, the function calls form a cycle, which means that each function eventually calls itself or one of the other functions in the cycle.

Backtracking

Backtracking is another algorithmic technique used to solve problems that involve finding all (or some) solutions to a problem that contains constraints. In other words, it is a method of recursively trying out options, and undoing the ones that don't work to try others until a solution is found or it is determined that no solution exists.

A popular example of a problem that can be solved using backtracking is the N-Queens problem where we have to place N queens on an NxN chessboard in such a way that no two queens attack each other.

Here's an example of N-Queens problem using backtracking in C++:


#include <iostream>
#include <vector>

void print(std::vector<int>& queens) {
    int n = queens.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (queens[i] == j) {
                std::cout << "Q ";
            } else {
                std::cout << ". ";
            }
        }
        std::cout << '\\n';
    }
    std::cout << '\\n';
}

bool is_valid(std::vector<int>& queens, int row, int col) {
    for (int i = 0; i < row; ++i) {
        if (queens[i] == col) {
            return false;
        }
        if (abs(row - i) == abs(col - queens[i])) {
            return false;
        }
    }
    return true;
}

void solve(std::vector<int>& queens, int row) {
    int n = queens.size();
    if (row == n) {
        print(queens);
    } else {
        for (int col = 0; col < n; ++col) {
            if (is_valid(queens, row, col)) {
                queens[row] = col;
                solve(queens, row + 1);
            }
        }
    }
}

int main() {
    int n = 4;
    std::vector<int> queens(n);
    solve(queens, 0);
    return 0;
}

In the above code example, the is_valid function returns true if the given row and col position of the queen is valid to be placed on the board, and false otherwise. The solve function places queens on the chessboard row by row until the solution is found. If the solve function reaches the last row of the chessboard, the solution (placement of queens) is printed. If the queen placement is found to be valid, the queens vector is updated, and solve is called recursively for the next row. If no solution is found at any point of the search, the function backtracks (returns to the previous valid placement and tries out a different placement) until all possible solutions have been explored.

Recursion is used in many real-life scenarios, including:

File System Navigation: When navigating through directory trees in a file system, recursive functions are used to traverse each branch of the tree.

Mathematical operations: Recursion is used to perform mathematical operations like calculating factorials, Fibonacci series, and greatest common divisors of two numbers.

Graphics and image processing: Recursion is used to generate complex images and animations in computer graphics.

Search and navigation: Recursive algorithms are used in pathfinding and route-finding algorithms like Depth First Search (DFS) and Breadth First Search (BFS) to explore a graph or a tree to find a solution.

Artificial Intelligence and Game Development: Recursive algorithms are used in artificial intelligence algorithms like minimax and alpha-beta pruning in game development to evaluate different moves.

Compiler design: Recursive algorithms are frequently used in compiler design to parse complex expressions.

Parsing expressions: Parsing is the process of analyzing a string of symbols, either in natural language or in computer language, to determine its grammatical structure. Recursive descent parsing is a popular technique for parsing expressions.

Recursion is a powerful technique that can greatly simplify the implementation of complex algorithms that involve repeated operations on data structures like trees, graphs, and arrays.

PRACTICE PROBLEMS :

Maximum Strength of a Group

N-Queens II