ayu*_*hgp 3 algorithm recursion loops
是否有任何问题只能在递归或迭代中解决.如果没有,所有算法都可以以具有相同复杂度的任何一种形式表示吗？
PS:我说的是理论上的复杂性(O,theta和omega),而不是在实际系统中实现的时间.
递归和迭代同样具有表现力:递归可以用具有显式堆栈的迭代替换,而迭代可以用尾递归替换.[1]
所以不,每个可以迭代求解的问题都可以通过递归来解决,反之亦然.如果您进行1:1转换,则Big-O表示法保持不变.然而,在递归上使用迭代算法仍然会更好,因为你可以做不同的事情.
1:https://en.wikipedia.org/wiki/Recursion_ (computer_science)#Recursion_versus_iteration