C语言递归真题解析

  • 时间:
  • 浏览:
  • 来源:互联网

根据代码求递归的值

#include<stdio.h>
int cnt=0;
int fib(int n)
{
    cnt++;
    if(n==0)
       return 1;
    else if(n==1)
       return 2;
    else
       return fib(n-1)+fib(n-2);
}
void main()
{
   fib(8);
   printf("%d",cnt);
}

问最终的输出值为多少?
解析如下:
只有当fib(n)中n等于1或者0时,才能退出递归。
观察得到:每次进行一次递归运算,即每进行一次fib()运算,cnt自加一次
所以有以下结论:
fib(0): cnt(0)= 1 +0
fib(1): cnt(1)= 1 +0
fib(2)=fib(1)+fib(0): cnt(2)= 1 +cnt(1)+cnt(0)
fib(3)=fib(2)+fib(1): cnt(3)= 1 +cnt(2)+cnt(1)



fib(8)=fib(7)+fib(6): cnt(8)= 1 +cnt(7)+cnt(6)

注意此处的加1,为每次进入递归函数时,便会cnt自加一。所以要加一。
所以:
0:1;
1:1;
2:3;
3:5;
4:9;
5:15;
6:25;
7:41;
8:67;
所以最终的结果便是67;
您算对了吗。

本文链接http://metronic.net.cn/metronic/show-53464.html