什么是尾递归？

Question

在开始学习lisp时,我遇到了尾递归这个术语.这究竟是什么意思？

Answer 1

考虑一个添加前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解释器开始实际执行计算总和之前完成.

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

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(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

在尾递归的情况下,每次递归调用的评估running_total都会更新.

注意:原始答案使用了Python中的示例.这些已经改为JavaScript,因为现代JavaScript解释器支持尾调用优化,但Python解释器不支持.

Answer 2

在传统的递归中,典型的模型是首先执行递归调用,然后获取递归调用的返回值并计算结果.以这种方式,在每次递归调用返回之前,您不会得到计算结果.

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

这样做的结果是,一旦准备好执行下一个递归步骤,就不再需要当前的堆栈帧了.这允许一些优化.事实上,使用适当编写的编译器,您应该永远不会有带尾递归调用的堆栈溢出窃听器.只需重复使用当前堆栈帧进行下一个递归步骤.我很确定Lisp会这样做.

Answer 3

重要的一点是尾递归基本上等于循环.这不仅仅是编译器优化的问题,而是表达性的基本事实.这有两种方式:你可以采取任何形式的循环

while(E) { S }; return Q

where E和Q是表达式,S是一系列语句,并将其转换为尾递归函数

f() = if E then { S; return f() } else { return Q }

当然,E,S,和Q必须定义来计算对一些变量的一些有趣的价值.例如,循环函数

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

相当于尾递归函数

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(这种带有参数较少的函数的尾递归函数的"包装"是一种常见的功能习惯.)

Answer 4

摘自" Lua编程 "一书,演示如何进行正确的尾递归(在Lua中,但也应该适用于Lisp)以及为什么它更好.

甲尾调用 [尾递归]是一种跳转的穿着作为一个呼叫.当一个函数将另一个函数作为最后一个动作调用时,会发生尾调用,因此它没有其他任何操作.例如,在以下代码中,调用g是尾调用:

function f (x)
  return g(x)
end

f通话结束后g,没有别的事可做.在这种情况下,当被调用函数结束时,程序不需要返回调用函数.因此,在尾调用之后,程序不需要保留有关堆栈中调用函数的任何信息....

因为正确的尾调用不使用堆栈空间,所以程序可以进行的"嵌套"尾调用的数量没有限制.例如,我们可以使用任何数字作为参数调用以下函数; 它永远不会溢出堆栈:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

......正如我之前所说,尾调用是一种转向.因此,Lua中正确尾部调用的一个非常有用的应用是编程状态机.这些应用程序可以通过函数表示每个状态; 改变状态是去(或调用)一个特定的功能.举个例子,让我们考虑一个简单的迷宫游戏.迷宫有几个房间,每个房间最多有四扇门:北,南,东和西.在每个步骤,用户输入移动方向.如果在该方向上有门,则用户前往相应的房间; 否则,程序会打印警告.目标是从最初的房间到最后的房间.

这个游戏是一个典型的状态机,当前的房间是状态.我们可以为每个房间实现一个功能的迷宫.我们使用尾调用从一个房间移动到另一个房间.一个有四个房间的小迷宫看起来像这样:

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

所以你看,当你做一个递归调用时:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

这不是尾递归,因为在进行递归调用之后,您仍然可以在该函数中执行操作(添加1).如果输入一个非常高的数字,可能会导致堆栈溢出.

Answer 5

使用常规递归,每个递归调用将另一个条目推送到调用堆栈.递归完成后,应用程序必须将每个条目一直弹回.

使用尾递归,根据语言,编译器可能能够将堆栈折叠为一个条目,因此您可以节省堆栈空间......大型递归查询实际上可能导致堆栈溢出.

基本上Tail递归可以优化为迭代.

Answer 6

行话文件有关于尾递归定义的说法:

尾递归/ n./

如果你还没有厌倦它,请参阅尾递归.

Answer 7

这是一个例子,而不是用文字解释.这是阶乘函数的Scheme版本:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

这是一个尾递归的factorial版本:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

您将在第一个版本中注意到对事实的递归调用被送入乘法表达式,因此在进行递归调用时必须将状态保存在堆栈中.在尾递归版本中,没有其他S表达式等待递归调用的值,并且由于没有其他工作要做,因此不必将状态保存在堆栈中.通常,Scheme尾递归函数使用常量堆栈空间.

Answer 8

尾递归是指递归调用在递归算法的最后一条逻辑指令中的最后一次.

通常在递归中你有一个基本情况,它停止递归调用并开始弹出调用堆栈.使用经典示例,尽管比Lisp更多C-ish,但是阶乘函数说明了尾递归.检查基本情况后发生递归调用.

factorial(x, fac=1) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

注意,对factorial的初始调用必须是阶乘(n,1),其中n是要计算阶乘的数字.

Answer 9

这意味着您可以简单地跳转到递归函数的顶部并继续执行,而不需要将指令指针推到堆栈上.这允许函数无限递归,而不会溢出堆栈.

我写了一篇关于这个主题的博客文章,其中有关于堆栈框架外观的图形示例.

Answer 10

这是一个比较两个函数的快速代码片段.第一种是用于查找给定数字的阶乘的传统递归.第二个使用尾递归.

理解起来非常简单直观.

判断递归函数是否为尾递归的简单方法是它是否在基本情况下返回具体值.意味着它不会返回1或true或类似的东西.它很可能会返回一个方法参数的变体.

另一种方法是判断递归调用是否没有任何添加,算术,修改等等......这意味着它只是一个纯粹的递归调用.

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

Answer 11

我理解的最好方法tail call recursion是递归的特殊情况,其中最后一次调用(或尾调用)是函数本身.

比较Python中提供的示例:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^递推

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^尾随回归

正如您在一般递归版本中看到的那样,代码块中的最终调用是x + recsum(x - 1).因此在调用该recsum方法之后,还有另一个操作x + ...

但是,在尾递归版本中,代码块中的最终调用(或尾调用)tailrecsum(x - 1, running_total + x)意味着对方法本身进行最后一次调用,之后不进行任何操作.

这一点是重要的,因为如在此看到的不使存储器增长,因为当底层VM看到一个函数调用本身在尾部位置(最后一个表达式的函数进行计算的),它消除了当前堆栈帧,尾递归这被称为尾调用优化(TCO).

编辑

NB.请记住,上面的示例是用Python编写的,其运行时不支持TCO.这只是一个例子来解释这一点.Scheme,Haskell等语言支持TCO

Answer 12

在Java中,这是Fibonacci函数的可能尾递归实现:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

将此与标准递归实现进行对比:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

Answer 13

我不是Lisp程序员,但我认为这会有所帮助.

基本上它是一种编程风格,使得递归调用是你做的最后一件事.

Answer 14

这是一个Common Lisp示例,它使用尾递归来执行阶乘.由于无堆栈特性,人们可以执行疯狂的大因子计算......

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

然后为了好玩,你可以试试 (format nil "~R" (! 25))

Answer 15

简而言之,尾递归将递归调用作为函数中的最后一个语句,这样它就不必等待递归调用.

所以这是一个尾递归,即N(x - 1,p*x)是函数中的最后一个语句,编译器很聪明地知道它可以优化为for循环(factorial).第二个参数p带有中间产品值.

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

这是编写上述阶乘函数的非尾递归方式(尽管一些C++编译器仍然可以优化它).

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

但这不是:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

我写了一篇名为" 理解尾递归 - Visual Studio C++ - 汇编视图 " 的长篇文章

Answer 16

这是tailrecsum前面提到的函数的Perl 5版本.

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}

Answer 17

这是关于尾部递归的计算机程序的结构和解释的摘录.

在对比迭代和递归时,我们必须注意不要将递归过程的概念与递归过程的概念混淆.当我们将过程描述为递归时,我们指的是过程定义(直接或间接)引用过程本身的语法事实.但是,当我们将流程描述为遵循线性递归的模式时,我们会谈论流程是如何演变的,而不是关于如何编写流程的语法.我们将一个递归过程称为事实 - 因为生成迭代过程,这似乎令人不安.但是,这个过程确实是迭代的:它的状态完全被它的三个状态变量捕获,并且解释器需要只跟踪三个变量才能执行该过程.

过程和过程之间的区别可能令人困惑的一个原因是,大多数常见语言(包括Ada,Pascal和C)的实现都是以这样一种方式设计的,即任何递归过程的解释都会消耗大量的内存.过程调用的数量,即使所描述的过程原则上是迭代的.因此,这些语言只能通过使用特殊用途的"循环结构"来描述迭代过程,例如do,repeat,until,for和while.Scheme的实现不会分享这个缺陷.它将在常量空间中执行迭代过程,即使迭代过程由递归过程描述.具有此属性的实现称为tail-recursive.使用尾递归实现,可以使用普通过程调用机制表示迭代,因此特殊迭代构造仅作为语法糖使用.

Answer 18

与普通递归相比，尾递归非常快。它很快是因为祖先调用的输出不会写入堆栈以保持跟踪。但在正常递归中，所有祖先调用写在堆栈中的输出以保持跟踪。

Answer 19

尾递归就是你现在的生活.你不断地循环使用相同的堆栈帧,因为没有理由或方法可以返回到"之前的"帧.过去已经完成,所以它可以被丢弃.你得到一个框架,永远移动到未来,直到你的过程不可避免地死亡.

_{当你考虑某些进程可能使用额外的帧但是如果堆栈没有无限增长时仍然被认为是尾递归的话,这种类比就会破坏.}

Answer 20

尾递归是一种递归函数,其中函数在函数的末尾("尾部")调用自身,其中在递归调用的返回之后不进行任何计算.许多编译器优化以将递归调用更改为尾递归或迭代调用.

考虑计算数字因子的问题.

一个简单的方法是:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

假设你调用factorial(4).递归树将是:

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1    

上述情况下的最大递归深度为O(n).

但是,请考虑以下示例:

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

factTail(4)的递归树将是:

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

在这里,最大递归深度是O(n),但没有一个调用将任何额外的变量添加到堆栈.因此编译器可以取消堆栈.

Answer 21

递归函数是一个自行调用的函数

它允许程序员使用最少的代码编写高效的程序。

缺点是，如果编写不正确，它们可能会导致无限循环和其他意外结果。

我将解释简单递归函数和尾递归函数

为了编写一个简单的递归函数

1. 要考虑的第一点是何时应该决定退出循环，即if循环
2. 第二个是如果我们是我们自己的职能，该怎么办

从给定的示例：

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

从上面的例子

if(n <=1)
     return 1;

是何时退出循环的决定因素

else 
     return n * fact(n-1);

是否要进行实际处理

为了便于理解，让我一个接一个地完成任务。

让我们看看如果我跑步会在内部发生什么 fact(4)

1. 代入n = 4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If循环失败，因此进入else循环，因此返回4 * fact(3)

2. 在堆栈内存中，我们有 4 * fact(3)

   代入n = 3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If循环失败，因此进入else循环

所以它返回 3 * fact(2)

记住我们称呼为``4 * fact（3）``

输出为 fact(3) = 3 * fact(2)

到目前为止，堆栈已经 4 * fact(3) = 4 * 3 * fact(2)

3. 在堆栈内存中，我们有 4 * 3 * fact(2)

   代入n = 2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If循环失败，因此进入else循环

所以它返回 2 * fact(1)

记得我们打过电话 4 * 3 * fact(2)

输出为 fact(2) = 2 * fact(1)

到目前为止，堆栈已经 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

3. 在堆栈内存中，我们有 4 * 3 * 2 * fact(1)

   代入n = 1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If 循环为真

所以它返回 1

记得我们打过电话 4 * 3 * 2 * fact(1)

输出为 fact(1) = 1

到目前为止，堆栈已经 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

最后，fact（4）的结果= 4 * 3 * 2 * 1 = 24

在尾递归会

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

1. 代入n = 4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If循环失败，因此进入else循环，因此返回fact(3, 4)

2. 在堆栈内存中，我们有 fact(3, 4)

   代入n = 3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If循环失败，因此进入else循环

所以它返回 fact(2, 12)

2. 在堆栈内存中，我们有 fact(2, 12)

   代入n = 2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

If循环失败，因此进入else循环

所以它返回 fact(1, 24)

3. 在堆栈内存中，我们有 fact(1, 24)

   代入n = 1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If 循环为真

所以它返回 running_total

输出为 running_total = 24

最后，fact（4,1）= 24的结果

Answer 22

如果每个递归情况仅包含对函数本身的调用（可能具有不同的参数），则函数是尾递归的。或者，尾递归是没有待处理工作的递归。请注意，这是一个独立于编程语言的概念。

考虑定义为的函数：

g(a, b, n) = a * b^n

可能的尾递归公式是：

g(a, b, n) | n is zero = a
           | n is odd  = g(a*b, b,   n-1)
           | otherwise = g(a,   b*b, n/2)

如果您检查其中g(...)涉及递归情况的每个 RHS，您会发现 RHS 的整个主体都是对 的调用g(...)，而且仅此而已。这个定义是尾递归的。

为了进行比较，非尾递归公式可能是：

g'(a, b, n) = a * f(b, n)
f(b, n) | n is zero = 1
        | n is odd  = f(b, n-1) * b
        | otherwise = f(b, n/2) ^ 2

中的每个递归情况f(...)都有一些待处理的工作需要在递归调用之后发生。

请注意，当我们从g'到 时g，我们充分利用了乘法的结合性（和交换性）。这不是偶然，大多数需要将递归转换为尾递归的情况都会利用这样的属性：如果我们想急切地做一些工作而不是让它悬而未决，我们必须使用诸如关联性之类的东西来证明答案是一样的。

尾递归调用可以通过向后跳转来实现，而不是使用堆栈进行普通递归调用。请注意，检测尾部调用或发出向后跳转通常很简单。然而，通常很难重新排列参数以使向后跳转成为可能。由于此优化不是免费的，因此语言实现可以选择不实现此优化，或者需要通过使用“tailcall”指令标记递归调用和/或选择更高的优化设置来选择加入。

然而，某些语言（例如Scheme）确实需要所有实现来优化尾部递归函数，甚至可能是尾部位置的所有调用。

在大多数命令式语言中，向后跳转通常被抽象为 (while) 循环，而尾递归在优化为向后跳转时，与循环同构。

Answer 23

• Tail Recursive Function 是一种递归函数，其中递归调用是函数中最后执行的事情。

常规递归函数，我们有堆栈，每次我们在该递归函数中调用递归函数时，都会在调用堆栈中添加另一层。在正常的递归空间中：O(n)尾递归使得空间复杂度为

O(N)=>O(1)

• 尾部调用优化意味着可以从另一个函数调用一个函数，而无需增加调用堆栈。

• 我们应该在递归解决方案中编写尾递归。但某些语言实际上并不支持其引擎中向下编译语言的尾递归。从 ecma6 开始，规范中就出现了尾递归。但是编译js的引擎都没有实现尾递归。在js中你不会实现O(1)，因为编译器本身不知道如何实现这个尾递归。截至 2020 年 1 月 1 日，Safari 是唯一支持尾部调用优化的浏览器。

• Haskell 和 Java 都有尾递归优化

正则递归阶乘

function Factorial(x) {
  //Base case x<=1
  if (x <= 1) {
    return 1;
  } else {
    // x is waiting for the return value of Factorial(x-1)
    // the last thing we do is NOT applying the recursive call
    // after recursive call we still have to multiply.
    return x * Factorial(x - 1);
  }
}

我们的调用堆栈中有 4 个调用。

Factorial(4); // waiting in the memory for Factorial(3)
4 * Factorial(3); //  waiting in the memory for Factorial(2)
4 * (3 * Factorial(2)); //  waiting in the memory for Factorial(1)
4 * (3 * (2 * Factorial(1)));
4 * (3 * (2 * 1));

• 我们进行 4 次 Factorial() 调用，空间复杂度为 O(n)
• 这可能会导致 Stackoverflow

尾递归阶乘

function tailFactorial(x, totalSoFar = 1) {
  //Base Case: x===0. In recursion there must be base case. Otherwise they will never stop
  if (x === 0) {
    return totalSoFar;
  } else {
    // there is nothing waiting for tailFactorial to complete. we are returning another instance of tailFactorial()
    // we are not doing any additional computaion with what we get back from this recursive call
    return tailFactorial(x - 1, totalSoFar * x);
  }
}

• 进行递归调用后，我们不需要记住任何事情

Answer 24

递归意味着一个调用自身的函数。例如：

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

尾递归表示结束函数的递归：

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

看，未结束的函数（程序，在 Scheme 行话中）所做的最后一件事就是调用自身。另一个（更有用）的例子是：

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

在辅助程序中，如果左边不是 nil，它所做的最后一件事就是调用自己（在 cons 和 cdr 之后）。这基本上就是您映射列表的方式。

尾递归有一个很大的优势，解释器（或编译器，取决于语言和供应商）可以对其进行优化，并将其转换为相当于 while 循环的东西。事实上，在 Scheme 传统中，大多数“for”和“while”循环都是以尾递归方式完成的（据我所知，没有 for 和 while）。

Answer 25

为了理解尾调用递归和非尾调用递归之间的一些核心差异,我们可以探索这些技术的.NET实现.

下面是一篇文章,其中包含C#,F#和C++\CLI中的一些示例:C#,F#和C++\CLI 中的Tail Recursion中的冒险.

C#不优化尾调用递归,而F#则优化.

原理的差异涉及循环与Lambda演算.C#的设计考虑了循环,而F#是根据Lambda演算的原理构建的.有关Lambda演算原理的非常好(和免费)的书,请参阅Abelson,Sussman和Sussman的计算机程序的结构和解释.

关于F#中的尾部调用,有关非常好的介绍性文章,请参阅F#中的尾部调用详细介绍.最后,这篇文章涵盖了非尾递归和尾调用递归(在F#中)之间的区别:F sharp中的尾递归与非尾递归.

如果您想了解C#和F#之间尾调用递归的一些设计差异,请参阅在C#和F#中生成尾调用操作码.

如果您非常关心要知道哪些条件阻止C#编译器执行尾调用优化,请参阅本文:JIT CLR尾调用条件.

Answer 26

递归有两种基本类型：头递归和尾递归。

在head recursion中，函数进行递归调用，然后执行更多计算，例如可能使用递归调用的结果。

在尾递归函数中，所有计算首先发生，递归调用是最后发生的事情。

摘自这篇超级棒的帖子。请考虑阅读它。

Answer 27

一尾递归函数是一个递归函数，其中最后一个动作恢复之前它使递归函数调用。即，立即返回递归函数调用的返回值。例如，您的代码如下所示：

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

实现尾部调用优化或尾部调用消除的编译器和解释器可以优化递归代码以防止堆栈溢出。如果您的编译器或解释器未实现尾部调用优化（例如CPython解释器），则以这种方式编写代码没有任何其他好处。

例如，这是Python中的标准递归阶乘函数：

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

这是阶乘函数的尾调用递归版本：

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

（请注意，即使这是Python代码，CPython解释器也不会进行尾调用优化，因此按这种方式排列代码不会给运行时带来任何好处。）

如阶乘示例所示，您可能必须使代码更加不可读才能利用尾部调用优化。（例如，基本情况现在有点不直观，并且该accumulator参数有效地用作一种全局变量。）

但是尾部调用优化的好处是它可以防止堆栈溢出错误。（我会注意到，通过使用迭代算法而不是递归算法，您可以获得相同的好处。）

当调用堆栈中放入过多帧对象时，会导致堆栈溢出。调用函数时，将框架对象压入调用堆栈，并在函数返回时从调用堆栈弹出。框架对象包含信息，例如局部变量和函数返回时返回的代码行。

如果您的递归函数进行过多的递归调用而没有返回，则调用堆栈可能超出其框架对象限制。（该数目因平台而异；在Python中，默认为1000个框架对象。）这会导致堆栈溢出错误。（嘿，这就是这个网站的名称！）

但是，如果递归函数做的最后一件事是进行递归调用并返回其返回值，则没有理由需要将当前帧对象保留在调用堆栈中。毕竟，如果在递归函数调用之后没有任何代码，则没有理由继续使用当前帧对象的局部变量。因此，我们可以立即摆脱当前框架对象，而不必将其保留在调用堆栈中。这样的最终结果是您的调用堆栈不会增加大小，因此不会导致堆栈溢出。

编译器或解释器必须具有尾调用优化功能，才能识别何时可以应用尾调用优化。即使这样，您也可能已经在递归函数中重新安排了代码以利用尾部调用优化，如果这种潜在的可读性下降值得优化，则取决于您。