递归与递推
理解递归
递归是一种编程技术，函数调用自身来解决同一问题的较小实例。每个递归解决方案都需要一个基本情况来停止递归和一个递归情况来分解问题。
基本递归示例
让我们从简单的例子开始理解递归的工作原理：阶乘计算和斐波那契数列。
阶乘和斐波那契
#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;
}记忆化存储先前计算的结果以避免重复计算。
树遍历
递归天然适合树操作。像前序、中序和后序这样的树遍历算法使用递归优雅地实现。
二叉树遍历
#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;
}每种遍历方法以不同的顺序访问节点，适用于不同的应用。
回溯算法
回溯是递归的一种形式，它尝试不同的解决方案，当解决方案不起作用时"回溯"。它非常适合解决谜题、生成排列和探索所有可能的解决方案。
N皇后问题
#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;
}回溯逐个尝试放置皇后，如果出现冲突则移除它们。
分治算法
分治将问题分解为较小的子问题，递归地解决它们，然后组合结果。归并排序和快速排序是经典的例子。
归并排序 - 分治算法
#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;
}归并排序通过分割和合并始终保持O(n log n)时间复杂度。