我在一次面试中被问到，解决问题的有效方法是检查回文。
现在我可以做两件事：
- 从 i = 0 开始到 i = n/2 并比较第 i 个和第 n 个字符是否相等。
- 我可以使用递归来检查第一个和最后一个是否相同，并且字符串的其余部分是否为回文。
第二个是递归的。我的问题是算法的递归和非递归版本的空间复杂度有什么区别？
阅读：
- http://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches http://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches
- 递归还是迭代？ https://stackoverflow.com/questions/72209/recursion-or-iteration
基本上，递归算法会增加开销，因为您将递归调用存储在执行堆栈中。
但如果递归函数是调用的最后一行（尾递归），则没有额外的惩罚。
这当然是两种算法是相同的。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
