理解尾递归

发表于 | 分类于

知乎上关于尾递归的讨论

尾递归就是操作的最后一步是调用自身的递归。

觉得上面的论述十分清晰，以廖雪峰的官方网站-递归函数里面的例子为例：
求一个数字的阶乘

1
2
3
4
5
def fact(n):
	if n == 1:
		return 1
	# 最后一步调用不是调用自身，而是一个数字和自身调用结果乘积的表达式
	return n * fact(n-1)

优化为尾递归

1
2
3
4
5
6
7
8
def fact(n):
	return fact_inter(n,1)
def fact_inter(n, m):
	if n == 1
		return m
	# 最后一步调用是调用自身
	return fact_inter(n - 1, m * n)

尾递归在一些编译器中会做优化，防止栈内存爆掉。因为尾递归调用之后不依赖上次调用的环境（资源），如上述代码最后一步，每次调用都会把计算的值存储在变量 m 中，不会等到最后一层调用完毕之后再释放资源。