数据结构学习笔记(五)——递归

数据结构学习笔记(五)——递归


大家好,今天是数据结构的第五篇文章。我们已经从数组过渡到了栈和队列,接下来就要学习一个重要的东西了,而后我们的树和图还有一些高(te)大(fan)上(ren)的数学问题都需要借助它来解决,它就是,递归!



前言


先来看看什么是递归recursion),它的简单定义是这样的:一个函数直接或间接调用自己。


为什么要用递归解决问题呢?递归可以把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题,并且小到一定程度可以直接得出它的解,从而得到原来问题的解。它的好处在于可以用简单的代码完成规模大的问题,N个问题可以转化为N-1个问题,那么解决N-1个问题只需要解决N-2个问题直到变成1个简单问题,最后逆向整个过程,从而完成求解。



举个栗子

在数学中,经常有这样一个问题,求出1+2+3+……+100的和。这类问题在中学的课程经常出现。用循环实现:

void main()
{
int sum,i;
sum=0;
for(i=1;i<=100;++i)
sum+=i;
printf("和为:%dn",sum);
}



循环的优点是,速度快,结构简单。但是并不能处理所有问题,像后面数据结构中树、图的部分问题本身只能用递归,或者是用递归实现起来较容易的汉诺塔的,八皇后等问题。

如果用递归的思想去考虑这个问题是怎样的呢?从

1加到100,用前面提到的思想翻译一下就是,把1到100的和拆分成100和1+..+99的和然后1到99又可以接着往下分成99和1+..+98的和,以此类推。这样就把一个复杂的问题拆分成一个简单问题的不断重复调用。


Long sum(int n) {
if(1 == n)
  return 1;
else
  return n + sum(n-1);
}
int main() {
 printf(“和为%ld”,sum(100));
 return 0;
}



以上主函数调用了sum()函数,而sum()函数内部又调用了它自己。那么一个函数怎么自己调用的自己?



函数的调用



通常,当在一个函数的运行期间调用另一个函数时,在运行被调用函数之前,系统需先完成3件事:(1)将所有实在参数、返回地址等信息传递给被调用函数保存;(2)为被调用函数的局部变量分配存储区;(3)将控制转移到被调函数的入口。而从被调用函数返回调用函数之前,系统也应完成3件工作:(1)保存被调函数的计算结果;(2)释放被调函数的数据区;(3)依照被调函数保存的返回地址将控制转移到调用函数。当有多个构成嵌套调用时。按照“后调用先返回”的原则,上述函数之间的信息传递和控制转移必须通过“栈”来实现,即系统将整个程序运行时所需的数据空间安排在一个栈中,每当调用一个函数时,就为它在栈顶分配一个存储区,每当从一个函数退出时,就释放它的存储区,则当前正运行的函数的数据区必在栈顶。例如,在图(c)所示主函数main中调用了函数first,而在函数first中又调用了函数second,则(a)展示了当前正在执行函数second中某个语句时栈的状态,而(b)展示从函数second退出之后正执行函数first中某个语句时栈的状态(图中以语句标号表示返回地址)。(本段摘自《数据结构(C语言版) 严蔚敏 吴伟民 编著》)


数据结构学习笔记(五)——递归


结论:A函数调用A函数的过程等价于A函数调用B函数的过程。




汉诺塔问题

数据结构学习笔记(五)——递归



三座塔中X塔从上至下从小到大有n个圆盘,要求将X上的n个圆盘移动至Z塔并保持原顺序,规定:

(1)每次只能移动一个圆盘

(2)任意时刻,都不能将大圆盘压在小圆盘之上。


数据结构学习笔记(五)——递归



我们先来看看思路,要想在满足以上条件并完成操作,大致可分为3步,1.先把A塔上的前n-1个圆盘从A借助C移到B2.A塔上的第n个盘子直接移到C3.再将B塔上的n-1个圆盘借助A移到C。从这3步操作中,我们不难看出13步的操作具有相同特征属性,只是问题的规模小1,因此可以用递归的思路求解。



实战

把思路转换成伪算法

   如果是一个圆盘

        直接将A塔上的圆盘从A移到C

   否则

        先将A塔上的前n-1个圆盘借助C塔移到B

        直接将A塔上的圆盘从A移到C

        最后将B塔上的n-1个圆盘借助A塔移到C


#include <stdio.h>

void hanoi(int n, char A, char B, char C) {
 if(1 == n) {
   printf("将编号为%d的盘子直接从%c柱子移到%c柱子n",n, A, C);
 }else {
   hnt(n-1, A, C, B);
   printf("将编号为%d的盘子直接从%c柱子移到%c柱子n",n, A, C);
   hnt(n-1, B, A, C);
 }
}

int main() {
 char ch1 = 'A';
 char ch2 = 'B';
 char ch3 = 'C';
 int n;
 printf("请输入要移动盘子的个数:");
 scanf("%d",&n);
 hanoi(n, 'A', 'B', 'C');

 return 0;
}




END

原文始发于微信公众号(代码墙):数据结构学习笔记(五)——递归