递归算法的空间复杂度

我在采访时被问到解决检查pallindrome问题的有效方法。递归算法的空间复杂度

现在我可以做两两件事：

从i开始= 0到i = N/2和比较第i和n i个字符为相等。
我可以使用递归来检查第一个和最后一个是否相同，而其余的字符串是pallindrome。

第二个是递归的。我的问题是算法的递归和非递归版本的空间复杂度有什么区别？

来源

2012-05-30 dharam

在

有一个读基本上，因为你存储在执行堆栈的递归调用递归算法会增加开销。

但是，如果递归函数是调用的最后一行（尾递归），那么没有额外的惩罚。

那当然两种算法都是一样的。

来源

2012-05-30 17:22:42 Yannis

理论上它们具有相同的空间复杂度;它在很大程度上取决于tail recursion是否可以优化。

如果是这样，堆栈会在每次递归时被替换，所以不会受到惩罚。

来源

2012-05-30 17:20:37

对于大型数据集，即使使用尾递归，也会导致StackOverflow错误。没有？ – Sudhakar

@Sudhakar这正是尾递归优化防止:) –

这个程序是一个有效的尾递归的例子。这产生了计算器。请纠正我，如果我错了。

 public class TailTest { \t public static void main(String[] args) { \t \t System.out.println(TailTest.iterate(100000)); \t } \t \t public static long iterate(int n){ \t \t if(n==1) return 1; \t \t \t \t return iterate(n-1); \t } }

– Sudhakar

递归算法的空间复杂度

回答

相关问题