数据结构和算法--递归和尾递归

递归和尾递归

递归

1、定义：

• 子问题必须和原始问题相同，且更为简单；
• 不能无限制的调用本身，必须有个出口，化简为非递归状况处理。

2、场景：

# 递归实现
def fact(n: int):
    """
    求n!
    :param n:
    :return:
    """
    if n < 0:
        return 0
    elif n == 0 or n == 1:
        return  1
    else:
        return n * fact(n - 1)

3、原理分析：

在每次函数调用计算n倍的(n－1)!的值，让n=n－1并持续这个过程直到n=1为止。这种定义不是尾递归的，
因为每次函数调用的返回值都依赖于用n乘以下一次函数调用的返回值，因此每次调用产生的栈帧将不得不保存在栈上直到下一个子调用的返回值确定。

尾递归

1、定义：

• 如何一个函数中所有递归形式调用都出现在函数末尾， 称这个递归函数是尾递归。

• 递归调用是整个函数体中最后一个执行语句且它返回值不属于表达式一部分；

• 回归过程中不用做任何操作（大多数代码编译器会利用这种特性自动生成优化代码）;

2、尾递归原理：

当编译器检测到一个函数是尾递归时，他就覆盖当前活动记录， 而不是在栈中创建一个新的，
因为递归调用是当前活跃期内最后一条执行的语句，于是当这个调用返回时，栈中并没有其他事情可做，因此没有保存栈帧
的必要。通过覆盖当前栈帧而不是在其之上重新添加一个，这样使用栈空间大大缩减，实际运行效率变高。

eg:
尾递归阶乘实现：

def fact_tail(n: int, res: int):
    """
    尾递归方式，求n！
    :param n:
    :param res:
    :return:
    """
    if n < 0:
        return 0
    elif n == 0:
        return 1
    elif n == 1:
        return res
    else:
        return fact_tail(n - 1, n * res)

尾递归解析：

函数比代码1多个参数res，除此之外并没有太大区别。res（初始化为1）维护递归层次的深度。这就让我们避免了每次还需要将返回值再乘以n。
然而，在每次递归调用中，令res=n*res并且n=n－1。继续递归调用，直到n=1，这满足结束条件，此时直接返回res即可。

总结：
递归和尾递归的不同：
示例中的函数是尾递归的，因为对facttail的单次递归调用是函数返回前最后执行的一条语句。
换句话说，在递归调用之后还可以有其他的语句执行，只是它们只能在递归调用没有执行时才可以执行。

尾递归是极其重要的，不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。
比如sum(n) = f(n) = f(n-1) + value(n) ;
会保存n个函数调用堆栈，而使用尾递归f(n, sum) = f(n-1, sum+value(n)); 这样则只保留后一个函数堆栈即可，之前的可优化删去。

优化尾递归的装饰器

有一个针对尾递归优化的decorator