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


当前回答

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

(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会这么做。

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

在对比迭代和递归时,我们必须小心不要将递归过程的概念与递归过程。当我们将过程描述为递归时指过程定义所指的句法事实(直接或间接)到程序本身。但当我们将过程描述为遵循一种模式,即线性递归,我们谈论的是过程如何演变,而不是如何编写过程的语法。这似乎令人不安我们将递归过程(如事实iter)称为生成迭代过程。然而,这个过程实际上是迭代的:它的状态被其三个状态变量完全捕获解释器只需要跟踪三个变量执行该过程。过程和程序之间的区别可能是令人困惑的是,大多数通用语言的实现(包括Ada、Pascal和C) 以这样一种方式设计过程消耗的内存量会随着过程调用,迭代。因此,这些语言可以描述迭代仅通过使用专用的“循环构造”来处理例如do、repeat、until、for和while。实施方案不具有此缺陷。它将在恒定空间中执行迭代过程,即使迭代过程由递归过程描述。一具有此属性的实现称为尾部递归。用一个尾部递归实现,可以使用普通过程调用机制,使特殊迭代构造只作为句法糖有用。

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

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

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

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

尾部调用[尾部递归]是一种goto-dressed作为呼叫。当函数调用另一个作为其最后一个行动,所以它没有其他事情可做。例如在以下代码中,对g的调用是尾调用:函数f(x)返回g(x)终止在f调用g之后,它没有其他内容在这种情况下,程序不需要返回调用函数时调用的函数末端。因此在尾呼之后,程序不需要保留任何有关调用函数的信息在堆栈中。。。因为正确的尾呼使用no堆栈空间一个程序可以生成。例如,我们可以使用任意数字作为自变量;它永远不会溢出堆栈:函数foo(n)如果n>0,则返回foo(n-1)end终止…正如我前面所说的,尾呼是有点后顾之忧。因此,一个非常有用的正确的尾部调用在Lua用于编程状态机。此类应用程序可以代表功能状态;更改状态是去(或打电话)一个特定的作用例如,让我们考虑一个简单的迷宫游戏。迷宫有几个房间,每个房间最多四个门:北、南、东和西在每个步骤中,用户输入移动方向。如果有门在该方向上,用户将相应的房间;否则程序打印警告。目标是从最初的房间到最后的房间房间该游戏是典型的状态机,其中当前房间是状态。我们可以用一个每个房间的功能。我们用尾巴从一个房间移动到另一个有四个房间的小迷宫可能看起来像这样:功能室1()本地移动=io.read()如果移动==“南”,则返回房间3()elseif move==“east”然后返回room2()否则打印(“无效移动”)返回房间1()--呆在同一个房间终止终止功能室2()本地移动=io.read()如果move==“south”,则返回room4()elseif move==“west”然后返回房间1()否则打印(“无效移动”)返回室2()终止终止功能室3()本地移动=io.read()如果move==“north”,则返回room1()elseif move==“east”然后返回room4()否则打印(“无效移动”)返回室3()终止终止功能室4()打印(“恭喜!”)终止

因此,当您进行如下递归调用时:

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

这不是尾部递归的,因为在进行递归调用之后,您仍然需要在该函数中做一些事情(添加1)。如果输入的数字很高,可能会导致堆栈溢出。