algorithm - 是否存在只能递归或只能迭代解决的问题？

Question

有没有什么问题只能用递归或迭代来解决。如果不是，是否可以将所有算法都表示为具有相同复杂度的任一形式？

PS:我说的是理论上的复杂性(O、theta 和 omega)，而不是在现实世界系统中实现时所花费的时间。

Answer 1

Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with tail recursion.[1]

所以不，每个可以迭代解决的问题都可以用递归解决，反之亦然。如果进行 1:1 转换，Big-O 表示法保持不变。但是，与递归算法相比，使用迭代算法仍然更好，因为您可以做不同的事情。

1:https://en.wikipedia.org/wiki/Recursion_(computer_science)#Recursion_versus_iteration