欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构学习笔记02----递归

程序员文章站 2024-02-12 22:19:52
...

                                数据结构学习笔记02----递归

还是以例子说明递归:

例1:递归求和

根据数据结构学习笔记02----递归,可写出程序:

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";
	}

}

运行结果:

数据结构学习笔记02----递归

看这两个代码,仅仅改变if语句中的两句话的位置,就将输出结果的顺序完全颠倒。关键是看调用前输出还是调用后输出

例三:汉诺塔

要求将A上面的盘子移动到C上,只能一个一个的移动,而且小的在上面,大的在下面。

数据结构学习笔记02----递归

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, ...);                
                                                         }                           

执行步骤:

数据结构学习笔记02----递归

 

例四:看下面三个函数

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)的执行过程:   数据结构学习笔记02----递归

其中: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)的执行过程:   

数据结构学习笔记02----递归

例五:青蛙跳台阶

问题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)阶,当然数据结构学习笔记02----递归。即:

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)问题分析

     当有三阶台阶时,它跳的方式有数据结构学习笔记02----递归三种跳法。

     由此可以看出,输出的是一个序列,而且序列的长短不一样,要输出序列,得用数组,也就是将序列先保存到数组中,然后当满足条件时,把序列输出。每次跳完以后再输出。

    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阶是数据结构学习笔记02----递归种:

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)

数据结构学习笔记02----递归

相关标签: 数据结构笔记