当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?
当前回答
术语文件对尾部递归的定义有这样的说法:
尾部递归/n/
如果您还没有厌倦它,请参阅尾部递归。
其他回答
对我来说,理解尾调用递归的最好方法是递归的一种特殊情况,其中最后一个调用(或尾调用)是函数本身。
比较Python中提供的示例:
def recsum(x):
if x == 1:
return x
else:
return x + recsum(x - 1)
^递归
def tailrecsum(x, running_total=0):
if x == 0:
return running_total
else:
return tailrecsum(x - 1, running_total + x)
^尾部递归
正如您在常规递归版本中看到的,代码块中的最后一个调用是x+recsum(x-1)。所以在调用recsum方法之后,还有一个操作是x+。。。
然而,在尾部递归版本中,代码块中的最后一个调用(或尾部调用)是tailrecsum(x-1,running_total+x),这意味着最后一次调用是对方法本身进行的,之后不再进行操作。
这一点很重要,因为这里看到的尾部递归不会使内存增长,因为当底层VM看到一个函数在尾部位置(函数中要计算的最后一个表达式)调用自己时,它会消除当前堆栈帧,这就是所谓的尾部调用优化(TCO)。
EDIT
没有。请记住,上面的示例是用Python编写的,其运行时不支持TCO。这只是一个解释这一点的例子。在Scheme、Haskell等语言中支持TCO
下面是一个使用尾部递归进行阶乘的常见Lisp示例。由于无堆栈的性质,人们可以进行疯狂的大型阶乘计算。。。
(defun ! (n &optional (product 1))
(if (zerop n) product
(! (1- n) (* product n))))
然后为了好玩,你可以尝试(格式化nil“~R”(!25))
这意味着不需要将指令指针推到堆栈上,只需跳到递归函数的顶部并继续执行即可。这允许函数无限递归而不会溢出堆栈。
我写了一篇关于这个主题的博客文章,里面有堆栈框架的图形示例。
递归有两种基本类型:头部递归和尾部递归。
在头部递归中,函数进行递归调用,然后执行更多计算,可能使用例如递归调用。在尾部递归函数中,所有计算首先发生递归调用是最后发生的事情。
摘自这篇超棒的帖子。请考虑阅读它。
递归意味着函数调用自身。例如:
(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)。