space-complexity - 递归算法的空间复杂度

Question

我在一次采访中被问到，解决检查回文问题的有效方法。

现在我可以做两件事：

1. 从 i = 0 到 i = n/2 并比较第 i 个和第 n 个字符是否相等。
2. 我可以使用递归来检查第一个和最后一个是否相同，并且字符串的其余部分是一个回文。

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

Answer 1

阅读

1. http://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches
2. 递归还是迭代？

基本上，递归算法会增加开销，因为您将递归调用存储在执行堆栈中。

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

那当然两种算法是相同的。

Answer 2

理论上它们具有相同的空间复杂度；这在很大程度上取决于是否可以优化尾递归。

如果是这样，堆栈在每次递归时都会被替换，因此不会产生惩罚。