关于一种计算递归次数题的思路

是一小朵云呀

代码如下
要求计算最后输出的count的结果

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int count = 0;
int fib(int a)
{
	count++;
	if (a == 0)
		return 1;
	else if (a == 1)
		return 2;
	else
		return fib(a - 1) + fib(a - 2);
}
int main()
{
	fib(10);
	printf("%d", count);
}

当遇到此类检索递归调用次数的题目，我们可以以由简到繁的思路来解决

我们看到，上面的例题直接进行计算是很复杂的，如果从输入的数字10开始解决，一步一步按顺序罗列，最终要计算的数字几乎是天文的（不过也没那么夸张，真硬算也能算）

此时对于这类递归，我们可以倒着来，从简单的数入手

我们可以先计算fib(0)，此时显然，主函数的打印结果为1，因为count++;语句只被执行了一次

我们再来计算fib(1)，同样count++;语句只被执行了一次

再看fib(2),当输入的值为2，我们执行else后的语句fib(1) + fib(0),神奇的事情发生了，我们发现计算fib(2)的结果正好是fib(1)和fib(0)的结果之和再加上1（这里1是首次进入函数时count++的值，也就是执行fib(2)的这次）

那么计算方式就很明确了，我们只需要依次计算下去，很容易就能得到fib(10)输出的count的值

比如fib(3)的count的值就等于fib(2)和fib(1)的count值再加一，fib(4)的count的值等于fib(3)的count的值加fib(2)的count的值再加1，以此类推，最后得到结果为177

来源：https://www.cnblogs.com/827-s/p/19201029