什么是尾巴递归？

在开始学习lisp的时候，我遇到了尾递归这个词。它到底是什么意思？

573716 次浏览
小开

我不是Lisp程序员，但我认为这个会有所帮助。

基本上，这是一种编程风格，递归调用是你做的最后一件事。

小开

使用常规递归，每个递归调用都会将另一个条目推送到调用堆栈上。递归完成后，应用程序必须一直向下弹出每个条目。

使用尾递归，根据语言的不同，编译器可能能够将堆栈折叠成一个条目，因此可以节省堆栈空间……大型递归查询实际上会导致堆栈溢出。

基本上，尾递归能够优化为迭代。

小开

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

通常在递归中，你有一个基本情况，它是停止递归调用并开始弹出调用堆栈的东西。使用一个经典的例子，尽管比Lisp更像C语言，但阶乘函数说明了尾递归。递归调用发生之后检查基本情况。

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

对阶乘的初始调用将是factorial(n)，其中fac=1（默认值）和n是要计算阶乘的数字。

小开

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

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

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

小开

这里有一个例子，而不是用单词来解释它。这是阶乘函数的模式版本：

(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表达式等待递归调用的值，并且由于没有进一步的工作要做，状态不必保存在堆栈上。通常，方案尾递归函数使用常量堆栈空间。

小开

行话文件对尾递归的定义有这样的说法：

尾递归 /n./

如果您还没有厌倦它，请参阅尾递归。

小开

这本书的摘录Lua编程展示了如何进行适当的尾部递归（在Lua中，但也应该适用于Lisp）以及为什么它更好。

A尾部呼叫[尾巴递归]是一种goto修饰一个尾部呼叫发生在函数调用另一个作为它的最后一个行动，所以没有别的事可做。例如，在以下代码中，对g的调用是一个尾部调用：

function f (x)return g(x)end

在f调用g之后，它没有别的了在这种情况下，程序不需要返回到调用函数调用时的函数结束。因此，在尾部呼叫之后，该程序不需要保留任何关于调用函数的信息在堆栈中…

因为正确的尾部调用使用no堆栈空间，没有限制a的“嵌套”尾部调用数程序可以使。例如，我们可以使用任何函数调用以下函数数字作为参数；它永远不会溢出堆栈：

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

…正如我之前所说，尾部调用是一种goto。因此，一个非常有用的适当尾部调用在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 roomendend
function room2 ()local move = io.read()if move == "south" then return room4()elseif move == "west" then return room1()else print("invalid move")return room2()endend
function room3 ()local move = io.read()if move == "north" then return room1()elseif move == "east" then return room4()else print("invalid move")return room3()endend
function room4 ()print("congratulations!")end

所以你看，当你进行递归调用时，比如：

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

这不是尾递归，因为在进行递归调用后，您仍有事情要做（添加1）。如果您输入非常高的数字，可能会导致堆栈溢出。

小开

重要的一点是尾递归本质上等同于循环。这不仅仅是编译器优化的问题，而是关于表现力的基本事实。这是双向的：你可以采用以下形式的任何循环

while(E) { S }; return Q

其中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);}

（这种用参数较少的函数“包装”尾递归函数是一种常见的函数习惯用法。）

小开
最佳答案

考虑一个简单的函数，它将前N个自然数相加（例如sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15）。

这是一个使用递归的简单JavaScript实现：

function recsum(x) {if (x === 0) {return 0;} 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 + recsum(0)))))5 + (4 + (3 + (2 + (1 + 0))))5 + (4 + (3 + (2 + 1)))5 + (4 + (3 + 3))5 + (4 + 6)5 + 1015

请注意，在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，因为Python解释器不支持尾调用优化

小开

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

我写了一篇关于这个主题的博客帖子，其中有堆栈帧外观的图形示例。

小开

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

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

Tail-Recursion表示结束函数的递归：

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

看，未结束函数（过程，在模式行话中）做的最后一件事是调用自己。另一个（更有用的）例子是：

(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之后）。

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

小开

这是前面提到的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}
小开

在Java，这是斐波那契函数的一个可能的尾递归实现：

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);}
小开

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

非常简单和直观的理解。

判断递归函数是否为尾递归的一个简单方法是它是否在基本情况下返回一个具体值。这意味着它不返回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);}}
小开

这是一个使用尾递归进行阶乘的Common Lisp示例。由于无堆栈的性质，可以执行非常大的阶乘计算… 

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

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

小开

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

这是一篇文章，其中包含C#、F#和C++\CLI：C#、F#和C++\CLI中的尾递归冒险中的一些示例。

C#不优化尾调用递归，而F#优化。

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

关于F#中的尾调用，有关非常好的介绍文章，请参阅F#中尾部调用的详细介绍。最后，这里有一篇文章介绍了非尾递归和尾调用递归（在F#中）之间的区别：F尖中的尾递归与非尾递归。

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

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

小开

对我来说，理解tail call recursion的最好方法是递归的特殊情况，其中最后一次通话（或尾调用）是函数本身。

比较Python中提供的示例：

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

^递归

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

尾部递归

正如您在通用递归版本中看到的，代码块中的最终调用是x + recsum(x - 1)。所以在调用recsum方法之后，还有另一个操作是x + ..。

但是，在尾递归版本中，代码块中的最终调用（或尾调用）是tailrecsum(x - 1, running_total + x)，这意味着最后一次调用是对方法本身进行的，之后没有操作。

这一点很重要，因为这里看到的尾递归不会使内存增长，因为当底层VM看到一个函数在尾部位置调用自己（函数中要计算的最后一个表达式）时，它会消除当前堆栈帧，这就是所谓的尾调用优化（TCO）。

编辑

注意。请记住，上面的示例是用Python编写的，其运行时不支持TCO。这只是一个解释这一点的例子。TCO在模式、Haskell等语言中得到支持

小开

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

在对比迭代和递归时，我们必须小心不要将递归过程的概念与递归过程的概念混淆递归过程。当我们将过程描述为递归时，我们是指过程定义所指的句法事实（直接或间接）到程序本身。但是当我们将一个过程描述为遵循一个模式，例如线性地递归，我们谈论的是过程如何演变，而不是关于如何编写过程的语法。这可能看起来令人不安我们将递归过程（例如face-iter）称为生成然而，这个过程实际上是迭代的：它的状态完全由它的三个状态变量捕获，并且解释器只需要跟踪三个变量即可执行该过程。

过程和过程之间的区别可能是令人困惑的是，大多数通用语言的实现（包括Ada、Pascal和C）以这样一种方式设计，即任何递归的解释过程消耗的内存量随着过程调用，即使所描述的过程原则上是，因此，这些语言可以描述迭代仅通过诉诸特殊用途的“循环构造”来处理例如do、重复、直到、for和同时。实现方案没有这个缺陷。它将在常量空间中执行迭代过程，即使迭代过程由递归过程描述。一个使用此属性的实现称为尾递归。使用尾部递归实现，迭代可以使用普通过程调用机制，使特殊迭代结构仅作为语法糖有用。

小开

简而言之，尾递归将递归调用作为函数中的最后语句，因此它不必等待递归调用。

所以这是一个尾递归，即N（x-1， p*x）是函数中的最后一个语句，编译器很聪明地发现它可以优化为for循环（阶乘）。第二个参数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 StudioC++-汇编视图”的长篇文章

在此处输入图片描述

小开

尾递归就是你现在的生活。你不断地回收同一个堆栈帧，一遍又一遍，因为没有理由或方法返回到“以前的”帧。过去的已经结束了，所以它可以被丢弃。你得到一个帧，永远进入未来，直到你的进程不可避免地死亡。

当你考虑到一些进程可能使用额外的帧，但如果堆栈不是无限增长，则仍然被认为是尾递归的时，这个类比就会失效。

小开

这个问题有很多很好的答案……但我忍不住加入了另一种关于如何定义“尾递归”的观点，或者至少是“正确的尾递归”。即：应该将其视为程序中特定表达式的属性吗？还是应该将其视为编程语言的实现的属性？

关于后一种观点的更多信息，有Will Clinger的经典论文，“适当的尾递归和空间效率”（PLDI 1998），它将“适当的尾递归”定义为编程语言实现的属性。该定义的构造允许人们忽略实现细节（例如调用堆栈实际上是通过运行时堆栈还是通过堆分配的帧链表表示）。

为了实现这一点，它使用渐近分析：不是像人们通常看到的那样对程序执行时间进行分析，而是对程序空间使用进行分析。这样，堆分配链表与运行时调用堆栈的空间使用最终是渐近等价的；所以人们可以忽略编程语言实现的细节（这个细节在实践中当然很重要，但是当人们试图确定给定实现是否满足“属性尾递归”的要求时，可能会使水变得相当混乱）

这篇论文值得仔细研究，原因有几个：

  • 它给出了程序尾表达式和尾部呼叫的归纳定义。（这样的定义，以及为什么这样的调用很重要，似乎是这里给出的大多数其他答案的主题。）

    以下是这些定义，只是为了提供文本的味道：

    定义1用核心方案编写的程序的尾表达式归纳定义如下。

    1. lambda表达式的主体是一个尾表达式
    2. 如果(if E0 E1 E2)是一个尾表达式，那么E1和E2都是尾表达式。
    3. 没有别的是尾巴表达。

    定义2 A尾部呼叫是一个尾表达式，它是一个过程调用。

（尾递归调用，或者正如论文所说，“自尾调用”是尾调用的特殊情况，其中过程本身被调用。）

  • 它为六个不同的“机器”提供了形式化定义，用于评估核心方案，其中每台机器对于每个机器所在的渐近空间复杂度类具有相同的可观察行为除了。

    例如，在分别给出以下机器的定义后：1.基于堆栈的内存管理，2.垃圾回收机制但没有尾调用，3.垃圾回收机制和尾调用，本文继续使用更高级的存储管理策略，例如4.“evlis尾递归”，其中环境不需要在尾调用中最后一个子表达式参数的评估中保留，5.将闭包的环境减少到闭包的自由变量只是，以及6.由阿佩尔和绍定义的所谓“空间安全”语义学。

  • 为了证明这些机器实际上属于六个不同的空间复杂度类别，本文针对每对被比较的机器，提供了具体的程序示例，这些程序将在一台机器上暴露渐近空间爆炸，而不是在另一台机器上。

（现在阅读我的答案，我不确定我是否能够真正抓住粘纸的关键点。但是，唉，我现在不能花更多的时间来发展这个答案。）

小开

尾递归是一个递归函数，函数调用本身在函数的末尾（“尾”），其中没有计算在递归调用返回后完成。许多编译器优化为将递归调用更改为尾递归或迭代调用。

考虑一个数的阶乘计算问题。

一个直截了当的办法是：

  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），但没有任何调用向堆栈添加任何额外的变量。因此编译器可以取消堆栈。

小开

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

在头递归中，一个函数进行递归调用，然后执行更多计算，可能使用例如，递归调用。

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

来自这个超级棒的帖子。请仔细阅读

小开

很多人已经在这里解释了递归。我想引用里卡尔多·特雷尔在《并发在. NET中，并发和并行编程的现代模式》一书中对递归带来的一些优势的一些想法：

"函数递归是在FP中迭代的自然方式，因为它避免状态的突变。在每次迭代期间，都会传递一个新值进入循环构造函数而不是被更新（突变）。在此外，可以组合递归函数，使您的程序更加模块化，并引入机会来开发

以下是同一本书中关于尾递归的一些有趣的笔记：

尾调用递归是一种将常规递归转换为功能转换为可处理大输入的优化版本没有任何风险和副作用。

注意尾部调用作为优化的主要原因是改进数据局部性、内存使用率和缓存使用率。通过执行尾部调用时，被调用者使用与调用者相同的堆栈空间。这减少了内存压力。它略微改善了缓存，因为相同的内存被重复用于后续调用者，并且可以留在缓存中，而不是驱逐旧的缓存行为新缓存腾出空间行。

小开

递归函数是自身调用的函数

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

缺点是他们可以造成无限循环和其他意想不到的结果，如果没有写好。

我来解释一下简单递归函数和尾递归函数

为了写一个简单递归函数

  1. 首先要考虑的是你应该什么时候决定出柜的循环，也就是if循环
  2. 第二个是如果我们是自己的函数要做什么过程

从给定的示例：

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

从上面的例子

if(n <=1)return 1;

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

elsereturn n * fact(n-1);

实际处理是要做的

为了便于理解，让我把任务一一分解。

让我们看看如果我运行fact(4)内部会发生什么

  1. 替换n=4
public static int fact(4){if(4 <=1)return 1;elsereturn 4 * fact(4-1);}

If循环失败，所以它转到else循环所以它返回4 * fact(3)

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

    替换n=3

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

If循环失败，所以它进入else循环

所以它返回3 * fact(2)

请记住，我们称之为“4*事实（3）”。

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

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

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

    代入n=2

public static int fact(2){if(2 <=1)return 1;elsereturn 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)

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

    替换n=1

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

If循环为真

所以它返回1

记得我们叫过4 * 3 * 2 * fact(1)

fact(1) = 1的输出

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

最后，事实（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)

  1. 在堆栈内存中，我们有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)

  1. 在堆栈内存中，我们有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)

  1. 在堆栈内存中，我们有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的输出

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

在此处输入图片描述

小开

尾递归函数是一个递归函数，它在返回之前执行的最后一个操作是进行递归函数调用。也就是说，递归函数调用的返回值会立即返回。例如，您的代码如下所示：

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

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

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

def factorial(number):if number == 1:# BASE CASEreturn 1else:# 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 CASEreturn accumulatorelse:# 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个帧对象。）这会导致堆栈溢出错误。（嘿，这就是这个网站的名字来自的地方！）

然而，如果你的递归函数做的最后一件事是进行递归调用并返回其返回值，那么它没有理由保持当前框架对象需要留在调用堆栈上。毕竟，如果递归函数调用后没有代码，没有理由挂住当前框架对象的局部变量。因此我们可以立即摆脱当前框架对象，而不是将其保留在调用堆栈上。这样做的最终结果是你的调用堆栈的大小不会增长，因此无法堆栈溢出。

编译器或解释器必须将尾调用优化作为一项功能，以便能够识别何时可以应用尾调用优化。即便如此，你可能仍需重新排列递归函数中的代码以利用尾调用优化，而这种潜在的易读性下降是否值得优化取决于你。

小开

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

小开

如果每个递归情况都包含对函数本身的调用的只有，则函数是尾递归的，可能带有不同的参数。或者，尾递归是无挂起工作的递归。请注意，这是一个独立于编程语言的概念。

考虑将函数定义为：

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时，我们基本上使用了结合性这不是偶然的，在大多数情况下，你需要将递归转换为尾递归将利用这样的属性：如果我们想热切地做一些工作而不是让它挂起，我们必须使用类似结合性的东西来证明答案是相同的。

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

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

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

小开
  • 尾递归函数是一个递归函数，其中递归调用是函数中最后执行的东西。

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

O(N)=>O(1)

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

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

  • Haskell和Java有尾递归优化

正则递归阶乘

function Factorial(x) {//Base case x<=1if (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次阶乘（）调用，空间为O（n）
  • 这可能会导致Stackoverflow

尾递归阶乘

function tailFactorial(x, totalSoFar = 1) {//Base Case: x===0. In recursion there must be base case. Otherwise they will never stopif (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 callreturn tailFactorial(x - 1, totalSoFar * x);}}
  • 在我们进行递归调用之后，我们不需要记住任何东西

提交答案