推荐学习书目
› Learn Python the Hard Way
Python Sites
› PyPI - Python Package Index
› http://diveintopython.org/toc/index.html
› Pocoo
值得关注的项目
› PyPy
› Celery
› Jinja2
› Read the Docs
› gevent
› pyenv
› virtualenv
› Stackless Python
› Beautiful Soup
› 结巴中文分词
› Green Unicorn
› Sentry
› Shovel
› Pyflakes
› pytest
Python 编程
› pep8 Checker
Styles
› PEP 8
› Google Python Style Guide
› Code Style from The Hitchhiker's Guide
这是一个创建于 3433 天前的主题，其中的信息可能已经有所发展或是发生改变。
请教一下前辈们，我刚开始学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)
在前面的讲解中用了无限递归导致内存崩溃超过最大递归深度的例子，那是不是就说递归这种每次都调用自身的行为更加消耗内存资源呢？
循环版本
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)
在前面的讲解中用了无限递归导致内存崩溃超过最大递归深度的例子，那是不是就说递归这种每次都调用自身的行为更加消耗内存资源呢？
 |
1
xpfd 2014-12-02 09:32:34 +08:00  2
python机理不懂，从c语言角度解释一下递归和循环的区别吧，递归相当于不停的调用自身函数，每调用一次都会在栈上申请一次，所以如果递归次数过多会导致栈溢出，就跟吃饭一样，不停的吃不停的吃，一直吃到最后全吐出来。
而循环是每次申请一次栈，循环结束后函数返回会执行出栈操作，也就是说每次都是吃一口，吐出来，然后再吃一口吐出来，明白了吧 |
 |
3
wy315700 2014-12-02 09:40:03 +08:00 2
图灵曾经证明过，一切递归都可以用一个等价循环来完成。
|
 |
5
asassas 2014-12-02 09:47:41 +08:00 1
是的，楼主可以google一下“Stack Frames”或者“栈帧”。
一般语言中，每次函数调用都会在栈上保存返回地址，分配局部变量等。 所以递归这种连续嵌套的函数调用就比较消耗内存，而循环不存在这些问题。 好像具有尾递归优化的语言能够避免这种内存消耗吧，python目前貌似还不支持。 |
 |
6
jox 2014-12-02 09:47:50 +08:00 via iPhone 1
python不支持尾递归优化 循环只需要当前栈 递归会创建多个栈 但是循环的本质是递归 循环能处理的问题递归也能处理 递归能处理的问题循环只能处理一部分 使用python不需要考虑性能 尤其是新手 当性能成为问题的时候再考虑优化 绝大多数场合没有考虑递归与循环那个效率高的必要
|
 |
8
mengzhuo 2014-12-02 09:52:35 +08:00 1
CPython有个问题……就是递归不能超过99……╮(╯▽╰)╭
在占用方面自然是循环完胜，因为不需要建立执行空间 |
|
9
xpfd 2014-12-02 09:56:11 +08:00 1
@Loop680 我觉得主要是因为需要用递归的场景写起来逻辑比你转换成循环的要简单，跟优雅没什么关系,我认为代码在保证功能和性能的前提下，要尽量写的简单易懂，对于以后维护有很大的帮助
|
 |
11
abscon 2014-12-02 10:01:17 +08:00 1
|
 |
12
yueyoum 2014-12-02 10:01:39 +08:00 1
用erlang吧， 递归既符合我个人的思维，代码也好写
|
 |
14
withrock 2014-12-02 10:06:42 +08:00 1
递归优美，自上而下；但循环更高效，自下而上。
|
|
15
jox 2014-12-02 10:22:18 +08:00 via iPhone 1
在写程序的时候递归和循环在表达力上是等价的 可以互相转换 有些递归需要记录每次递归开始时的状态 如果使用循环可以借助创建用户栈来记录这些状态来模拟递归 这样在内存占用上循环没有太大优势 但是在缺少尾递归优化支持的时候依然会减少函数调用带来的支出 不需要记录状态的问题 在有尾递归优化的时候循环在效率上的优势是微乎其微的
但是有些问题用递归解决很自然 比如树的遍历 比如需要divide and conquer策略的算法 有些问题用循环解决很自然 比如列表的遍历 这样的时候选择最合适的手段解决问题是很自然的 让编译器去做优化工作就行了 但是因为大多数时候递归的程序都很简短和优雅 所以有些人会偏爱递归 |
 |
16
tftk 2014-12-02 10:25:02 +08:00 1
递归是计算机的精髓所在。
|
 |
17
eriale 2014-12-02 10:27:49 +08:00
python不支持尾递归，所以能用循环，尽量用循环，不到万不得已的时候，不要用递归。
如果在产品开发中要用递归，最好也确认递归层数比较少。 |
|
18
abscon 2014-12-02 10:31:39 +08:00
|
 |
21
znoodl 2014-12-02 10:57:49 +08:00 via iPhone 1
所有的递归都可转换成非递归，分为直接转换和间接转换，间接转换用栈模拟调用
|
 |
22
besto 2014-12-02 10:59:18 +08:00 1
楼上该说的都说了，补充几点：
1. 递归确实可以用循环替代，但是尾递归优雅（不是好看的意思）。 2. 尾递归程序不是那么容易写的，参考Lisp的程序，但尾递归的开销约等于循环。 3. 非尾递归会引起栈崩，100，1000，1w，10w，100w来测试qsort，总有能蹦的时候 4. Python类似的高级语言，考虑这种细节意义不是太大。 |
|
24
besto 2014-12-02 11:13:47 +08:00
@Loop680 刚学习某种语言，纠结这个，不如继续学习点python特性。
语言具有相同性，你这个问题，恰恰不是python独有的，C也有，Java也有(当然Lisp没有...) ==================================================================== 很多程序员最终的代码都是控制逻辑，而非算法逻辑。。。。 |
 |
25
Bluecoda 2014-12-02 11:20:17 +08:00
递归的好处是高级的抽象
上面解释了很多，递归因为种种原因，达不到循环的性能。唯一能够达到循环的性能的，就是优化过的尾递归。 |
 |
27
yunshansimon 2014-12-02 17:11:57 +08:00
递归用在处理链表上，你如果不是链表结构的话，就不要用递归了。
|
 |
28
alsotang 2014-12-02 17:29:13 +08:00
循环和尾递归都内存友好，递归的话，不好判断
|
 |
29
kingcos 2014-12-02 18:47:36 +08:00
。。。你可以看中国MOOC大学的数据结构，浙大的，就讲这个了！！
不过他举例的是C语言。。。我现在大概给你说说吧，不知道对不对呢~~~ 他举例：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印1到N的全部正整数。 然后用递归，当n = 100，000时，递归就直接崩溃了，而循环的话，就没问题，你可以试下~ 他的说明：递归虽然可以让我们更加清晰的写出代码，但是计算机不愿意做递归：因为递归对空间的占用过于庞大，超过了他能占用的空间，程序没有打出一个数字就崩溃了。 PS我也准备学python呢。。。刚学完C就学python会不会有些过快呢？ @Loop680 |
|
30
kingcos 2014-12-02 18:49:50 +08:00
忘了解释了= =
for循环：空间占用永远是个常量，不会随着n的增长而增长对内存的占用。 递归：当n越大时，S（n）呈线性增长，而这个函数所占空间是有限的，当把他的有限空间用完，程序就会崩溃。（S(n)是空间复杂度~：根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。） |
 |
31
327beckham 2014-12-02 19:19:50 +08:00
递归不太好，果断循环。
|
 |
32
1023400273 2014-12-03 09:05:56 +08:00
@xpfd 通俗易懂啊
|
Select Language