关于递归和 While

[JCZ2MkKb5S8ZX9pq]

• 说实话直到最近，有时候写递归脑子还是会卡住。
• 然后昨天顺手就把一个可以用递归表达的函数，直接写成了 while，好像也运行顺利。
• 我就在想，是否 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 必须递归。
• 或者递归有啥特别的优势嘛？

[ipwx]

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

[ipwx]

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

http://ideone.com/3zaTEJ

[idealhs]

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

[newtype0092]

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

[reself]

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

[JCZ2MkKb5S8ZX9pq]

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

[reself]

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

[taogen]

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

[Vegetable]

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

[reself]

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

[wysnylc]

建议使用迭代代替所有递归,递归会导致栈溢出和逻辑不易读

[ipwx]

@JCZ2MkKb5S8ZX9pq 例子很容易找，而且是标准算法。

用栈辅助：图搜索的深度优先遍历。
用队列辅助：图搜索的广度优先遍历。

[HolmLoh]

@idealhs
这是理想情况，正常情况是 代码要能运行，只是恰巧给人看的

[Amit]

我感觉递归更符合直觉，更容易理解。把递归改成循环，需要自己维护栈

[jmc891205]

主题叫“关于递归和迭代”更好一点
因为实现迭代的方式有很多种 用 while 只是其中一种

[msg7086]

迭代是一种递归的做法。当然有些递归不是那么容易写成循环就是了。
不过说白了，循环和递归都是让当前运行指令跳回头部，所以本质上都是一样的，无非是要保存和恢复调用者的环境而已。循环就是一种（可能经过简化的）递归。

[luckyuro]

你的 1 改一下就是尾递归了，有很多语言对尾递归有优化。
个人觉得递归和循环是思考 /看待问题角度的事情，个人认为有些问题拿递归来思考比较容易。
还有就是，有些语言变量的值不能修改，这种情况下感觉循环会有些变扭，就会用递归

[luckyuro]

你永远可以用一个栈把递归转换成循环。关于尾递归的介绍可以看看 sicp 一开始的一章