认识尾递归

尾递归是指在一个函数的最后一个操作是调用自身的递归。这意味着在递归调用后没有其他操作需要执行，直接返回递归调用的结果。尾递归通常是指递归调用出现在函数的最后一行，或者是出现在一个单独的分支中，确保在递归调用之后没有其他代码需要执行。尾递归的特点是在递归调用之后不需要保存当前函数的状态，因为递归调用的结果会直接返回。这种特性使得编译器可以对尾递归进行优化，将其转化为循环形式，从而避免在调用栈中不断添加新的帧，节约了内存空间。

拿计算阶乘举例：

普通的递归

factorial(n):

if n == 0:

return 1

else:

return n * factorial(n-1)

尾递归形式

factorial_tail(n, acc=1):

if n == 0:

return acc

else:

return factorial_tail(n-1, acc*n)//返回结果直接是递归函数本身

// 如果上述为return factorial_tail(n-1, acc）+1或者 return factorial_tail(n-1, acc*n)*n

这类形式都不是尾递归，因为返回结果并不是单一递归函数本身，有额外项，（如+1，*n)它的存在会导致每次函数调用栈不会清除，一直累积，和递归一样。

尾递归的优点

直接上实例看看尾递归的效率（拿计算斐波那契数列举例子）

很容易写出递归；

//count用于计算调用fac函数时，计算机会计算fac（3）的次数

实际结果如下：

可以看到，计算fac（40）时，fac(3)在电脑中居然会计算如此多次！！！！效率很低！

稍微修改下使用尾递归的方法

实际结果如下：

经过同样的测试，fac（3）只计算了1次；由此可见尾递归的效率是多么高！

为什么尾递归效率高呢？

尾递归和普通递归都是通过函数调用自身来实现的，但它们在内存利用方面有所不同。

在普通递归中，每次递归调用都会将当前函数的局部变量、参数和返回地址压入调用栈中，这些信息会在递归返回时被弹出。因此，如果递归层级很深，调用栈可能会变得非常大，占用大量内存空间甚至导致栈溢出。

而在尾递归中，递归调用是当前函数的最后一个操作，也就是说在调用之后没有其他操作需要执行。这使得编译器可以对尾递归进行优化，将其转化为循环形式，在原来的栈区不断覆盖再覆盖，而不是在调用栈中不断添加新的帧。这种优化称为"尾调用优化"。由于尾调用优化消除了不必要的调用栈帧，因此尾递归通常比普通递归节约内存空间。

尾递归在调用栈上不会累积大量的帧，而且可以被优化成循环，从而减少了内存的占用。