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))
1
ipwx 2019-09-27 15:10:08 +08:00 3
1、只有尾递归才能比较容易地被转化为循环。并且,一个合格的程序员在这种情况下优先使用循环,除非你在用一些正统的函数式编程语言。
2、非尾递归不太容易转换成循环。不过在写算法的时候,很多时候为了效率,也会想办法转化成循环。不过这需要借助额外的数据结构,比如队列或者栈。 3、在 2 的情况下,递归远比非递归容易写、容易读。 |
2
ipwx 2019-09-27 15:15:07 +08:00
|
3
idealhs 2019-09-27 15:26:04 +08:00
代码是写给人看的,只是恰巧能够运行
|
4
newtype0092 2019-09-27 15:28:27 +08:00
递归转化成循环是一种普遍的优化方式吧
|
5
reself 2019-09-27 15:34:34 +08:00
递归和递推公式容易转换。递归更"数学",循环更偏向"程序"
|
6
JCZ2MkKb5S8ZX9pq OP @ipwx 请问有没有情况 2 的合适的例子?
|
7
reself 2019-09-27 15:43:56 +08:00
递归偏向于"是什么",就像数学归纳法中的初始条件和推理。你给的递归的例子里,代码本身就描述了阶乘的定义:f(n)=n*f(n-1)
循环偏向于"怎么做",描述的实现方式而不是定义 |
8
taogen 2019-09-27 15:49:06 +08:00 via Android
递归使代码更简洁,但会消耗额外的内存。数据集合 size 比较大时,不适合用递归,容易发生 Stack overflow。
|
9
Vegetable 2019-09-27 15:52:07 +08:00
函数本身就是调用栈,所以,没有必须递归的算法。
递归的优势是让算法更好理解。 |
10
reself 2019-09-27 15:52:11 +08:00
@JCZ2MkKb5S8ZX9pq 因为函数调用其实就是局部环境的入栈和出栈,因此理论上所有递归都能转成循环,只是有的需要用栈来辅助(尾递归是特殊情况)。需要用栈辅助的情况下,其实不如递归易读。不过操作系统一般会限制函数调用栈的大小,所以不能保证调用深度的情况下,转成循环可以规避掉这个限制,也是有意义的。
像树和图的场景,用递归就更简洁。 |
11
wysnylc 2019-09-27 15:58:00 +08:00
建议使用迭代代替所有递归,递归会导致栈溢出和逻辑不易读
|
12
ipwx 2019-09-27 16:33:59 +08:00
|
14
Amit 2019-09-27 17:20:51 +08:00
我感觉递归更符合直觉,更容易理解。把递归改成循环,需要自己维护栈
|
15
jmc891205 2019-09-27 17:41:22 +08:00
主题叫“关于递归和迭代”更好一点
因为实现迭代的方式有很多种 用 while 只是其中一种 |
16
msg7086 2019-09-28 04:29:06 +08:00
迭代是一种递归的做法。当然有些递归不是那么容易写成循环就是了。
不过说白了,循环和递归都是让当前运行指令跳回头部,所以本质上都是一样的,无非是要保存和恢复调用者的环境而已。循环就是一种(可能经过简化的)递归。 |
17
luckyuro 2019-09-28 11:12:36 +08:00 via iPhone
你的 1 改一下就是尾递归了,有很多语言对尾递归有优化。
个人觉得递归和循环是思考 /看待问题角度的事情,个人认为有些问题拿递归来思考比较容易。 还有就是,有些语言变量的值不能修改,这种情况下感觉循环会有些变扭,就会用递归 |
18
luckyuro 2019-09-28 11:13:44 +08:00 via iPhone
你永远可以用一个栈把递归转换成循环。关于尾递归的介绍可以看看 sicp 一开始的一章
|