C语言数据结构递归之斐波那契数列

首先,关于递归深度,递归提供了一个简单的定义。如果调用Fibonacci(),当n为1或2时Fibonacci(n)应返回1;对于其他数值应返回Fibonacci(n-1)+Fibonacci(n-2);

longFibonacci(n){if(n>2)returnFibonacci(n-1)+Fibonacci(n-2);elsereturn1;}

然后是兔子总数问题。

有一对兔子,从出生后第三个月起每个月都生一对兔子,小兔子长到第三个月后又生一对兔子,假如兔子都不死,每个月兔子对数为多少?

思考这道题的时候,如果你简单的推算一下,会发现兔子每个月的对数就是斐波那契数列。

第一个月:1对;
第二个月:1对;
第三个月:2对;
第四个月:3对:
第五个月:5对:
第六个月:8对;
……

我之前做这道题的时候,觉得思路很简单,就是从第三个月起,求每个月的兔子数时,只要把这个月的前两个月总数相加。
这是我之前的代码,用f1和f2表示月。:

#include<stdio.h>intmain(){intf1,f2;intmonth,ct;printf("请输入月份:");scanf("%d",&month);if(month<=2)printf("两只。\n");if(month>2){f1=f2=1;ct=0;while(ct<month-2){f1=f1+f2;ct+=1;f2=f1+f2;ct+=1;}if(month%2==0){printf("第%d个月的兔子对数为:%d.\n",month,f2);}if(month%2==1){printf("第%d个月的兔子对数为:%d.\n",month,f1);}}return0;}

其实这个代码离递归就差一步,很接近了。但是我当时完全没有想到。

这是我重新修改之后的代码:

#include<stdio.h>longFibonacci(n){if(n>2)returnFibonacci(n-1)+Fibonacci(n-2);elsereturn1;}intmain(){longnum;intmonth;printf("请输入月份:");scanf("%d",&month);num=Fibonacci(month);printf("这个月的兔子对数为%d.\n",num);return0;}