为什么C语言中基于栈的迭代性能未优于递归？以斐波那契数为例
简要介绍
（小幅编辑：我提出这个问题的初衷并非讨论算法本身。我完全清楚使用3个局部变量或长度为3的数组实现的快速迭代解法。实际上我刻意让两个测试方案的复杂度差异尽可能降到最低。我想了解的是，使用自定义栈和迭代实现与递归完全相同的算法，是否能够提升性能！）
我们在学校学习编程时，通常会被告知一般情况下迭代比递归效率更高，除非递归能提供更特定、更优雅的问题解决方式。
因此我最近决定做一个简单测试。由于函数调用本质上是通过调用栈处理的，因此可以实现自定义栈来管理所需的局部变量，将递归实现改写为迭代版本。以下是我用C语言实现的斐波那契数计算器，包含递归版本和理论上等价的迭代算法版本。
测试方法
递归实现 (fibon_recu):
uint64_t calls = 0; /* Calculate Fibonacci number using recursive algorithm. */ uint64_t fibonacci(uint8_t idx) { calls++; return (idx <= 1) ? idx : (fibonacci(idx - 1) + fibonacci(idx - 2)); }
迭代实现 (fibon_iter):
uint64_t loop_count; /* Calculate Fibonacci number using stack-based method derived from recursive algorithm. */ uint64_t fibonacci(uint8_t idx) { uint64_t ret = 0; uint8_t stack_val[ARR_STACK_SIZE], cache; uint16_t stack_size; loop_count = 0; // Push index into simulated stack stack_size = 1; *stack_val = idx; while(stack_size) { // Pop simulated stack top stack_size -= 1; cache = *(stack_val + stack_size); if(cache > 1) { // Push <index - 1> and <index - 2> into simulated stack *(stack_val + stack_size) = cache - 1; *(stack_val + stack_size + 1) = cache - 2; stack_size += 2; } else { ret += cache; } loop_count++; } return ret; }
有开发者提出过如下观点：
根据栈的实现方式不同，栈可能最终需要在堆中动态分配内存，这通常比栈帧的创建和销毁开销更高。通常而言，如果你有两个算法想要对比实际性能，最好直接运行两者对比结果。
这一点在我的测试设备上确实得到了验证，我决定使用静态数组模拟栈，因为静态数组本身会分配在栈帧中而非堆上。在我的设备上，这种场景下访问堆中的变量会让性能下降约20-30倍（数据图未在此展示）。
也有开发者提到，使用自定义栈的迭代实现有时可以提升性能，我认为这一点非常有趣。
另外，为了尽可能保证对比公平，我使用-O0参数编译两段代码，禁用所有编译器优化。
测试结果
测试结果对比了递归实现fibon_recu和迭代实现fibon_iter的性能，测试使用的gcc版本、设备基础信息也同步附在结果中。
更新内容
<2021年9月7日 11:00 UTC>
感谢开发者Ian Abbott指出，在-O0参数下使用指针访问代替索引访问可以提升性能。这使得迭代测试的执行时间下降到仅比递归测试略长的水平。
<2021年9月7日 22:45 UTC>
感谢各位开发者提供的见解甚至详细测试！我阅读了这些回答后做了更新，同时将问题标记为已解决。不过，请阅读下方所有回答，它们都提供了不同但重要的视角！
首先，开发者Eugene指出，即使使用-O0参数，函数调用本身也可能被优化，而自制的栈实现不会被优化。因此正如开发者Lundin所说，-O0实际上仍然不是公平的测试条件。
第二，开发者Jacon指出，在-O1及更低优化等级下，编译器可能不会替换尾递归，而开发者John进行的测试显示，-O1可以让基于栈的迭代测试性能大幅提升。
上述回答提到的汇编输出和结果如下：
-O1编译等级：- 迭代版本汇编代码
- 递归版本汇编代码
- 测试结果：该等级下迭代性能远优于递归
-O2编译等级：- 迭代版本汇编代码
- 递归版本汇编代码
- 测试结果：该等级下尾递归被优化，递归实现性能相比
-O1有明显提升
结果显示，Eugene提到的编译器行为在我的测试环境中确实成立：-O1参数保留了所有递归bl调用，而-O2参数优化了尾部bl调用。John观察到的性能提升也可以在我的设备上复现。
因此我推测，测试结果表明指令复杂度和递归调用在效率和性能上是相互竞争的因素。-O0参数完全不会优化自制栈，导致额外的复杂度抵消了迭代的优势。-O1参数保留了递归调用，同时优化了迭代实现，让后者获得性能提升。-O2参数消除了尾递归，让递归实现的性能比-O1下更好，再次凸显了两者的竞争关系。
原始问题
为什么看起来等价的迭代实现性能仍然没有优于递归？是我有什么明显的错误，还是有什么隐藏在表象之下的因素？
感谢！
内容的提问来源于stack exchange，提问作者Zevin Zenph Zambori
