什么是尾递归?

在开始学习 Lisp 的同时,我遇到了术语 “ 尾递归” 。到底是什么意思?

答案

考虑一个简单的函数,该函数将前 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(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

在尾递归的情况下,每次对递归调用进行评估时, running_total更新running_total

注意:原始答案使用了 Python 中的示例。这些已更改为 JavaScript,因为 Python 解释器不支持尾部调用优化 。但是,尽管尾部调用优化是ECMAScript 2015 规范的一部分,但大多数 JavaScript 解释器都不支持它

传统的递归中 ,典型的模型是先执行递归调用,然后取递归调用的返回值并计算结果。这样,直到您从每个递归调用中返回后,您才能得到计算结果。

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

这样的结果是,一旦您准备好执行下一个递归步骤,就不再需要当前的堆栈框架。这样可以进行一些优化。实际上,使用适当编写的编译器,决不应该使用尾部递归调用来实现堆栈溢出窃笑 。只需将当前堆栈框架重用于下一步递归步骤。我很确定 Lisp 会这样做。

重要的一点是,尾递归实质上等同于循环。这不仅是编译器优化的问题,还是表达能力的基本事实。这是双向的:您可以采用任何形式的循环

while(E) { S }; return Q

其中EQ是表达式, S是语句序列,并将其转换为尾递归函数

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

当然,必须定义ESQ才能对某些变量计算一些有趣的值。例如,循环功能

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

(这种尾部递归函数与较少参数的函数的 “包装” 是常见的函数习语。)

摘自《 Lua 编程 》一书的摘录显示了如何进行适当的尾递归 (在 Lua 中,但也应适用于 Lisp)以及为什么更好。

尾调用 [tail recursion] 是一种装扮成电话的 goto。当一个函数调用另一个函数作为其最后一个动作时,就会发生尾部调用,因此它无事可做。例如,在以下代码中,对g的调用是一个尾部调用:

function f (x)
  return g(x)
end

f调用g ,它无事可做。在这种情况下,当被调用函数结束时,程序无需返回到调用函数。因此,在进行尾部调用之后,程序无需在堆栈中保留有关调用函数的任何信息。 ...

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

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

就像我之前说的,尾部呼叫是 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 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)。如果输入很高的数字,可能会导致堆栈溢出。

使用常规递归,每个递归调用将另一个条目推入调用堆栈。递归完成后,该应用程序必须将所有条目从头向下弹出。

使用尾递归,根据语言的不同,编译器可能会将堆栈折叠为一个条目,从而节省了堆栈空间... 大型的递归查询实际上可能导致堆栈溢出。

基本上,尾部递归可以优化到迭代中。

这里有一个例子,而不是用语言解释。这是阶乘函数的 Scheme 版本:

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

这是尾递归的阶乘版本:

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

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

术语文件说了有关尾递归的定义:

尾递归 /n./

如果您还不满意,请参阅尾递归。

尾递归是指递归调用在递归算法中的最后逻辑指令中位于最后。

通常在递归中,您有一个基本情况 ,这是停止递归调用并开始弹出调用堆栈的基础。使用经典示例,尽管 C 函数比 Lisp 多,但阶乘函数说明了尾递归。 检查基本情况后,将进行递归调用。

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

对阶乘的初始调用为 factorial factorial(n) ,其中fac=1 (默认值),n 为要计算阶乘的数字。

这意味着您无需将指令指针压入堆栈,只需跳转到递归函数的顶部并继续执行即可。这允许函数无限递归而不会溢出堆栈。

我写了一篇有关该主题的博客文章,其中有一些图形示例显示了堆栈框架的外观。

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

非常简单直观。

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