A colorful summary of recursion and backtracking with code examples and notes.

Recursion 🌟

What is Recursion?

• Recursion is a programming technique that breaks problems into smaller sub-tasks and repeatedly calls the function to solve them.
• It provides an alternative to iterative methods, often making the code shorter and easier to read.

Recursion Flow

1. Base Case: Stops the recursion.
2. Recursive Case: Calls the function with a smaller problem.

void recursion() {
    // Base case
    if () {
        return;
    }
    recursion();
}
int main() {
    recursion();
}

How Recursion Works

• Base Case: The condition where the function stops calling itself.
• Recursive Case: The function calls itself with modified input, moving closer to the base case.

void fun(int i) {
    if (i == 0) return;
    fun(i - 1);
    cout << i << '\\\\n';  // Prints after recursion
}

void fun(int i) {
    if (i == 0) return;
    cout << i << '\\\\n';  // Prints before recursion
    fun(i - 1);
}

Stack Overflow 💥

• A stack overflow happens when a function calls itself indefinitely due to missing or incorrect base cases.
• Always define a base case to stop recursion.

int fact(int n) {
    return n * fact(n - 1);  // Missing base case: Infinite recursion
}

Backtracking 🔄

What is Backtracking?

• Backtracking is a recursive algorithm that incrementally builds solutions and excludes invalid ones early.