当前位置：首页 > article >正文

递归基本操作总结

article 2024/10/10 7:15:29

递归三要素：参数，出口，返回值

一、思路：

找重复：->作为主要逻辑（或者返回值）
1.找到一种划分方法
2.找到递推公式或者等价转换
找变化的量：
变化的量通常作为参数
找出口:
一般就是边界条件

二、通过例子来理解：

1.阶乘：

// 1.f(n)求n的阶乘
/*
找重复：f(n) = n*f(n-1)，求n-1的阶乘是原问题的子问题
找变化：n变化，变化的量应该作为参数
找边界：f(0)=1
*/
int f(int n) {
	if (n == 0) return 1; //边界
	return n * f(n - 1); //假设已经求出了n-1的阶乘
}

2.打印i-j之间的所有整数：

//2.打印i-j之间的所有整数
/*
找重复：打印i~j之间的所有整数<=>打印i~j-1之间的所有整数+打印j
找变化：区间不断缩小
找边界：i=j
*/
//收缩右边界
void print(int i, int j) {
	if (j < i) {
		return;
	}
	print(i, j - 1);	//打印i~j-1之间的所有整数
	cout << j << " ";	//打印j
}

//或者也可以这样写,收缩左边界
void print1(int i, int j) {
	if (i > j) {
		return;
	}
	cout << i << " ";	//打印i
	print(i + 1, j);	//打印i+1~j之间的所有整数
}

3. 对数组求和

//3.对数组求和
//找重复：sum(a[0...n-1]) = a[0]+sum(a[1...n-1])，sum(a[1...n-1])是原问题的子问题
//找变化：数组首元素位置变化，变化的量应该作为参数
//找边界：n=0
int sum(vector<int>& a, int begin) {
	if (begin == a.size()) return 0; //边界
	return a[begin] + sum(a, begin + 1); //假设已经求出了a[begin...n-1]的和
}

4. 翻转字符串

//4.翻转字符串
//找重复：翻转字符串s[0...n-1] = s[n-1]+翻转字符串s[0...n-2]，翻转字符串s[0...n-2]是原问题的子问题
//找变化：字符串末元素的位置变化(字符串长度)，变化的量应该作为参数
//找边界：n=0
void reverse(string s, int end) {
	if (end == 0) {
		cout << s[0];
		return;
	}//边界
	cout << s[end]; //打印最后一个字符
	reverse(s, end - 1); //翻转s[0...n-2]
}

5.求斐波那契数列的第n项：

//5.求斐波那契数列的第n项，通项公式：f(n)=f(n-1)+f(n-2)->
int fib(int n) {
	if (n == 1 || n == 2) return 1; //边界
	return fib(n - 1) + fib(n - 2); //假设已经求出了n-1和n-2的斐波那契数列
}

但是显然规模变大了，有大量重复:
当然，可以通过一些优化去求斐波那契数列的第n项：比如用动态规划或者是矩阵快速幂。

6.求最大公约数：（欧几里得算法）

//6.求最大公约数
//找重复：gcd(a,b) <=> gcd(b,a%b)
//找变化：a,b变化，变化的量应该作为参数
//找边界：b=0
int gcd(int a, int b) {
	if (b == 0) return a; //边界
	return gcd(b, a % b); //假设已经求出了a%b的最大公约数
}

7.插入排序改为递归:

//插入排序改为递归
void insert_sort(vector<int>& a, int n) {
	if (n == 0) return;
	insert_sort(a, n - 1); //假设已经排好了a[0...n-2]
	int x = a[n - 1];
	int j = n - 2;
	while (j >= 0 && a[j] > x) {
		a[j + 1] = a[j];
		j--;
	}
	a[j + 1] = x;
}

8.汉诺塔问题

//汉诺塔问题
//找重复：hanoi(n,a,b,c) <=> hanoi(n-1,a,c,b) + a->b + hanoi(n-1,c,b,a)
//找变化：n,a,b,c变化，变化的量应该作为参数
//找边界：n=1
void hanoi(int n, char a, char b, char c) {
	if (n == 1) {
		cout << "move " << n << " : " << a << " -> " << b << endl; //把第n个盘子从a移动到b
		return;
	}
	hanoi(n - 1, a, c, b); //把前n-1个盘子从a移动到c,b作为辅助
	cout << "move " << n << " : " << a << " -> " << b << endl; //把第n个盘子从a移动到b
	hanoi(n - 1, c, b, a); //把前n-1个盘子从c移动到b,a作为辅助
}