如何计算fibonacci函数的递归调用次数

#include <stdioh>

long Fib(int n);

int count;

int main()

{

int n, i, x;

printf("Input n:");

scanf("%d", &n);

for (i = 1 ; i <= n; i++)

{

count = 0;

x = Fib(i);

printf("Fib(%d)=%d, count=%d\n", i, x, count);

}

return 0;

}

long Fib(int n)

{

count++;

if (n == 0) return 0;

else if (n == 1) return 1;

else return (Fib(n - 1) + Fib(n - 2));

}

这个程序是用来实现几个数的相加（我的理解），最后一个输出是加法的最终结果。

首先用我的语言解释一下递归的意义。递归算法就像是一些嵌套的屋子，每一层屋子里都有一个你想拿到的东西，你从最外层的门开始进去，但是你进的时候并不取走东西，而是等到你到达最里面的屋子时，取出这个最里面的东西，并开始往外走，到次里层屋子取出东西，继续往外走，重复这个动作，一直到你取出最外面屋子里的东西并跳出整个屋子。

下面针对你的程序用上面的思想来解释一下：

现在你要实现几个数的和，你每一次输入的数字相当于进入下一层屋子的钥匙。第一次输入的是1，你进到第一层，把1先存在这里，并不作加法，第二次输入2，进到第二层，把2放在这一层，然后输入3，进入第三层，把3放在这里，最后输入0，你进入了最里面的屋子，此时执行了

if(x==0) sum=0; //else 就不执行了，所以也没有后续的test(sum)

cout<<sum<<endl; //这时第一次输出sum,为0。

现在从最里面该往外走了，首先到了第三层，这里有你存着的数字3，现在，把刚才得到的sum=0与3相加，得到了sum=3,并输出。

再往外走，用sum=3和这里存的2相加，得到sum=5，并输出。

最后一层，肯定就得到了6。

这样讲解不知道你明白了没有？希望对你有帮助！

几乎每一本c

语言基础的书都讲到了函数递归的问题，但是初学者仍然容易在这个地方犯错误。先看看下面的例子：

void

fun(int

i)

{

if

(i>0)

{

fun(i/2);

}

printf("%d\n",i);

}

intmain()

{

fun(10);

return

0;

}

问：输出结果是什么？

这是我上课时，一个学生问我的问题。他不明白为什么输出的结果会是这样：

0

1

2

5

10

他认为应该输出0。因为当i

小于或等于0

时递归调用结束，然后执行printf

函数打印i

的值。

这就是典型的没明白什么是递归。其实很简单，printf("%d\n",i);语句是fun

函数的一部分，肯定执行一次fun

函数，就要打印一行。怎么可能只打印一次呢？关键就是不明白怎么展开递归函数。展开过程如下：

void

fun(int

i)

{

if

(i>0)

{

//fun(i/2);

if(i/2>0)

{

if(i/4>0)

{

…

}

printf("%d\n",i/4);

}

printf("%d\n",i/2);

}

printf("%d\n",i);

}

这样一展开，是不是清晰多了？其实递归本身并没有什么难处，关键是其展开过程别弄错了。

二、不使用任何变量编写strlen

函数

看到这里，也许有人会说，strlen

函数这么简单，有什么好讨论的。是的，我相信你能熟练应用这个函数，也相信你能轻易的写出这个函数。但是如果我把要求提高一些呢：

不允许调用库函数，也不允许使用任何全局或局部变量编写intmy_strlen

(char

strdest);似乎问题就没有那么简单了吧？这个问题曾经在网络上讨论的比较热烈，我几乎是全程“观战”，差点也忍不住手痒了。不过因为我的解决办法在我看到帖子时已经有人提出了，所以作罢。

解决这个问题的办法由好几种，比如嵌套有编语言。因为嵌套汇编一般只在嵌入式底层开发中用到，所以本书就不打算讨论c

语言嵌套汇编的知识了。有兴趣的读者，可以查找相关资料。

也许有的读者想到了用递归函数来解决这个问题。是的，你应该想得到，因为我把这个问题放在讲解函数递归的时候讨论。既然已经有了思路，这个问题就很简单了。代码如下：

intmy_strlen(

const

char

strdest

)

{

assert(null

!=

strdest);

if

('\0'

==

strdest)

{

return

0;

}

else

{

return

(1

+

my_strlen(++strdest));

}

}

第一步：用assert

宏做入口校验。

第二步：确定参数传递过来的地址上的内存存储的是否为'\0'。如果是，表明这是一个空字符串，或者是字符串的结束标志。

第三步：如果参数传递过来的地址上的内存不为'\0'，则说明这个地址上的内存上存储的是一个字符。既然这个地址上存储了一个字符，那就计数为1，然后将地址加1

个char类型元素的大小，然后再调用函数本身。如此循环，当地址加到字符串的结束标志符'\0'时，递归停止。

当然，同样是利用递归，还有人写出了更加简洁的代码：

intmy_strlen(

const

char

strdest

)

{

return

strdest1+strlen(strdest+1):0;

}

这里很巧妙的利用了问号表达式，但是没有做参数入口校验，同时用strdest

来代替('\0'==

strdest)也不是很好。所以，这种写法虽然很简洁，但不符合我们前面所讲的编码规范。可以改写一下：

intmy_strlen(

const

char

strdest

)

{

assert(null

!=

strdest);

return

('\0'

!=

strdest)(1+my_strlen(strdest+1)):0;

}

上面的问题利用函数递归的特性就轻易的搞定了，也就是说每调用一遍my_strlen

函数，其实只判断了一个字节上的内容。但是，如果传入的字符串很长的话，就需要连续多次函数调用，而函数调用的开销比循环来说要大得多，所以，递归的效率很低，递归的深度太大甚至可能出现错误（比如栈溢出）。所以，平时写代码，不到万不得已，尽量不要用递归。即便是要用递归，也要注意递归的层次不要太深，防止出现栈溢出的错误；同时递归的停止条件一定要正确，否则，递归可能没完没了。