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

[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)

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

[znoodl]

所有的递归都可转换成非递归，分为直接转换和间接转换，间接转换用栈模拟调用

[besto]

楼上该说的都说了，补充几点：
1. 递归确实可以用循环替代，但是尾递归优雅（不是好看的意思）。
2. 尾递归程序不是那么容易写的，参考Lisp的程序，但尾递归的开销约等于循环。
3. 非尾递归会引起栈崩，100，1000，1w，10w，100w来测试qsort，总有能蹦的时候
4. Python类似的高级语言，考虑这种细节意义不是太大。

[Loop680]

@besto 学到了很多意外的知识啊，好开心，多谢多谢

[besto]

@Loop680 刚学习某种语言，纠结这个，不如继续学习点python特性。
语言具有相同性，你这个问题，恰恰不是python独有的，C也有，Java也有(当然Lisp没有...)
====================================================================
很多程序员最终的代码都是控制逻辑，而非算法逻辑。。。。

[Bluecoda]

递归的好处是高级的抽象

上面解释了很多，递归因为种种原因，达不到循环的性能。唯一能够达到循环的性能的，就是优化过的尾递归。

[Loop680]

@besto 今天看书的时候偶尔想到的一点东西，不是特别明白就来问一下，没有纠结的。^_^

[yunshansimon]

递归用在处理链表上，你如果不是链表结构的话，就不要用递归了。

[alsotang]

循环和尾递归都内存友好，递归的话，不好判断

[kingcos]

。。。你可以看中国MOOC大学的数据结构，浙大的，就讲这个了！！
不过他举例的是C语言。。。我现在大概给你说说吧，不知道对不对呢~~~
他举例：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印1到N的全部正整数。
然后用递归，当n = 100，000时，递归就直接崩溃了，而循环的话，就没问题，你可以试下~
他的说明：递归虽然可以让我们更加清晰的写出代码，但是计算机不愿意做递归：因为递归对空间的占用过于庞大，超过了他能占用的空间，程序没有打出一个数字就崩溃了。

PS我也准备学python呢。。。刚学完C就学python会不会有些过快呢？
@Loop680

[kingcos]

忘了解释了= =
for循环：空间占用永远是个常量，不会随着n的增长而增长对内存的占用。
递归：当n越大时，S（n）呈线性增长，而这个函数所占空间是有限的，当把他的有限空间用完，程序就会崩溃。（S(n)是空间复杂度~：根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。）

[327beckham]

递归不太好，果断循环。

[1023400273]

@xpfd 通俗易懂啊