关于一种计算递归次数题的思路
<p>代码如下<br>要求计算最后输出的count的结果</p>
<pre><code>#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);
}
</code></pre>
<p>当遇到此类检索递归调用次数的题目，我们可以以由简到繁的思路来解决</p>
<p>我们看到，上面的例题直接进行计算是很复杂的，如果从输入的数字10开始解决，一步一步按顺序罗列，最终要计算的数字几乎是天文的（不过也没那么夸张，真硬算也能算）</p>
<p>此时对于这类递归，我们可以倒着来，从简单的数入手</p>
<p>我们可以先计算<code>fib(0)</code>，此时显然，主函数的打印结果为1，因为<code>count++;</code>语句只被执行了一次</p>
<p>我们再来计算<code>fib(1)</code>，同样<code>count++;</code>语句只被执行了一次</p>
<p>再看<code>fib(2)</code>,当输入的值为2，我们执行<code>else</code>后的语句<code>fib(1) + fib(0)</code>,神奇的事情发生了，我们发现计算<code>fib(2)</code>的结果正好是<code>fib(1)</code>和<code>fib(0)</code>的结果之和再加上1（这里1是首次进入函数时<code>count++</code>的值，也就是执行fib(2)的这次）</p>
<p>那么计算方式就很明确了，我们只需要依次计算下去，很容易就能得到<code>fib(10)</code>输出的count的值</p>
<p>比如<code>fib(3)</code>的count的值就等于<code>fib(2)</code>和<code>fib(1)</code>的count值再加一，<code>fib(4)</code>的count的值等于<code>fib(3)</code>的count的值加<code>fib(2)</code>的count的值再加1，以此类推，最后得到结果为177</p><br><br>
来源：https://www.cnblogs.com/827-s/p/19201029
頁:
[1]