递归是一种非常重要的编程技巧，它可以让我们用简洁的代码解决复杂的问题。
主要内容： 递归是一种算法，它通过调用自身来解决问题。一个递归函数通常包括两个部分：基本情况（base case）和递归情况（recursive case）。基本情况是指函数能够直接解决的最简单问题，而递归情况则是指函数通过调用自身来解决更小规模的问题。
初级
阶乘
举个例子，我们可以使用递归来计算阶乘。阶乘表示为n!，定义为n * (n-1) * (n-2) * … * 1。我们可以将其写成一个递归函数：
c
int factorial(int n) {
if (n == 0) {
return 1; // 基本情况
} else {
return n * factorial(n - 1); // 递归情况
}
}
python
def factorial(n):
if n==1: return 1
else: return factorial(n-1)*n
print(factorial(4))
斐波那契数列
斐波那契数列：斐波那契数列的第n项定义为前两项之和（除了第0项和第1项分别为0和1）。我们可以使用递归来计算斐波那契数列的第n项：
c
#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;
}
python
def fib(n):
if n==1 or n==2: return 1
else: return fib(n-1) fib(n-2)
print(fib(15))
print(fib(35))
加入哈希表记忆优化
def fib(n):
if hash.get(n,0): return hash[n]
res=fib(n-1) fib(n-2)
hash[n]=res
return res
hash={
1:1,2:1}
print(fib(15))
print(fib(50))
在这个例子中，fib函数接受一个参数：整数n。函数使用递归来计算斐波那契数列的第n项。
当n等于0或者1时，直接返回n作为结果。否则，返回前两项之和。
汉诺塔
汉诺塔问题：汉诺塔是一个经典的递归问题。它包括三根柱子和一些大小不等的圆盘。初始时，所有圆盘都叠在第一根柱子上，按照从大到小的顺序排列。目标是将所有圆盘移动到第三根柱子上，并保持原有顺序。每次移动只能移动一个圆盘，并且不能将大圆盘放在小圆盘上面。
我们可以使用递归来解决汉诺塔问题。假设我们要将n个圆盘从柱子a移动到柱子c，可以分为以下步骤：
将前n-1个圆盘从柱子a移动到柱子b（借助柱子c）。
将最后一个圆盘从柱子a移动到柱子c。
将前n-1个圆盘从柱子b移动到柱子c（借助柱子a）。
其中步骤1和步骤3都是规模更小的汉诺塔问题，因此可以使用递归来解决。
c
#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;
}
python
def hanoi(n,a,b,c):
if n==1: print(a "---->" c)
else:
hanoi(n-1,a,c,b)
print(a "---->" c)
hanoi(n-1,b,a,c)
hanoi(2,'a','b','c')
在这个例子中，hanoi函数接受4个参数：圆盘数量n，起始柱子a，辅助柱子b和目标柱子c。函数使用递归来解决汉诺塔问题，并输出每一步的移动过程。
当圆盘数量为1时，直接将圆盘从起始柱子移动到目标柱子。否则，先将前n-1个圆盘从起始柱子移动到辅助柱子（借助目标柱子），然后将最后一个圆盘从起始柱子移动到目标柱子，最后再将前n-1个圆盘从辅助柱子移动到目标柱子（借助起始柱子）。
数组求和
给定一个整数数组，使用递归计算数组中所有元素的和。
c
#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;
}
python
def arr_sum(l,n):
if n==0: return 0
return l[n-1] arr_sum(l,n-1)
arr = [1,2,3,4,5,10]
print(arr_sum(arr,len(arr)))
在这个例子中，sum函数接受两个参数：整数数组arr和数组长度n。函数使用递归来计算数组中所有元素的和。
当数组长度为0时，返回0作为结果。否则，返回最后一个元素加上前n-1个元素的和。
幂运算
给定两个整数x和n，使用递归计算x的n次方。
c
#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;
}
python
def power_x_y(x,y):
if y==0:return 1
if y&1:return x*power_x_y(x,(y-1)>>1)**2
return power_x_y(x,y>>1)**2
print(power_x_y(2,11))
print(power_x_y(2,12))
在这个例子中，power函数接受两个参数：底数x和指数n。函数使用递归来计算x的n次方。
当指数为0时，返回1作为结果。否则，根据指数的奇偶性分别处理。如果指数是偶数，则将其除以2并递归计算x的(n/2)次方，然后将结果平方；如果指数是奇数，则将其减去1并递归计算x的(n-1)次方，然后将结果乘以x。
数组翻转
给定一个整数数组，使用递归将数组翻转
c
#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;
}
python
def swap(x, y):
tmp=l[x]
l[x]=l[y]
l[y]=tmp
def reverse_list(l,start,end):
if start>=end:return
swap(start,end)
reverse_list(l,start 1,end-1)
l=[1,2,3,4,5,6,7,8,9]
reverse_list(l,0,len(l)-1)
print(l)
在这个例子中，reverse函数接受三个参数：整数数组arr、起始位置start和结束位置end。函数使用递归来将数组翻转。
当起始位置大于等于结束位置时，直接返回。否则，交换两端的元素，并对剩余部分进行递归翻转。
字符串翻转
给定一个字符串，使用递归将字符串翻转。
c
#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时，直接返回字符串本身作为结果。否则，取出第一个字符和剩余部分，并对剩余部分进行递归翻转，然后将第一个字符添加到末尾。
中级
全排列
给定一个字符串，使用递归打印出该字符串的所有排列。
c
#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;
}
python
#数组全排列（转化为字符串即可）
def swap(left, right):
tmp=l[left]
l[left] = l[right]
l[right] = tmp
def all_sort(l,left, right):
if left==right:print(l)
else:
for i in range(left,right 1):
swap(left,i)
all_sort(l,left 1,right)
swap(left,i)
l=[1,2,3]
all_sort(l,0,len(l)-1)
在这个例子中，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;i
这段代码是一个使用递归生成整数数组所有子集的c 程序。它定义了一个名为subsets的函数，该函数接受四个参数：整数数组arr、结果集合result、当前子集合并subset和当前索引位置index。
在主函数中，首先定义了一个整数数组arr = {1, 2 ,3}，然后定义了一个结果集合和一个空的子集合并。接着调用了一次subsets(arr,result ,subset ,0)函数，以生成所有子集。
最后，程序遍历结果集合并打印出每个子集。
高级
正则表达式匹配
给定一个字符串s和一个正则表达式p，使用递归实现正则表达式匹配。
#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;
}
在这个例子中，ismatch函数接受两个参数：字符串s和正则表达式p。函数使用递归来实现正则表达式匹配。
当正则表达式为空时，如果字符串也为空，则返回true；否则返回false。接着判断第一个字符是否匹配。如果正则表达式的长度大于等于2且第二个字符为’*'，那么可以选择忽略这两个字符或者重复第一个字符。否则，继续比较剩余部分。
n皇后问题
给定一个整数n，表示棋盘的大小为n*n，使用递归求出所有不同的n皇后摆放方案。
#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;col> 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;k
这段代码是一个使用递归解决n皇后问题的c 程序。它定义了三个函数：isvalid、backtrack和solvenqueens。
其中，isvalid函数用于判断在棋盘的第row行第col列放置一个皇后是否合法。它接受三个参数：棋盘board、行号row和列号col。函数通过遍历棋盘上方、右上方和左上方来判断是否有其他皇后与当前位置冲突。
backtrack函数用于回溯搜索所有可能的解。它接受三个参数：结果集合res、棋盘board和当前行号row。当row等于棋盘大小时，表示找到了一种解法，将其加入结果集合中。否则，遍历当前行的每一列，如果在该位置放置皇后合法，则继续搜索下一行。
solvenqueens函数是主要的求解函数。它接受一个整数n作为参数，表示棋盘的大小为n*n。函数首先定义了一个结果集合res和一个空棋盘board，然后调用一次backtrack(res, board, 0)函数以搜索所有可能的解。
在主函数中，首先定义了一个整数n=4，表示棋盘大小为4*4。然后调用solvenqueens(n)函数求解，并打印出所有不同的摆放方案。
🦀️ ⭐
递归是一种强大而优雅的编程技巧，在解决复杂问题时非常有用。但是使用时需要注意避免无限循环和栈溢出等问题。
无限循环
避免无限循环是编写递归函数时需要注意的一个重要问题。如果递归函数没有正确地定义基本情况和递归情况，就可能出现无限循环的情况。
为了避免无限循环，我们需要确保每次递归调用都能够使问题的规模减小，最终能够达到基本情况。这样，递归函数就能够在有限的步骤内结束。
例如，在计算阶乘的例子中，我们定义了两种情况：当n等于0时，直接返回1作为结果；否则，返回n乘以(n-1)!。由于每次递归调用都会将n减小1，因此最终一定会达到基本情况n等于0。
另外，在编写递归函数时，也可以使用一些技巧来避免无限循环。例如，可以使用计数器来记录递归调用的次数，并在超过一定次数时强制结束递归。
总之，要避免无限循环，关键是要正确地定义基本情况和递归情况，并确保每次递归调用都能够使问题的规模减小。
栈溢出
栈溢出（stack overflow）是指程序在运行过程中，栈空间被耗尽的情况。这通常是由于程序中存在无限递归或者过深的递归调用导致的。
当程序运行时，每次函数调用都会在栈上分配一定的空间来存储局部变量、参数和返回地址等信息。当函数返回时，这些空间会被释放。如果函数调用层次过深，栈上分配的空间就会超过栈的容量，导致栈溢出。
栈溢出可能会导致程序崩溃或者产生不可预料的行为。因此，在编写递归函数时，应该注意避免无限递归和过深的递归调用。
如果你在解决这些问题时遇到困难，不妨多思考一下，或者寻求其他人的帮助。只要坚持不懈，相信你一定能够掌握递归这一重要技能。