前言
递归是一种非常重要的编程技巧,它可以让我们用简洁的代码解决复杂的问题。
主要内容
主要内容: 递归是一种算法,它通过调用自身来解决问题。一个递归函数通常包括两个部分:基本情况(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 <iostream>
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 <iostream>
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 <iostream>
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 <iostream>
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 <iostream>
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 <iostream>
#include <string>
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 <iostream>
#include <string>
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 <iostream>
#include <vector>
using namespace std;
void subsets(vector<int> &arr, vector<vector<int>> &result, vector<int> &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<int> arr = {
1, 2 ,3};
vector<vector<int>> result;
vector<int> subset;
subsets(arr,result ,subset ,0);
for(int i=0;i<result.size();i++){
cout<<"[";
for(int j=0;j<result[i].size();j++){
cout<<result[i][j]<<" ";
}
cout<<"]"<<endl;
}
return 0;
}
这段代码是一个使用递归生成整数数组所有子集的C++程序。它定义了一个名为subsets的函数,该函数接受四个参数:整数数组arr、结果集合result、当前子集合并subset和当前索引位置index。
在主函数中,首先定义了一个整数数组arr = {1, 2 ,3},然后定义了一个结果集合和一个空的子集合并。接着调用了一次subsets(arr,result ,subset ,0)函数,以生成所有子集。
最后,程序遍历结果集合并打印出每个子集。
高级
正则表达式匹配
给定一个字符串s和一个正则表达式p,使用递归实现正则表达式匹配。
#include <iostream>
#include <string>
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 <iostream>
#include <vector>
#include <string>
using namespace std;
bool isValid(vector<string> &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<vector<string>> &res, vector<string> &board, int row) {
if(row==board.size()){
res.push_back(board);
return ;
}
int n=board[row].size();
for(int col=0;col<n;col++){
if(!isValid(board,row,col)){
continue;
}
board[row][col]='Q';
backtrack(res,board,row+1);
board[row][col]='.';
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> board(n,string(n,'.'));
backtrack(res,board,0);
return res;
}
int main() {
int n=4;
vector<vector<string>> result=solveNQueens(n);
for(int k=0;k<result.size();k++){
cout<<"Solution "<<k+1<<":"<<endl;
for(int i=0;i<result[k].size();i++){
cout<<result[k][i]<<endl;
}
cout<<endl;
}
}
这段代码是一个使用递归解决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)是指程序在运行过程中,栈空间被耗尽的情况。这通常是由于程序中存在无限递归或者过深的递归调用导致的。
当程序运行时,每次函数调用都会在栈上分配一定的空间来存储局部变量、参数和返回地址等信息。当函数返回时,这些空间会被释放。如果函数调用层次过深,栈上分配的空间就会超过栈的容量,导致栈溢出。
栈溢出可能会导致程序崩溃或者产生不可预料的行为。因此,在编写递归函数时,应该注意避免无限递归和过深的递归调用。
如果你在解决这些问题时遇到困难,不妨多思考一下,或者寻求其他人的帮助。只要坚持不懈,相信你一定能够掌握递归这一重要技能。