与多核时代的迭代相比,递归是首选吗？

Question

或者说,多核CPU是否比迭代更快地处理递归？

或者它只取决于一种语言在机器上的运行方式？与执行简单迭代相比,c执行函数调用成本较高.

我有这个问题,因为有一天我告诉我的一个朋友,递归并不是任何可以加速程序的神奇魔法,他告诉我,使用多核CPU递归可能比迭代更快.

编辑:

如果我们考虑最受递归喜欢的情况(数据结构,函数调用), 递归的速度是否更快？

编辑10月12日:

那么多核cpu如何表现呢？现在的软件都是针对多核cpu编程的吗？

Answer 1

实际上有两种方法来看待这个问题：

1.纯粹看编译后的代码，是的，迭代比递归更快。这是因为递归增加了函数调用（=开销），而迭代则没有。然而，常见的递归类型是尾递归：在函数末尾进行递归调用。这总是由编译器针对迭代进行优化。所以在这种情况下没关系。因此：在某些情况下，递归会更慢，但永远不会更快。

2.从函数式编程的角度来看，大多数时候递归函数被编写为没有副作用。（递归函数中存在副作用会使其产生正确的结果变得非常困难。）如果函数没有副作用，那么并行化就很简单（因此更容易在多核系统上运行）。这本身不是递归函数的属性，但这可能是您的朋友认为递归比迭代更快的原因。