5 函数（二） 5.1 基本知识 5.2 函数重载 5.3 示例 5.4 变量的作用域和生命期 5.5 编译预处理 5.6 递归函数

1、什么是递归 2、递归函数举例 3、课堂讨论 4、斐波那契(Fibonacci) 数列 5、Hanoi塔问题

一个哄小宝宝睡觉前讲的经典故事： 从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。讲的什么故事呢？从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。讲什么故事呢？从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。讲的什么故事呢？从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。。。。。。

1、什么是递归 什么是递归：函数调用了自身(直接递归)。或一个函数调用了另一个函数，而另一个函数却调用了本函数(间接递归)。 从问题求解的角度来看，递归的本质就是将大问题的求解转化为较小问题的求解。持续不断的分解过程最终将问题化简成一个最基本的形式，并且是一个已知解。

2、递归函数举例 例：求N! int fact(int n) { if (n==1 || n==0) return 1; else return n*fact(n-1); }

例：求最大公约数的2个版本 int gcd(int a, int b)//递归版 { if(a%b==0) return b; else return gcd(b, a%b); } 迭代法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。 int gcd(int a, int b)//迭代版 { while(b!=0){ int t=a%b; a=b; b=t; } return a;

3、课堂讨论 问题一：已知每个同学的期中考试成绩，如何求出全班最高分？ 方法二？ 方法一？ 方法三？

问题二：如何编程实现ab？ 方法二？ 二分法 方法一？ 常规法 要点： a10 = a5*a5 ； a11 = a5*a5*a

4、斐波那契(Fibonacci) 数列 斐波那契（Leonardo Fibonacci，约1170－约1250），意大利数学家，12、13世纪欧洲数学界的代表人物。 他的一个“兔子问题”引起了后人的极大兴趣。题目假定一对大兔子每一个月可以生一对小兔子，而小兔子出生后两个月就有生殖能力，问从一对小兔子开始，n年后能繁殖成多少对兔子？这导致“斐波那契数列”：1，1，2，3，5，8，13，21，…，其规律是每一项（从第3项起）都是前两项的和。

问题：求fibonacci数列前40个数。数列第1，2两个数为1，1。从第3个数开始，该数是其前面两个数之和。即: f1=1 (n=1) f2=1 (n=2) fn=fn-1+fn-2 (n>2)

时间(月)  初生兔子(对) 成熟兔子(对)  兔子总数(对)  1 1 0 1 2 0 1 1 3 1 1 2 4 1 2 3 5 2 3 5 6 3 5 8 7 5 8 13 8 8 13 21 9 13 21 34 10 21 34 55 若把兔子总数(对)继续写下去，得到的数列便称为斐波那契数列。数列中每个数便是前两个数之和，而数列的最初两个数都是1。 数学上，一般设F0=1, F1=1；当n＞1时， Fn=Fn-1+Fn-2 。

求解斐波那契数列(迭代法) int fib(int n) { if(n<2) return 1; int f0=1，f1=1,f2; for(int i=2; i<=n; i++) f2=f0+f1; f0=f1; f1=f2; } return f2; 利用数组保存所有可能的结果，避免每次重新求解可提高效率。 PreProcess(a,40); 结果存入数组a while(cin>>n){ cout<<a[n]<<endl; } int main(){ int n; while(cin>>n){ cout<<fib(n)<<endl; } return 0;

求解斐波那契数列(递归法) int fib(int n) { if(n<2) return 1; else return fib(n-1)+fib(n-2); }

知道黄金分割率吗？ 当斐波那契数列趋向于无穷大时，相邻两项的比值趋向于黄金分割0.618。 课后建议：百度百科 - 斐波那契数列http://baike.baidu.com/view/816.htm 课后建议：百度百科 -计算思维 http://baike.baidu.com/view/3053744.htm?fr=aladdin

斐波那契螺旋线

递增的牛群（HLoj 1190） 开始有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

C1=1, C2=2, C3=3, C4=4, C5=6，... 且，当n＞3时，Cn = Cn-1 + Cn-3。 时间(年)  小牛 中牛 大牛  总数  1 0 0 1 1 2 1 0 1 2 3 1 1 1 3 4 1 1 2 4 5 2 1 3 6 6 3 2 4 9 7 4 3 6 13 8 6 4 9 19 9 9 6 13 28 10 13 9 19 41 数列特点： C1=1, C2=2, C3=3, C4=4, C5=6，... 且，当n＞3时，Cn = Cn-1 + Cn-3。

求解递增的牛群(递归法) int Cows(int n) { if(n<4) return n; else return Cows(n-1)+Cows(n-3); }

5、 Hanoi塔问题 设A、B、C是三个塔座。开始时，在塔座A上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起，如后图所示。现在要求将塔座A上的这一叠圆盘移到塔座B上，并仍按同样顺序叠置。在移到圆盘时应遵守以下移动规则： 规则(1)：每次只能移动一个圆盘； 规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则(3)：在满足移动规则(1)和(2)的前提下，可将圆盘移至A，B，C中任何一塔座上。

问题分析 设an表示从塔座A上的n个圆盘全部转移到另一根柱子上的转移次数。显然，a1 =1。当n≥2时，要将塔座A上的n个圆盘全部转移到塔座B上，可以这样设想： 先把塔座A上的 n-1个圆盘想法转移到塔座C上，这需要转移an-1次，然后把塔座A上的最后一个大圆盘转移到塔座B上，显然这需要转移1次，最后再把塔座C上的 n-1个圆盘转移到塔座B上，这也需要转移an-1 次。经过这些步骤后，所有塔座A上的n个圆盘就全部转移到塔座B上。根据加法规则，一共转移了2an-1 +1次。 可以建立如下的递归关系：

计算总的移动次数的递推公式如下 a1=1 an=2an-1+1 (n>1) 求解递推关系式,可得 an=2n-1                

// 求解hanoi 搬动过程的 参考代码 void move(char get, char put) { cout<<get<<"-->"<<put<<endl; } // 递归函数 void hanoi(int n, char from, char to, char by) if(n==1) move(from,to); else hanoi(n-1,from,by,to); hanoi(n-1,by,to,from); int main() { int n; cin>>n; // move n diskes From A To B By C hanoi(m,'A', 'B', 'C'); return 0; }

相关练习题 请使用递归法解决下列问题： 1111 判断回文串 1164 数字和 1190 母牛的故事 5017 最小公倍数 5018 求最大值 5020 求N! 6061 整数转换成字符串 6064 编写递归函数Ack(m，n) 6201 数组程序设计1