当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?


当前回答

尾部递归函数是一个递归函数,其中递归调用是函数中最后执行的事情。

常规递归函数,我们有堆栈,每次调用递归函数中的递归函数时,都会向调用堆栈添加另一层。在正常递归中空间: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)这可能会导致堆栈溢出

尾部递归因子

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

在进行递归调用后,我们不需要记住任何内容

其他回答

考虑一个将前N个自然数相加的简单函数。(例如,和(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 + 10
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中的示例。由于Python解释器不支持尾部调用优化,这些代码已更改为JavaScript。然而,虽然尾部调用优化是ECMAScript 2015规范的一部分,但大多数JavaScript解释器不支持它。

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

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

尾部递归是函数调用的递归函数自身位于函数的末尾(“尾部”),其中没有计算在递归调用返回后完成。许多编译器优化以将递归调用更改为尾部递归调用或迭代调用。

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

一种简单的方法是:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

假设你调用阶乘(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),但没有一个调用向堆栈添加任何额外变量。因此编译器可以取消堆栈。

递归意味着函数调用自身。例如:

(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)))

在helper过程中,如果左边不是nil,最后一件事就是调用自己(AFTER cons something和cdr something)。这基本上就是如何映射列表的。

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

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

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

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