递归

开局先贴贴参考文献


汉诺塔问题

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

很经典的问题,我以前也研究过这东西只不过现在忘得差不多了

最后还是去查查资料才想起来咋整

我们假设目前A杆上有n个盘子

有个前提就是大盘在下,小盘在上

所以我们需要完成的第一个步骤就是把最大盘子以外的的n-1个盘子从A移动到B

第二个步骤是把这坨里面最大的一个盘子从A移动到C

最后一个步骤是把B上面的n-1个盘子移到C这个最大的盘子上面

也就是三步骤,假设移动n-1个盘子的次数为H

那么总的移动次数HN = H+1+H =2H+1

到这里你应该能理解要干什么了,也就是本章的主题

我们并不知道H的具体次数是什么,但是我们可以让剩下的盘子也重复这样的步骤

假设说现在汉诺塔有3层

那么总的次数就等于H3

H3 = 2H2+1;

H2 = 2H1+1;

H1 = 1;

那么H3就是2*(2*1+1)+1 = 7

到这里问题基本解决了

你只要多试几个用数学归纳法总结一下

便会得出结论,n层汉诺塔的移动次数为2^n – 1


递归是什么

相信在做完了上面这道经典的题目

你应该能理解递归的本质是什么

递归本身并不是一种算法,而是一种解决问题的思考方式

当这种思维方式被用于解决算法问题时,这种算法就被叫做递归算法

递归算法的定义(从程序的角度):任何调用自身函数的过程都可以称为递归算法(前面实现的汉诺塔程序就是一个很好的例子)。这里需要注意的是递归必须满足以下两个条件:

  • ①边界条件:至少有一条初始定义是非递归的,如汉诺塔的H(0)=0,阶乘的0!=1。
  • ②递归通式:由已知函数值逐步计算出未知函数值,如汉诺塔的H(0)=0,可以推算出H(1)=H(0)+1+H(0)。

边界条件和递推通式是递归定义的两个基本要素,缺一不可,并且递归通式必须在有限次数内运算完成达到边界条件以保证能够正常结束递归,得到运算结果。

PS:调用自身可以被称为直接递归,p调用q然后q又调用p被称为间接递归,但在算法设计里任何间接递归算法都可以转化为直接递归,所以我们主要讨论的都是直接递归


斐波那契数列中的递归思想

假如动物中有一种特殊的种类,它出生2天后就开始以每天1只的速度繁殖后代。假设第1天,有1只这样的动物(该动物刚出生,从第3天开始繁殖后代)。那么到第11天,共有多少只呢?

(其实就是经典的兔子繁殖问题)

我们按照顺序去计算这种动物的数量

1天 ——1

2天 ——1

3天 ——2 = 1 + 1

4天 ——3 = 1 + 2

5天 ——5 = 2 + 3

6天 ——8 = 3 + 5

7天 ——13 = 5 + 8

。。。。。。。(以下省略)

把每天的动物数进行归纳我们会得出一个结论

  • 第n-1天出生的动物,在第n天还存活着。
  • 第n-2天以前出生的动物,在第n天繁殖了后代

也就是说

设第n天的动物总数为F(n),则有:F(n)=F(n-1)+F(n-2) 其中 n>=3

(注意为了让F(2)=F(1)+F(0)成立,定义F(0)=0,而F(1)则依然为1)

通过比较上面递归算法的定义,我们可以得出这是一个递归算法

而动物数所组成的这个数列,是意大利中世纪数学家斐波那契在<算盘全书>中提出的,这个级数的通项公式,除了具有F(n)=F(n-1)+F(n-2) 的性质外,还可以证明通项公式为:Fn=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}(n=1,2,3,…)


什么时候使用递归?

1.定义是递归的

许多数学公式、数列等的定义是递归的,可以直接转化

像刚讲的斐波那契数列

2.数据结构是递归的

例如单链表,指针next是指向自身结点的一种指针

是一种递归的数据结构

3.问题的求解方法是递归的

例如汉诺塔,特别适合用递归方法来求解


待补充

发表评论

您的电子邮箱地址不会被公开。