4.5.1从裴波那契的兔子问题看递归算法.pptx

1、递归算法和递归程序，熊文铜梁中学：函数定义：函数是一组一起执行任务的语句。用户定义函数定义格式函数名称(参数表)代码在As类型过程结束函数调用函数格式：函数名称(参数表)，函数，过程，概念或数学结构。如果它自己的引用直接或间接地出现在它的定义或描述中，就说它们是递归的或递归定义的。在程序设计中，过程或函数直接或间接地调用自己，这被称为递归调用。我们拿n！例如，递归：如果n=1，则函数事实(byval n为整数)，如果n=1，则事实=1，否则事实=n *事实(n-1)结束如果结束函数，递归的概念，这是通过递归工作栈实现的；递归=递归回归；1.递归：问题发展到一个极点，这个过程叫做递归；这个过程相

2、当于推动堆栈。2.回归：一个接一个地解决问题，最后返回原来的问题。这个过程叫做回归。这个过程相当于玩堆栈。递归：如果n=1，则函数fact (byval n为整数)然后fact=1否则fact=n * fact (n-1)如果end函数结束。递归解必须满足两个条件：一个问题可以转化为新问题，新问题的解与原问题的解完全相同，只是被处理对象的规模不同。必须有明确的递归结束条件。递归工作原理，递归框架F(n) if(递归结束条件)返回；否则F=F(n-i)关系表达式，经典递归，找到n！费伯纳奇数列的汉诺塔问题找到最大公约数。递归退出条件：递归公式：河内塔由N个不同大小的圆盘和A、B、c、B、c三根木

3、柱组成。开始时，N个圆盘从大到小依次套在a柱上，如图1所示。需要根据以下规则将A列上的N个磁盘移动到C列：(1)一次只能移动一个磁盘；(2)光盘只能存储在三列中；(3)移动过程中，不允许将大板压在小板上。你需要多少次把这些N板从a柱移到C柱？河内塔问题，算法分析这个题目是一个典型的递归编程问题。(1)当N=1时，只有一个板，只需移动：交流电一次；(2)当N=2时，它需要移动三次：a-1-b，a-2-c，b-1-C。(3)如果N=3，具体的移动步骤是：A - 1 - C，河内塔问题，河内塔问题。A-1-c，让我们假设取出步骤3、步骤4和步骤7相当于N=2的情况(以上两个部分被绑在一起并被视为一个

4、部分):汉诺塔问题，移动(a，b，c)，移动(a，c，b)，移动(b，a，c)否则，继续执行；使用列c作为辅助转换，将列a上的(N-1)工作表移动到列b，并调用程序mov(n-1，a，c，b)；将A柱上的剩余部分直接移到C柱上；使用列a作为辅助转换，从列b移动(N-1)到列c，并调用程序mov (n-1，b，a，c)。河内塔问题，专用子移动(n为整数，byval a为字符串，byval b为字符串，byval c为字符串，t为长)如果n=1，则text 3 . text=text 3 . text a b vbcrlf t=t1增加变量t以计算移动次数。否则调用移动(n - 1，A，C，B，t

5、)文本3。文本=文本3。文本A B vbCrLf t=t 1呼叫移动(n - 1，C，B，A，t)结束如果结束子专用子命令1_Click()调暗t为长，n为整数t=0 n=值(文本1。文本)A=A B=B C=C呼叫转移(n，A，B，C，T)文本2。著名的意大利数学家斐波那契在他的算盘一书中提出了一个“兔子问题”:假设兔子在一个月内可以长成大兔子，大兔子每个月会生出一对小兔子。如果你在年初有一对兔子，年底会有多少对兔子？(当然，必须假设兔子没有死，并且严格按照上述规则成长和繁殖)，问题4-16，表43兔子问题分析表。虽然这张表已经解决了斐波纳契数列中的兔子问题(年底兔子的总数是144)，但是如

6、果你仔细观察这张表，你会发现兔子的数量增长得越来越快。如果时间较长，就很难只用列表的方法。(例如，你想知道五年内兔子的数量吗？我们需要研究表格中的规则，找出解决这个问题的一般方法。设计算法“兔子问题”可以很容易地通过列出一个递归公式来解决。假设第N个月的兔子数是F(N)，我们有：这是因为每个月的大兔子数必须等于前一个月的兔子总数，每个月的小兔子数必须等于前一个月的大兔子数。我们可以根据上面的递归公式设计一个递归程序。递归程序的特点是独立地编写一个函数(或子过程)，这个函数只给出几个非常简单情况的直接答案，而在其他情况下，这个问题是通过反复调用自己并将其简化为最简单的情况来解决的。函数Fib(用

7、整数表示)如果N=3，那么Fib=1否则Fib=Fib(N - 1) Fib(N - 2)结束函数专用子命令1_Click() N=Val(文本1)。文本)文本2。Text=第N个月的兔子数是：Fib(N) End Sub、代码、测试程序和递归算法的特征。递归过程通常通过函数或子过程来实现。递归算法：在一个函数或子过程中，直接或间接地调用自己的算法。递归算法的本质是将问题转化为规模缩小的同类子问题。然后递归调用一个函数(或过程)来表示问题的解决方案。递归算法解决问题的特点：(1)递归是在一个过程或函数中调用自身。(2)当使用增量返回策略时，必须有一个明确的递归结束条件，称为递归退出。(3)递归算法通常非常简洁，但运行效率较低。因此，一般不推荐使用递归算法来设计程序。(4)在递归调用过程中，系统打开一个栈来存储每一层的返回点和局部量。太多的递归容易导致堆栈溢出等。因此，一般不推荐使用递归算法来设计程序。递归算法中体现的“重复”一般有三个要求：第一，每次调用的规模减小(通常减半)；第二，两个相邻的重复之间有着密切的关系，