关于递归和 While

def fact(n):
    if n == 1:
        print('fact: 1 = 1')
        return 1
    print(f'fact: {n} = {n}*fact({n-1})')
    return n * fact(n - 1)


print(fact(10))

在递归时，运行顺序是从外到内从，有点反过来的。

def fact2(n):
    r = a = 1
    while True:  # 退出条件写在下面感觉更易读一点
        r *= a
        print(f'a={a} | r={r}')
        a += 1
        if a > n:
            return r


print(fact2(10))

用 while 写起来和理解起来都比较顺一点。

我是美术半路出家的，现在就有点疑惑。
想请教下各位高手，哪些情况下不适用 while 必须递归。
或者递归有啥特别的优势嘛？

while

fact

return

18 条回复 • 2019-09-28 11:13:44 +08:00

ipwx

2019-09-27 15:10:08 +08:00

1、只有尾递归才能比较容易地被转化为循环。并且，一个合格的程序员在这种情况下优先使用循环，除非你在用一些正统的函数式编程语言。
2、非尾递归不太容易转换成循环。不过在写算法的时候，很多时候为了效率，也会想办法转化成循环。不过这需要借助额外的数据结构，比如队列或者栈。
3、在 2 的情况下，递归远比非递归容易写、容易读。

ipwx

2019-09-27 15:15:07 +08:00

顺便楼主你这情况就是尾递归。而且为啥要用 while，用 for 不就行了。

http://ideone.com/3zaTEJ

idealhs

2019-09-27 15:26:04 +08:00

代码是写给人看的，只是恰巧能够运行

newtype0092

2019-09-27 15:28:27 +08:00

递归转化成循环是一种普遍的优化方式吧

reself

2019-09-27 15:34:34 +08:00

递归和递推公式容易转换。递归更"数学"，循环更偏向"程序"

JCZ2MkKb5S8ZX9pq

2019-09-27 15:37:01 +08:00

@ipwx 请问有没有情况 2 的合适的例子？

reself

2019-09-27 15:43:56 +08:00

递归偏向于"是什么"，就像数学归纳法中的初始条件和推理。你给的递归的例子里，代码本身就描述了阶乘的定义：f(n)=n*f(n-1)
循环偏向于"怎么做"，描述的实现方式而不是定义

taogen

2019-09-27 15:49:06 +08:00 via Android

递归使代码更简洁，但会消耗额外的内存。数据集合 size 比较大时，不适合用递归，容易发生 Stack overflow。

Vegetable

2019-09-27 15:52:07 +08:00

函数本身就是调用栈，所以，没有必须递归的算法。
递归的优势是让算法更好理解。

reself

2019-09-27 15:52:11 +08:00

@JCZ2MkKb5S8ZX9pq 因为函数调用其实就是局部环境的入栈和出栈，因此理论上所有递归都能转成循环，只是有的需要用栈来辅助（尾递归是特殊情况）。需要用栈辅助的情况下，其实不如递归易读。不过操作系统一般会限制函数调用栈的大小，所以不能保证调用深度的情况下，转成循环可以规避掉这个限制，也是有意义的。
像树和图的场景，用递归就更简洁。