Today I studied the foundations of recursion and got introduced to backtracking. These are essential problem-solving techniques used in problems involving decision trees, permutations, combinations, and more.

What is Recursion?

Recursion is a function calling itself to solve smaller instances of the same problem, eventually reaching a base case. It uses the call stack for tracking function calls.

Key Concepts:

Base Case: The condition to stop recursion (must-have)
Recursive Case: The self-call with smaller input
Stack Space: Every call consumes stack memory

Basic Recursion Problems with Complexities

1. Print Name N Times

void printName(int i, int n) {
    if (i > n) return;
    cout << "Sid" << endl;
    printName(i+1, n);
}
// Time: O(n), Space: O(n)

2. Print 1 to N

void print1ToN(int i, int n) {
    if (i > n) return;
    cout << i << " ";
    print1ToN(i+1, n);
}
// Time: O(n), Space: O(n)

3. Print N to 1

void printNTo1(int n) {
    if (n < 1) return;
    cout << n << " ";
    printNTo1(n-1);
}
// Time: O(n), Space: O(n)

4. Sum of First N Numbers

int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n-1);
}
// Time: O(n), Space: O(n)

5. Factorial of N

int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n-1);
}
// Time: O(n), Space: O(n)

6. Fibonacci Number

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}
// Time: O(2^n), Space: O(n)

7. Reverse Array using Recursion

void reverse(int arr[], int l, int r) {
    if (l >= r) return;
    swap(arr[l], arr[r]);
    reverse(arr, l+1, r-1);
}
// Time: O(n), Space: O(n)

8. Palindrome Check

bool isPalindrome(int arr[], int l, int r) {
    if (l >= r) return true;
    if (arr[l] != arr[r]) return false;
    return isPalindrome(arr, l+1, r-1);
}
// Time: O(n), Space: O(n)

Backtracking – Introduction

Backtracking is recursion with a decision tree. It tries all possibilities and undoes ("backtracks") when a path fails.

Key Idea:

Choose
Explore
Un-choose (Backtrack)

Used in:

Subsets
Permutations
N-Queens
Sudoku Solver

Subsequence-Based Problems (very imp)

Given an array, find different types of subsequences using recursion.

1. Print All Subsequences

void subseq(int i, vector<int> &arr, vector<int> &ds) {
    if (i == arr.size()) {
        for (int x : ds) cout << x << " ";
        cout << endl;
        return;
    }
    ds.push_back(arr[i]);            // take
    subseq(i+1, arr, ds);
    ds.pop_back();                   // don't take
    subseq(i+1, arr, ds);
}
// Time: O(2^n), Space: O(n)

2. Print Subsequences With Sum = K

void sumK(int i, int sum, vector<int> &arr, vector<int> &ds, int k) {
    if (i == arr.size()) {
        if (sum == k) {
            for (int x : ds) cout << x << " ";
            cout << endl;
        }
        return;
    }
    ds.push_back(arr[i]);
    sumK(i+1, sum + arr[i], arr, ds, k);
    ds.pop_back();
    sumK(i+1, sum, arr, ds, k);
}
// Time: O(2^n), Space: O(n)

3. Print Only One Subsequence With Sum = K

bool sumKOne(int i, int sum, vector<int> &arr, vector<int> &ds, int k) {
    if (i == arr.size()) {
        if (sum == k) {
            for (int x : ds) cout << x << " ";
            cout << endl;
            return true;
        }
        return false;
    }
    ds.push_back(arr[i]);
    if (sumKOne(i+1, sum + arr[i], arr, ds, k)) return true;
    ds.pop_back();
    if (sumKOne(i+1, sum, arr, ds, k)) return true;
    return false;
}
// Time: O(2^n), Space: O(n)

4. Count Subsequences With Sum = K

int countSumK(int i, int sum, vector<int> &arr, int k) {
    if (i == arr.size()) {
        return sum == k ? 1 : 0;
    }
    int left = countSumK(i+1, sum + arr[i], arr, k);
    int right = countSumK(i+1, sum, arr, k);
    return left + right;
}
// Time: O(2^n), Space: O(n)

Summary:

Learned the difference between recursion and backtracking
Covered multiple standard problems using recursion
Introduced subsequence patterns — a foundation for backtracking
Learned complexity of each problem for both time and space

Day 4 – Recursion and Backtracking