我们如何计算朴素斐波那契的调用次数？
How do we calculate number of calls in naive fibonaci?
所以下面不是优化的斐波那契函数：
sub fib {
my ( $n ) = @_;
return 1 if( $n == 1 || $n == 2 );
return fib( $n - 1 ) + fib( $n - 2 );
}
当我们试图找到 20 的斐波那契时，我实际上打印了 fib(3) 被调用的次数。
是2584。fib(2)被称为4181。
据我所知，这个算法表现出指数行为。
我的问题是，如果没有 在代码中实际保留一个计数器并打印函数调用，我如何计算 fib(3) 会被调用 2584 次 ？指数部分是如何计算的？
我相信这是 Target - desired number + 1 处的斐波那契数，所以在询问 fib(3) 在 fib(20) 中被调用的次数是多少的情况下，它将是 fib(20 - 3 + 1)（即fib(18) = 2584）。
如果你画出代表斐波那契调用的树，你可以自己看到！
fib(i) 仅从 fib(i+1) 和 fib(i+2) 直接调用，并且每次调用一次。
因此calls(i)（fib(i)的调用次数）等于calls(i+1) + calls(i+2)
因此，如果我们从 m 开始并尝试计算 calls(n)，我们将得到以下结果：
calls(m) = 1 (= fib(1))
calls(m-1) = 1 (= fib(2))
calls(m-2) = 2 (1+1) (= fib(3))
calls(m-3) = 3 (1+2) (= fib(4))
calls(m-4) = 5 (2+3) (= fib(5))
...
这就是我们要计算第 m-n+1 个数字的斐波那契数列
（要了解为什么它恰好是 m-n+1，请考虑何时 n = m，它应该是 fib(1)）。
calls(n) = fib(m-n+1)
我们可以在这里使用优化的斐波那契函数来有效地（在线性时间内）计算 fib(m-n+1)，这将是未优化版本中 fib(n) 的调用次数。
对于您的示例，如果您调用 fib(20)，fib(3) 会被调用 2584 次。
fib(20-3+1) = fib(18) = 2584.
注：calls(1) = calls(3)（因为fib(2)不调用fib(1)），所以这是一个特例。
Dukeling 向您展示了 fib(3) 被调用次数的顺序：fib(20) (m) 被调用一次，fib(19) (m-1) 被调用一次，然后 fib(18) 被调用一次时间 fib(19) 或 fib(20) 被调用，总计 1+1.
当我们沿着序列向下移动以查找 fib(3) 被调用的次数时，您会注意到数字（和计算）与斐波那契数列本身相对应。我们从 20 下降到 3，所以 m - n + 1 步，每一步都对应下一个斐波那契数。等到调用了多少次fib(3)(fib(n))时，序列已经到了第m-n+1个斐波那契数，对应调用了多少次f(n)在未优化的递归期间。
所以下面不是优化的斐波那契函数：
sub fib {
my ( $n ) = @_;
return 1 if( $n == 1 || $n == 2 );
return fib( $n - 1 ) + fib( $n - 2 );
}
当我们试图找到 20 的斐波那契时，我实际上打印了 fib(3) 被调用的次数。
是2584。fib(2)被称为4181。
据我所知，这个算法表现出指数行为。
我的问题是，如果没有 在代码中实际保留一个计数器并打印函数调用，我如何计算 fib(3) 会被调用 2584 次 ？指数部分是如何计算的？
我相信这是 Target - desired number + 1 处的斐波那契数，所以在询问 fib(3) 在 fib(20) 中被调用的次数是多少的情况下，它将是 fib(20 - 3 + 1)（即fib(18) = 2584）。
如果你画出代表斐波那契调用的树，你可以自己看到！
fib(i) 仅从 fib(i+1) 和 fib(i+2) 直接调用，并且每次调用一次。
因此calls(i)（fib(i)的调用次数）等于calls(i+1) + calls(i+2)
因此，如果我们从 m 开始并尝试计算 calls(n)，我们将得到以下结果：
calls(m) = 1 (= fib(1))
calls(m-1) = 1 (= fib(2))
calls(m-2) = 2 (1+1) (= fib(3))
calls(m-3) = 3 (1+2) (= fib(4))
calls(m-4) = 5 (2+3) (= fib(5))
...
这就是我们要计算第 m-n+1 个数字的斐波那契数列
（要了解为什么它恰好是 m-n+1，请考虑何时 n = m，它应该是 fib(1)）。
calls(n) = fib(m-n+1)
我们可以在这里使用优化的斐波那契函数来有效地（在线性时间内）计算 fib(m-n+1)，这将是未优化版本中 fib(n) 的调用次数。
对于您的示例，如果您调用 fib(20)，fib(3) 会被调用 2584 次。
fib(20-3+1) = fib(18) = 2584.
注：calls(1) = calls(3)（因为fib(2)不调用fib(1)），所以这是一个特例。
Dukeling 向您展示了 fib(3) 被调用次数的顺序：fib(20) (m) 被调用一次，fib(19) (m-1) 被调用一次，然后 fib(18) 被调用一次时间 fib(19) 或 fib(20) 被调用，总计 1+1.
当我们沿着序列向下移动以查找 fib(3) 被调用的次数时，您会注意到数字（和计算）与斐波那契数列本身相对应。我们从 20 下降到 3，所以 m - n + 1 步，每一步都对应下一个斐波那契数。等到调用了多少次fib(3)(fib(n))时，序列已经到了第m-n+1个斐波那契数，对应调用了多少次f(n)在未优化的递归期间。