为什么基于堆栈的迭代并不比 C 中的递归更好？（以斐波那契数为例）

What I'd like to know about is that if implementing an identical algorithm to the recursive one attacking the same problem in custom stacks and iteration can improve the performance!

This assumes the algorithms are actually identical. Your stack-based algorithm isn't identical to the recursive version - for one thing, you're performing a lot more assignments and tests in the stack-based version than the recursive version, which kills any gains you make by not calling the function recursively. Secondly, the recursive version is (most likely) passing arguments via registers, not the stack.

On my system, turning on level 1 optimization significantly improves the runtime performance of the stack-based version relative to the recursive version (to where the stack-based version takes much less time than the recursive version). On my system, going from -O0 to -O1 speeds up the recursive version by ~26% and the stack-based version by ~67%.

And for what it's worth, this is a naive iterative implementation of fibonacci:

unsigned long fib_it( int n )
{
  /**
   * Circular buffer to store the
   * intermediate values
   */
  unsigned long f[3] = { 0ul, 1ul, 1ul };

  if ( n <= 2 )
    return f[n];

  int i;
  for ( i = 3; i <= n; i++ )
    f[i % 3] = f[(i-1) % 3] + f[(i-2) % 3];

  return f[(i+2) % 3];
}

which absolutely spanks the recursive and stack-based versions in terms of both run time and memory usage as n gets large (you basically just have to worry about overflow). As others have shown there are faster algorithms that minimize the number of intermediate calculations, and there is a closed-form version that's faster yet.

If a recursive algorithm is executing too slowly for you, you don't speed it up by re-implementing the recursiveness of it with your own stacks - you speed it up by using a non-recursive approach. As a definition of the Fibonacci function, F_n = F_n-1 + F_n-2 is compact and easy to understand, but as an implementation of the function it is horribly inefficient because it computes the same values multiple times. The iterative version above computes each value exactly once.

What makes recursive functions like quicksort fast is that they dramatically reduce the size of the problem space with each call. Recursive fibonacci doesn't do that.

Edit

一些数字。我的测试工具有两个参数——要计算的第 N 个数字，以及要使用的算法——s用于基于堆栈的版本、r递归和i我上面的迭代版本。对于小 N，差异并不太明显（用 编译-O1）：

$ ./fib -n 5 -r
   i          F(i)    clocks   seconds
   -          ----    ------   -------
   5             5         1  0.000001

$ ./fib -n 5 -s
   i          F(i)    clocks   seconds
   -          ----    ------   -------
   5             5         2  0.000002

$ ./fib -n 5 -i
   i          F(i)    clocks   seconds
   -          ----    ------   -------
   5             5         2  0.000002

但是，随着 N 变大，差异就显现出来了：

$ ./fib -n 40 -r
   i          F(i)    clocks   seconds
   -          ----    ------   -------
  40     102334155    543262  0.543262

$ ./fib -n 40 -s
   i          F(i)    clocks   seconds
   -          ----    ------   -------
  40     102334155    330824  0.330824

$ ./fib -n 40 -i
   i          F(i)    clocks   seconds
   -          ----    ------   -------
  40     102334155         2  0.000002

一旦超过 N=50，递归和基于堆栈的版本的运行时间就会变得非常长，而迭代版本的运行时间不会改变：

 $ ./fib -n 50 -r
   i          F(i)    clocks   seconds
   -          ----    ------   -------
  50   12586269025  66602759 66.602759

 $ ./fib -n 50 -s
   i          F(i)    clocks   seconds
   -          ----    ------   -------
  50   12586269025  39850376 39.850376

 $ ./fib -n 50 -i
   i          F(i)    clocks   seconds
   -          ----    ------   -------
  50   12586269025         2  0.000002

现在，这就是我的系统上的行为方式，这是使用非常粗糙的仪器（对 的几次调用clock）的第 0 级分析。