递归算法的空间复杂度

Question

我在接受采访时被问及解决问题检查pallindrome的有效方法.

现在我可以做两件事:

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

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

Answer 1

请阅读

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

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

但是如果递归函数是调用的最后一行(尾递归),则没有额外的惩罚.

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