当前位置：首页 > article >正文

C++杂记——尾递归

article 2025/3/4 17:17:50

文章目录

- - 递归
  - 尾递归
  - 递归的消除

递归

传统地递归过程就是函数调用，涉及返回地址、函数参数、寄存器值等压栈（在x86-64上通常用寄存器保存函数参数），这样做的缺点有二：

效率低，占内存
如果递归链过长，可能会栈溢出

尾递归

尾递归是递归的一种特殊情形，是一种特殊的尾调用，即在尾部直接调用自身的递归函数。核心思想是边调用便产生结果。尾递归涉及在最后一行的递归调用，尾递归可以通过将递归调用变成goto语句并在其前面加上对函数每个参数的赋值语句而手工消除。它模拟了递归调用，因为没有什么需要存储；在递归调用结束后，实际上没有必要知道存储的值。因此，我们就可以带着在一次递归调用中已经用过的那些值goto到函数顶部。

这是尾递归：

int function f(x) {
   if (x === 1) return 1;
   return f(x-1);
}

int function f(x) {
   if (x === 1) return 1;
   return 1 + f(x-1);
}

后者不是尾递归，是因为该函数的最后一步操作是用1加上f(x-1)的返回结果，因此，最后一步操作不是调用自身。注意，后面这段代码的递归也发生在函数末尾，但它不是尾递归。**尾递归的判断标准是函数运行最后一步是否调用自身，而不是是否在函数的最后一行调用自身。**因此阶乘n!的递归求法，尽管看起来递归发生在函数末尾，其实也不是尾递归：

int function factorial(n) {
   if (n === 1) return 1;
   return n * factorial(n-1); // 最后一步不是调用自身，因此不是尾递归
}

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

特点：在尾部调用的是函数自身，可通过优化使得计算仅占用常量栈空间