Recursion & Recurrence
Understanding Recursion
Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem. Every recursive solution needs a base case to stop the recursion and a recursive case that breaks down the problem.
Basic Recursion Examples
Let's start with simple examples to understand how recursion works: factorial calculation and Fibonacci sequence.
Factorial and Fibonacci
#include <iostream>
#include <vector>
using namespace std;
// Factorial: n! = n * (n-1)!
long long factorial(int n) {
// Base case
if (n <= 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Fibonacci: F(n) = F(n-1) + F(n-2)
long long fibonacci(int n) {
// Base cases
if (n <= 1) {
return n;
}
// Recursive case
return fibonacci(n - 1) + fibonacci(n - 2);
}
// Optimized Fibonacci with memoization
long long fibonacciMemo(int n, vector<long long>& memo) {
if (n <= 1) {
return n;
}
if (memo[n] != -1) {
return memo[n];
}
memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
return memo[n];
}
int main() {
cout << "Factorial of 5: " << factorial(5) << endl;
cout << "Fibonacci of 10: " << fibonacci(10) << endl;
// Using memoization for efficiency
vector<long long> memo(11, -1);
cout << "Fibonacci with memoization: " << fibonacciMemo(10, memo) << endl;
return 0;
}Memoization stores previously computed results to avoid redundant calculations.
Tree Traversal
Recursion is naturally suited for tree operations. Tree traversal algorithms like preorder, inorder, and postorder are elegantly implemented using recursion.
Binary Tree Traversal
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class BinaryTree {
public:
// Preorder: Root -> Left -> Right
void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// Inorder: Left -> Root -> Right
void inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
// Postorder: Left -> Right -> Root
void postorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
// Calculate tree height
int height(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return 1 + max(leftHeight, rightHeight);
}
// Count total nodes
int countNodes(TreeNode* root) {
if (root == nullptr) {
return 0;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
int main() {
// Create a sample tree: 1
// / \
// 2 3
// / \
// 4 5
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
BinaryTree tree;
cout << "Preorder traversal: ";
tree.preorderTraversal(root);
cout << endl;
cout << "Inorder traversal: ";
tree.inorderTraversal(root);
cout << endl;
cout << "Postorder traversal: ";
tree.postorderTraversal(root);
cout << endl;
cout << "Tree height: " << tree.height(root) << endl;
cout << "Total nodes: " << tree.countNodes(root) << endl;
return 0;
}Each traversal method visits nodes in a different order, useful for different applications.
Backtracking
Backtracking is a form of recursion that tries different solutions and "backtracks" when a solution doesn't work. It's perfect for solving puzzles, generating permutations, and exploring all possible solutions.
N-Queens Problem
#include <iostream>
#include <vector>
using namespace std;
class NQueens {
private:
vector<vector<string>> solutions;
bool isSafe(vector<string>& board, int row, int col, int n) {
// Check this column on upper rows
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') {
return false;
}
}
// Check upper diagonal on left side
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
// Check upper diagonal on right side
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
void solve(vector<string>& board, int row, int n) {
// Base case: all queens are placed
if (row == n) {
solutions.push_back(board);
return;
}
// Try placing queen in each column of current row
for (int col = 0; col < n; col++) {
if (isSafe(board, row, col, n)) {
board[row][col] = 'Q'; // Place queen
solve(board, row + 1, n); // Recursively place remaining queens
board[row][col] = '.'; // Backtrack
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
solutions.clear();
vector<string> board(n, string(n, '.'));
solve(board, 0, n);
return solutions;
}
void printSolution(const vector<string>& board) {
for (const string& row : board) {
cout << row << endl;
}
cout << endl;
}
};
int main() {
NQueens nqueens;
vector<vector<string>> solutions = nqueens.solveNQueens(4);
cout << "Solutions for 4-Queens problem:" << endl;
for (int i = 0; i < solutions.size(); i++) {
cout << "Solution " << (i + 1) << ":" << endl;
nqueens.printSolution(solutions[i]);
}
cout << "Total solutions found: " << solutions.size() << endl;
return 0;
}Backtracking tries placing queens one by one, removing them if conflicts arise.
Divide and Conquer
Divide and conquer breaks a problem into smaller subproblems, solves them recursively, and combines the results. Merge sort and quick sort are classic examples.
Merge Sort - Divide and Conquer
#include <iostream>
#include <vector>
using namespace std;
class MergeSort {
public:
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
vector<int> L(n1), R(n2);
// Copy data to temporary arrays
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge the temporary arrays back
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Divide: Sort first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Conquer: Merge the sorted halves
merge(arr, left, mid, right);
}
}
void printArray(const vector<int>& arr) {
for (int x : arr) {
cout << x << " ";
}
cout << endl;
}
};
int main() {
vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
MergeSort sorter;
cout << "Original array: ";
sorter.printArray(arr);
sorter.mergeSort(arr, 0, arr.size() - 1);
cout << "Sorted array: ";
sorter.printArray(arr);
return 0;
}Merge sort consistently achieves O(n log n) time complexity by dividing and merging.