数据结构学习笔记02----递归
数据结构学习笔记02----递归
还是以例子说明递归:
例1:递归求和
根据,可写出程序:
int Test::sum(int n)
{
if (n == 0) {
return 0;
}
else {
return n + sum(n - 1);
}
}
从这个简单的程序可以看出,递归一般的结构是if(终止条件)+ else.后面的递推过程。
据此,可以很容易写出联乘的递归形式:
int f(int n)
{
if(n==1) return 1;
else return n*f(n-1);
}
例2:正反序输出问题
void Test::print1(int n)
{
if (n > 0) {
cout << n << "\t";
print1(n - 1);
}
cout << endl;
}
void Test::print2(int n)
{
if (n > 0) {
print2(n - 1);
cout << n << "\t";
}
}
运行结果:
看这两个代码,仅仅改变if语句中的两句话的位置,就将输出结果的顺序完全颠倒。关键是看调用前输出还是调用后输出。
例三:汉诺塔
要求将A上面的盘子移动到C上,只能一个一个的移动,而且小的在上面,大的在下面。
1)分析:
假设有三个:我们只需要将1,2号盘子移动到B上,然后将3号盘子从A移动到C上,最后将B上的1,2号盘子移动到C上就结束了。
假设有n个:我们只需要将n-1号盘子移动到B上,然后将n号盘子从A移动到C上,最后将B上的n-1号盘子移动到C上就结束了。
2)终止条件的处理:
①:对一号盘子处理。
②:把一号盘子当普通盘子,也就是无特殊盘子。
3)代码的执行和运行
那么可写为:
void Test::Move(int n, char a, char b, char c)//n表示n个,a,b,c分别表示源,中间过渡,目的
{
if (n >= 1) {
Move(n - 1, a, c, b);//n-1个从a通过c移动到b上
cout << n << "号盘子从" << a << "移动到" << c << endl;//挪走了n-1个还剩下n号
Move(n - 1, b, a, c);
}
}
部分调用过程:
Move(3,a,b,c) Move(2,a,c,b) Move(2,a,c,b)
{ { {
Move(2, a, c, b); Move(1, a, b, c); Move(0, ...);
3->a->c; 2->a->b; 1->a->c;
Move(2, b, a, c); Move(2, c, a, b); Move(0, ...);
} } }
Move(2,a,c,b)
{
Move(2, a, c, b);
3->a->c;
Move(0, ...);
}
执行步骤:
例四:看下面三个函数
void Test::harder1(int n)
{
if (n > 0) {
cout << n << "\t";
harder1(n - 1);
cout << n << "\t";
}
}
void Test::harder2(int n)
{
if (n > 0) {
harder2(n - 1);
cout << n << "\t";
harder2(n - 1);
}
}
harder2(4):
void Test::harder3(int n)
{
cout << n << "\t";
harder3(n - 1);
cout << n << "\t";
harder3(n - 1);
}
下面模拟harder1(4)的执行过程: ①:4 harder(3) 4 ②:4 3 harder(2) 3 4 ,最终为43211234
下面模拟harder2(4)的执行过程:
其中:1 2 1是harder(2)的输出,其中那个2是harder(2)执行过程中中间那个输出语句cout << n << "\t";
由此可推出harder2(5) = harder2(4) 5 harder2(4) = 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
下面模拟harder3(4)的执行过程:
例五:青蛙跳台阶
问题1.一只青蛙一次只能跳一阶或者2阶,那么跳n阶台阶有多少种跳法。
1)问题分析:
此问题的终止条件 若n=1(只剩下一凳)则返回1,剩下一凳有1种方法;若n=2(只剩下2凳)则返回2,剩下两凳有2种方法。
首先将问题降阶处理:由于青蛙第一次跳可能是跳一阶,也可能跳两阶,而且两中跳法不重复,故对于n阶台阶,要么降一阶要么降2阶,也就是下面的f(n - 1) +和f(n - 2),所以总共的跳法是两种加起来。
下面伪代码中n是剩余要跳的台阶数,函数f返回值是跳法的个数。
if (n == 1) return 1;//终止条件
else if (n == 2) return 2;//终止条件
else return f(n - 1) + f(n - 2);//f(n - 1)是第一次跳1阶, f(n - 2)是第一次跳2阶
2)代码实现:
int Test::jump_1_2(int n)
{
if (n == 1)
return 1;
if (n == 2)
return 2;
return jump_1_2(n - 1) + jump_1_2(n - 2);
}
问题2.一只青蛙一次可以跳1,2,.....n阶台阶,那么跳n阶台阶有多少种跳法。
1)分析问题
此时问题的终止条件不像上一次那样,因为不知道它最后一次跳是跳了几阶。所以它的终止条件是当n = 0时,终止。
我们将n阶降阶(没说要像问题1中降1阶或者降2阶),降的阶数对于剩下n阶台阶有n种,也就是将n阶问题转化成了n个子问题。对于n阶台阶,若跳了x阶,那么还剩下(n-x)阶,当然。即:
for (int i = 1; i <= n; ++i)
{
t += f(n - i);//t是n阶情况下能跳的种数,f(n - i)是剩下的n-i阶台阶的跳法
}
2)代码实现:
int Test::jump_all(int n)
{
int t = 0;
if (n == 0)
return 1;
for (int i = 1; i <= n; ++i)
{
t += jump_all(n - i);
}
return t;
}
问题3.以上只是单纯的求出有多少种跳法,但是没有输出每种跳法,那么应该如何输出囊?
1)问题分析
当有三阶台阶时,它跳的方式有三种跳法。
由此可以看出,输出的是一个序列,而且序列的长短不一样,要输出序列,得用数组,也就是将序列先保存到数组中,然后当满足条件时,把序列输出。每次跳完以后再输出。
step1:首先我们要找一个条件,也就是可以看做是完成的条件。分析jump_all(int n)可知,当return的值是1的时候,也就是可以当成完成了。
step2:要在递归过程中吧每一次的跳法的中间过程放入数组中。
step3:由于序列长度长短不一,所以还得需要数组的长度。
2)程序分析
int Test::jump_all_output(int left, int a[], int filled)
{
{
int t = 0;
if (left == 0)
{
//输出a[]中存放的元素
for (int i = 0; i<filled; ++i)
{
cout << a[i] << "\t";
}
cout << endl;
return 1;
}
for (int i = 1; i <= left; ++i)
{
a[filled] = i;
t += jump_all_output(left - i, a, filled + 1);
}
return t;
}
}
①:程序的返回值还是返回跳的种数。参数a[]是存放序列的数组;filled是当前数组的长度,所以在调用时写0;left是当前剩余的台阶数
②运行结果:以3阶为例,n阶是种:
f(0) = 1;
f(1) = f(0) = 1;
f(2) = f(1) + f(0) = 2;
f(3) = f(2) + f(1) + f(0) = 2 + 1 + 1 = 4;
.
.
.
.
f(n) = f(n-1) + f(n-2)......+f(0) = 2^(n-1)
上一篇: 使用echarts
下一篇: 微信小程序基础-01