对于内存占用来说，递归和循环中的哪个对资源的利用比较高效？

[Loop680]

请教一下前辈们，我刚开始学Python，看的是Python基础教程，第6.6章节里面提到了幂指数运算的例子：

循环版本
def power(x,n):
result = 1
for i in range(n):
result *= x
return result

递归版本
def power(x,n):
if n = 0:
return 1
else:
return x * power(x,n-1)

在前面的讲解中用了无限递归导致内存崩溃超过最大递归深度的例子，那是不是就说递归这种每次都调用自身的行为更加消耗内存资源呢？

[xpfd]

python机理不懂，从c语言角度解释一下递归和循环的区别吧，递归相当于不停的调用自身函数，每调用一次都会在栈上申请一次，所以如果递归次数过多会导致栈溢出，就跟吃饭一样，不停的吃不停的吃，一直吃到最后全吐出来。
而循环是每次申请一次栈，循环结束后函数返回会执行出栈操作，也就是说每次都是吃一口，吐出来，然后再吃一口吐出来，明白了吧

[est]

@Loop680 @xpfd 有个东西叫尾递归优化，实质就是把递归转换为循环。

[wy315700]

图灵曾经证明过，一切递归都可以用一个等价循环来完成。

[Loop680]

@xpfd 那即是说，递归的意义仅在于优雅？

[asassas]

是的，楼主可以google一下“Stack Frames”或者“栈帧”。
一般语言中，每次函数调用都会在栈上保存返回地址，分配局部变量等。
所以递归这种连续嵌套的函数调用就比较消耗内存，而循环不存在这些问题。
好像具有尾递归优化的语言能够避免这种内存消耗吧，python目前貌似还不支持。

[jox]

python不支持尾递归优化 循环只需要当前栈 递归会创建多个栈 但是循环的本质是递归 循环能处理的问题递归也能处理 递归能处理的问题循环只能处理一部分 使用python不需要考虑性能 尤其是新手 当性能成为问题的时候再考虑优化 绝大多数场合没有考虑递归与循环那个效率高的必要

[Loop680]

@jox 明白了，精简易读的代码才是首要追求的目标吧。

[mengzhuo]

CPython有个问题……就是递归不能超过99……╮(╯▽╰)╭

在占用方面自然是循环完胜，因为不需要建立执行空间

[xpfd]

@Loop680 我觉得主要是因为需要用递归的场景写起来逻辑比你转换成循环的要简单，跟优雅没什么关系,我认为代码在保证功能和性能的前提下，要尽量写的简单易懂，对于以后维护有很大的帮助

[xpfd]

@est 又学到一招了:) 不过实际工作中能不用递归就尽量不用递归，递归用不好很容易出事

[abscon]

@wy315700
那这个“等价的循环”是否需要手工维护一个堆栈？是的话并没有对资源的利用更高效。

@Loop680
困难的问题本质就是困难的，并不会由于换一种表达方式就变简单了。在需要维护历史记录时，不管循环还是递归对资源的利用都“不高效”。

只有在能做尾递归优化而又未做时，才可以说循环效率优于递归。
但不是什么情况都能做尾递归优化的。

[yueyoum]

用erlang吧， 递归既符合我个人的思维，代码也好写

[wy315700]

@abscon 是算法层面的。不需要模拟一个栈

[withrock]

递归优美，自上而下；但循环更高效，自下而上。

[jox]

在写程序的时候递归和循环在表达力上是等价的 可以互相转换 有些递归需要记录每次递归开始时的状态 如果使用循环可以借助创建用户栈来记录这些状态来模拟递归 这样在内存占用上循环没有太大优势 但是在缺少尾递归优化支持的时候依然会减少函数调用带来的支出 不需要记录状态的问题 在有尾递归优化的时候循环在效率上的优势是微乎其微的

但是有些问题用递归解决很自然 比如树的遍历 比如需要divide and conquer策略的算法 有些问题用循环解决很自然 比如列表的遍历
这样的时候选择最合适的手段解决问题是很自然的 让编译器去做优化工作就行了 但是因为大多数时候递归的程序都很简短和优雅 所以有些人会偏爱递归

[tftk]

递归是计算机的精髓所在。

[eriale]

python不支持尾递归，所以能用循环，尽量用循环，不到万不得已的时候，不要用递归。
如果在产品开发中要用递归，最好也确认递归层数比较少。

[abscon]

@wy315700 换一种问法：把任意递归算法转换成循环时，算法的时间或者空间复杂度是否保持不变？或者必然降低？

因为@Loop680 问的是“对资源的利用比较高效”。

[wy315700]

@abscon 这就没研究过了，没有那么深的内功

[Loop680]

@abscon 嗯对，我也想问关于算法的执行时间会不会有所提高。尽可能地追求效率嘛。