文章目录

• 前言
• 主要内容
• • 初级
  • • 阶乘
    • 斐波那契数列
    • 汉诺塔
    • 数组求和
    • 幂运算
    • 数组翻转
    • 字符串翻转
  • 中级
  • • 全排列
    • 子集
  • 高级
  • • 正则表达式匹配
    • N皇后问题
• 总结
• • 无限循环
  • 栈溢出
• 更多宝藏

前言

😎🥳😎🤠😮🤖🙈💭🍳🍱
递归是一种非常重要的编程技巧，它可以让我们用简洁的代码解决复杂的问题。

主要内容

🦞🦐🦀🦑🦪

主要内容： 递归是一种算法，它通过调用自身来解决问题。一个递归函数通常包括两个部分：基本情况（base case）和递归情况（recursive case）。基本情况是指函数能够直接解决的最简单问题，而递归情况则是指函数通过调用自身来解决更小规模的问题。

初级

阶乘

举个例子，我们可以使用递归来计算阶乘。阶乘表示为n!，定义为n * (n-1) * (n-2) * … * 1。我们可以将其写成一个递归函数：

int factorial(int n) {if (n == 0) {return 1; // 基本情况} else {return n * factorial(n - 1); // 递归情况}
}

斐波那契数列

斐波那契数列：斐波那契数列的第n项定义为前两项之和（除了第0项和第1项分别为0和1）。我们可以使用递归来计算斐波那契数列的第n项：

#include 
using namespace std;int fib(int n) {if (n == 0 || n == 1) {return n;} else {return fib(n - 1) + fib(n - 2);}
}int main() {int n = 10;cout << fib(n) << endl;return 0;
}

在这个例子中，fib函数接受一个参数：整数n。函数使用递归来计算斐波那契数列的第n项。
当n等于0或者1时，直接返回n作为结果。否则，返回前两项之和。

汉诺塔

汉诺塔问题：汉诺塔是一个经典的递归问题。它包括三根柱子和一些大小不等的圆盘。初始时，所有圆盘都叠在第一根柱子上，按照从大到小的顺序排列。目标是将所有圆盘移动到第三根柱子上，并保持原有顺序。每次移动只能移动一个圆盘，并且不能将大圆盘放在小圆盘上面。

我们可以使用递归来解决汉诺塔问题。假设我们要将n个圆盘从柱子A移动到柱子C，可以分为以下步骤：

将前n-1个圆盘从柱子A移动到柱子B（借助柱子C）。
将最后一个圆盘从柱子A移动到柱子C。
将前n-1个圆盘从柱子B移动到柱子C（借助柱子A）。
其中步骤1和步骤3都是规模更小的汉诺塔问题，因此可以使用递归来解决。

#include 
using namespace std;void hanoi(int n, char A, char B, char C) {if (n == 1) {cout << "Move disk 1 from " << A << " to " << C << endl;} else {hanoi(n - 1, A, C, B);cout << "Move disk " << n << " from " << A << " to " << C << endl;hanoi(n - 1, B, A, C);}
}int main() {int n = 3; // 圆盘数量hanoi(n, 'A', 'B', 'C');return 0;
}

在这个例子中，hanoi函数接受4个参数：圆盘数量n，起始柱子A，辅助柱子B和目标柱子C。函数使用递归来解决汉诺塔问题，并输出每一步的移动过程。

当圆盘数量为1时，直接将圆盘从起始柱子移动到目标柱子。否则，先将前n-1个圆盘从起始柱子移动到辅助柱子（借助目标柱子），然后将最后一个圆盘从起始柱子移动到目标柱子，最后再将前n-1个圆盘从辅助柱子移动到目标柱子（借助起始柱子）。

数组求和

给定一个整数数组，使用递归计算数组中所有元素的和。

#include 
using namespace std;int sum(int arr[], int n) {if (n == 0) {return 0;} else {return arr[n - 1] + sum(arr, n - 1);}
}int main() {int arr[] = {1, 2, 3, 4};int n = sizeof(arr) / sizeof(arr[0]);cout << sum(arr, n) << endl;return 0;
}

在这个例子中，sum函数接受两个参数：整数数组arr和数组长度n。函数使用递归来计算数组中所有元素的和。

当数组长度为0时，返回0作为结果。否则，返回最后一个元素加上前n-1个元素的和。

幂运算

给定两个整数x和n，使用递归计算x的n次方。

#include 
using namespace std;int power(int x, int n) {if (n == 0) {return 1;} else if (n % 2 == 0) {int y = power(x, n / 2);return y * y;} else {return x * power(x, n - 1);}
}int main() {int x = 2;int n = 10;cout << power(x, n) << endl;return 0;
}

在这个例子中，power函数接受两个参数：底数x和指数n。函数使用递归来计算x的n次方。

当指数为0时，返回1作为结果。否则，根据指数的奇偶性分别处理。如果指数是偶数，则将其除以2并递归计算x的(n/2)次方，然后将结果平方；如果指数是奇数，则将其减去1并递归计算x的(n-1)次方，然后将结果乘以x。

数组翻转

给定一个整数数组，使用递归将数组翻转

#include 
using namespace std;void reverse(int arr[], int start, int end) {if (start >= end) {return;} else {swap(arr[start], arr[end]);reverse(arr, start + 1, end - 1);}
}int main() {int arr[] = {1, 2, 3, 4};int n = sizeof(arr) / sizeof(arr[0]);reverse(arr, 0, n - 1);for (int i = 0; i < n; i++) {cout << arr[i] << " ";}cout << endl;return 0;
}

在这个例子中，reverse函数接受三个参数：整数数组arr、起始位置start和结束位置end。函数使用递归来将数组翻转。
当起始位置大于等于结束位置时，直接返回。否则，交换两端的元素，并对剩余部分进行递归翻转。

字符串翻转

给定一个字符串，使用递归将字符串翻转。

#include 
#include 
using namespace std;string reverse(string str) {if (str.length() <= 1) {return str;} else {char first = str[0];string rest = str.substr(1);return reverse(rest) + first;}
}int main() {string str = "hello";cout << reverse(str) << endl;return 0;
}

在这个例子中，reverse函数接受一个参数：字符串str。函数使用递归来将字符串翻转。

当字符串长度小于等于1时，直接返回字符串本身作为结果。否则，取出第一个字符和剩余部分，并对剩余部分进行递归翻转，然后将第一个字符添加到末尾。

中级

全排列

给定一个字符串，使用递归打印出该字符串的所有排列。

#include 
#include 
using namespace std;void permute(string str, int l, int r) {if (l == r) {cout << str << endl;} else {for (int i = l; i <= r; i++) {swap(str[l], str[i]);permute(str, l + 1, r);swap(str[l], str[i]);}}
}int main() {string str = "ABC";int n = str.length();permute(str, 0, n - 1);return 0;
}

在这个例子中，permute函数接受三个参数：字符串str、起始位置l和结束位置r。函数使用递归来打印出字符串的所有排列。

当起始位置等于结束位置时，直接打印字符串作为结果。否则，枚举起始位置到结束位置之间的每一个字符，并将其与起始位置的字符交换，然后对剩余部分进行递归排列。

子集

给定一个整数数组，使用递归打印出该数组的所有子集。

#include 
#include 
using namespace std;void subsets(vector &arr, vector> &result, vector &subset, int index) {result.push_back(subset);for (int i = index; i < arr.size(); i++) {subset.push_back(arr[i]);subsets(arr, result, subset, i + 1);subset.pop_back();}
}int main() {vector arr = {1, 2 ,3};vector> result;vector subset;subsets(arr,result ,subset ,0);for(int i=0;icout<<"[";for(int j=0;jcout<

#include 
#include 
using namespace std;bool isMatch(string s, string p) {if (p.empty()) {return s.empty();}bool first_match = (!s.empty() && (s[0] == p[0] || p[0] == '.'));if (p.length() >= 2 && p[1] == '*') {return (isMatch(s, p.substr(2)) || (first_match && isMatch(s.substr(1), p)));} else {return first_match && isMatch(s.substr(1), p.substr(1));}
}int main() {string s = "aa";string p = "a*";cout << isMatch(s, p) << endl;return 0;
}

#include 
#include 
#include 
using namespace std;bool isValid(vector &board, int row, int col) {int n = board.size();for (int i = 0; i < row; i++) {if (board[i][col] == 'Q') {return false;}}for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (board[i][j] == 'Q') {return false;}}for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (board[i][j] == 'Q') {return false;}}return true;
}void backtrack(vector> &res, vector &board, int row) {if(row==board.size()){res.push_back(board);return ;}int n=board[row].size();for(int col=0;colif(!isValid(board,row,col)){continue;}board[row][col]='Q';backtrack(res,board,row+1);board[row][col]='.';}}vector> solveNQueens(int n) {vector> res;vector board(n,string(n,'.'));backtrack(res,board,0);return res;}int main() {int n=4;vector> result=solveNQueens(n);for(int k=0;kcout<<"Solution "<cout<