详解什么是尾递归（通俗易懂，示例讲解）

朱雀 2020-10-24 16:38 755阅读 0赞

在**传统的递归中**，典型的模型是首先执行递归调用，然后获取递归调用的返回值并计算结果。以这种方式，在每次递归调用返回之前，您不会得到计算结果。传统地递归过程就是函数调用，涉及返回地址、函数参数、寄存器值等压栈（在x86-64上通常用寄存器保存函数参数），这样做的缺点有二：

*  效率低，占内存
 *  如果递归链过长，可能会**statck overflow**

若函数在尾位置调用自身（或是一个尾调用本身的其他函数等等），则称这种情况为**尾递归**。尾递归也是递归的一种特殊情形。尾递归是一种特殊的尾调用，即在尾部直接调用自身的递归函数。对尾递归的优化也是关注尾调用的主要原因。尾调用不一定是递归调用，但是尾递归特别有用，也比较容易实现。

## **尾递归的原理：** ##

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

## 特点： ##

尾递归在普通尾调用的基础上，多出了2个特征：

*  在尾部调用的是函数自身 （Self-called）；
 *  可通过优化，使得计算仅占用常量栈空间 (Stack Space)。

## 说明： ##

传统模式的编译器对于尾调用的处理方式就像处理其他普通函数调用一样，总会在调用时创建一个新的栈帧（stack frame）并将其推入调用栈顶部，用于表示该次函数调用。

当一个函数调用发生时，电脑必须 “记住” 调用函数的位置 —— 返回位置，才可以在调用结束时带着返回值回到该位置，返回位置一般存在调用栈上。在尾调用这种特殊情形中，电脑理论上可以不需要记住尾调用的位置而从被调用的函数直接带着返回值返回调用函数的返回位置（相当于直接连续返回两次）。尾调用消除即是在不改变当前调用栈（也不添加新的返回位置）的情况下跳到新函数的一种优化（完全不改变调用栈是不可能的，还是需要校正调用栈上形式参数与局部变量的信息。）

由于当前函数帧上包含局部变量等等大部分的东西都不需要了，当前的函数帧经过适当的更动以后可以直接当作被尾调用的函数的帧使用，然后程序即可以跳到被尾调用的函数。产生这种函数帧更动代码与 “jump”（而不是一般常规函数调用的代码）的过程称作尾调用消除(Tail Call Elimination)或尾调用优化(Tail Call Optimization, TCO)。尾调用优化让位于尾位置的函数调用跟 goto 语句性能一样高，也因此使得高效的结构编程成为现实。

然而，对于 C++ 等语言来说，在函数最后 return g(x); 并不一定是尾递归——在返回之前很可能涉及到对象的析构函数，使得 g(x) 不是最后执行的那个。这可以通过返回值优化来解决。

在**尾递归中**，首先执行计算，然后执行递归调用，将当前步骤的结果传递给下一个递归步骤。这导致最后一个语句采用的形式`(return (recursive-function params))`。**基本上，任何给定递归步骤的返回值与下一个递归调用的返回值相同**。

我们考虑一个最基本的关于N的求和函数，（例如`sum(5) = 1 + 2 + 3 + 4 + 5 = 15`）。

这是一个使用JavaScript实现的递归函数：

function recsum(x) {
        if (x===1) {
            return x;
        } else {
            return x + recsum(x-1);
        }
    }

如果你调用`recsum(5)`，JavaScript解释器将会按照下面的次序来计算：

recsum(5)
    5 + recsum(4)
    5 + (4 + recsum(3))
    5 + (4 + (3 + recsum(2)))
    5 + (4 + (3 + (2 + recsum(1))))
    5 + (4 + (3 + (2 + 1)))
    15

注意在JavaScript解释器计算recsum（5）之前，每个递归调用必须全部完成。

这是同一函数的尾递归版本：

function tailrecsum(x, running_total=0) {
        if (x===0) {
            return running_total;
        } else {
            return tailrecsum(x-1, running_total+x);
        }
    }

下面是当你调用tailrecsum(5)的时候实际的事件调用顺序：

tailrecsum(5, 0)
    tailrecsum(4, 5)
    tailrecsum(3, 9)
    tailrecsum(2, 12)
    tailrecsum(1, 14)
    tailrecsum(0, 15)
    15

在尾递归的情况下，每次递归调用的时候，`running_total`都会更新。