Day 4 – Recursion and Backtracking
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