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


当前回答

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

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

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

其他回答

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

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

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

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

为了编写简单的递归函数

首先要考虑的一点是你应该什么时候决定出来是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

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

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

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

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

下面是比较两个函数的快速代码片段。第一种是传统的递归,用于求给定数的阶乘。第二种使用尾部递归。

理解起来非常简单直观。

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

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

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

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