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


当前回答

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

在头部递归中,函数进行递归调用,然后执行更多计算,可能使用例如递归调用。在尾部递归函数中,所有计算首先发生递归调用是最后发生的事情。

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

其他回答

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

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

(用参数较少的函数“包装”尾部递归函数是一种常见的函数习惯用法。)

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

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

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

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

为了编写简单的递归函数

首先要考虑的一点是你应该什么时候决定出来是if循环的第二个问题是,如果我们是自己的职能部门,我们应该做什么

从给定的示例中:

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

是否要进行实际处理

为了便于理解,让我逐一完成任务。

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

替换n=4

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

如果循环失败,则转到else循环因此它返回4*事实(3)

在堆栈内存中,我们有4*事实(3)替换n=3

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

如果循环失败,则转到else循环

因此它返回3*事实(2)

记住我们称之为“4*事实”(3)``

事实(3)的输出=3*事实(2)

到目前为止,堆栈具有4*事实(3)=4*3*事实(2)

在堆栈内存中,我们有4*3*事实(2)替换n=2

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

如果循环失败,则转到else循环

因此它返回2*事实(1)

记住我们称之为4*3*事实(2)

事实(2)的输出=2*事实(1)

到目前为止,堆栈具有4*3*事实(2)=4*3*2*事实(1)

在堆栈内存中,我们有4*3*2*事实(1)替换n=1

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

如果循环为真

所以它返回1

记住我们称之为4*3*2*事实(1)

事实(1)的输出=1

到目前为止,堆栈具有4*3*2*事实(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);
    }
}

替换n=4

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

如果循环失败,则转到else循环因此它返回事实(3,4)

在堆栈内存中,我们有事实(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);
    }
}

如果循环失败,则转到else循环

因此它返回事实(2,12)

在堆栈内存中,我们有事实(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);
    }
}

如果循环失败,则转到else循环

因此它返回事实(1,24)

在堆栈内存中,我们有事实(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);
    }
}

如果循环为真

因此它返回running_total

running_total=24的输出

最后,事实(4,1)的结果=24

这里有一个例子,而不是用文字来解释。这是阶乘函数的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尾部递归函数使用常数堆栈空间。

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

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

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

下面是一个使用尾部递归进行阶乘的常见Lisp示例。由于无堆栈的性质,人们可以进行疯狂的大型阶乘计算。。。

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

然后为了好玩,你可以尝试(格式化nil“~R”(!25))