为什么尾递归模函数可以优化？
尾递归优化是一种编译器或解释器对递归函数进行优化的技术。在传统的递归函数中，每次递归调用都会在调用栈中创建一个新的帧，保存函数的局部变量和返回地址。当递归调用层级较深时，调用栈可能会耗尽内存，导致栈溢出。
尾递归是指递归函数的最后一个操作是递归调用自身，并且该递归调用的返回值直接被当前函数返回，不再进行任何操作。尾递归优化通过将尾递归转化为循环来避免创建新的调用帧，从而减少内存消耗。
尾递归优化的原理是利用函数调用的尾部位置，将递归调用转化为循环。在优化后的尾递归函数中，每次递归调用都会更新函数的参数，而不是创建新的调用帧。这样可以避免调用栈的不断增长，节省内存空间。
尾递归优化的优势主要体现在以下几个方面：
- 节省内存空间：尾递归优化避免了不断创建新的调用帧，减少了内存消耗，特别是在递归调用层级较深时，可以有效避免栈溢出的问题。
- 提高性能：尾递归优化将递归转化为循环，减少了函数调用的开销，提高了程序的执行效率。
- 简化代码逻辑：尾递归优化将递归函数转化为循环结构，使代码逻辑更加清晰简洁，易于理解和维护。
尾递归优化适用于递归调用层级较深，且每次递归调用都依赖于上一次递归调用的结果的情况。常见的应用场景包括数学计算、遍历和搜索算法等。
腾讯云提供了云函数（Serverless Cloud Function）服务，可以用于部署和运行尾递归优化后的函数。云函数是一种无服务器计算服务，可以根据实际需求自动分配和释放计算资源，无需关心服务器的运维和扩展。您可以通过腾讯云云函数服务来部署和运行尾递归优化后的函数，实现高效的计算和资源利用。
更多关于腾讯云云函数的信息和产品介绍，请访问腾讯云云函数官方文档：腾讯云云函数
相关·内容
我正在解决上发布的问题。其中之一是编写一个函数来计算列表的长度。它应该是尾递归的。
天真的、非尾递归的解决方案是：
let rec length_naive xs = (** Not tail recursive *)
match xs with
| [] -> 0
| _ :: xs -> 1 + length_naive xs;;
(length_naive [@tailcall]) [1, 2, 3, 4];;
let one_hundred_million = 100000000;;
let non_tail_result = length_naive(L
浏览 13提问于2022-08-31得票数 2
回答已采纳
我理解递归函数的问题和堆栈溢出问题的风险。
然而，如果一个函数能够被优化为尾部递归，那么为什么这个优化不自动应用于ie。为什么我需要标记一个可以用@tailrec优化的函数？
浏览 1提问于2016-01-26得票数 4
回答已采纳
1回答
在阅读时，我在Haskell中编写了这个几乎是尾部递归的示例：
triangle :: Int -> Int
triangle 0 = 0
triangle x = x + triangle (x - 1)
这当然不是一个尾调用，因为尽管递归调用在“返回”本身中，但是x +防止当前堆栈被重用到递归调用中。
但是，可以将其转换为尾递归代码(尽管非常丑陋和冗长)：
triangle' :: Int -> Int
triangle' = innerTriangle 0
where innerTriangle acc 0 = acc
innerT
浏览 4提问于2016-03-09得票数 3
回答已采纳
1回答
引用
...a尾调用是作为过程的最终动作执行的子例程调用。如果尾调用可能导致调用链后面再次调用相同的子例程，则该子例程被称为尾递归，这是递归的特例。
现在我已经用C编写了下面的例程
int foo (int x){
if ( x > 100)
return x-10;
else
return foo(foo(x+11));
}
基于上面的定义，在我看来foo应该是一个尾递归函数，因为它的递归调用是过程的最终操作，但在我曾经读过的某个地方，它不是尾递归函数。
因此，问题是：
为什么这个函数不是尾递归的？
浏览 6提问于2015-05-25得票数 1
2回答
我最近在学习日期结构。在Mark的书“C中的数据结构和算法分析”中，为什么他说尾递归是递归的糟糕用法，最好不要在第三章中使用它？但我看到很多人说它在网上很有用。
浏览 0提问于2013-09-10得票数 4
回答已采纳
1回答
鉴于这一守则：
int x;
int a (int b) {
b = a (b);
b += x;
return b;
}
GCC为什么要返回这个输出(英特尔语法)： -哥德波特的GCC资源管理器
a:
sub rsp, 8
call a
mov edx, DWORD PTR x[rip]
add rsp, 8
lea eax, [rax+rdx*8]
add eax, edx
ret
并返回此输出(AT&T语法)： -Godbolt的Clang
a:
浏览 2提问于2014-06-29得票数 4
回答已采纳
2回答
在erlang中，尾递归比前向递归更好吗？
或者erlang编译器也优化了前向递归？
我的意思是，有没有理由使用尾递归而不是前向递归？
在我看来，前向递归看起来更漂亮。
浏览 2提问于2011-02-09得票数 6
回答已采纳
我在思考这里提出的问题之一()以及如何改进代码。
不管怎样，我是这样想的：
def simpledb_update(name: String, metadata: Map[String, String]) = {
def inner_update(attempt: int): Unit = {
try {
db(config("simpledb_db")) += (name, metadata)
return
} catch {
case e =>
if (attempt >= 6) {
浏览 1提问于2011-03-15得票数 1
回答已采纳
3回答
我在下面的F#定义中看到了一个连续传递风格的斐波纳契函数，我一直认为它是尾递归的：
let fib k =
let rec fib' k cont =
match k with
| 0 | 1 -> cont 1
| k -> fib' (k-1) (fun a -> fib' (k-2) (fun b -> cont (a+b)))
fib' k id
在Scala中尝试等效代码时，我使用了现有的@ tail are，当Scala编译器通知我递归调用不处于尾位置时，我感到措手不及：
def fib(k
浏览 5提问于2015-06-23得票数 3
回答已采纳
有没有人写了一篇正式的论文，描述了一种(自动)将函数转换为尾递归函数的方法？我正在寻找一种大学级别的正式治疗，包括限制(可以转换的函数类型)，转换过程，如果可能的话，还有正确性的证明？Haskell中的例子将是一个额外的奖励。
浏览 0提问于2012-05-22得票数 10
回答已采纳
2回答
我读过一篇文章，声称foldl可能很容易发生堆栈溢出。发布示例代码为：
maximum [1..1000000]
代码不会在我的机器上溢出。但是，它可能会因环境而异。我像这样增加了数字：
maximum [1..1000000000]
它导致了硬盘交换，所以我不得不停止评估。示例代码并不重要。堆栈溢出真的发生了吗？或者仅仅是一个过去的故事？
浏览 1提问于2011-02-12得票数 4
回答已采纳
4回答
在这个站点和web的其他地方搜索，JVM不支持尾调用优化。因此，这是否意味着如果要在JVM上运行，就不应该编写尾部递归Scala代码，例如可以在非常大的输入列表上运行的以下代码？
// Get the nth element in a list
def nth[T](n : Int, list : List[T]) : T = list match {
case Nil => throw new IllegalArgumentException
case _ if n == 0 => throw new IllegalArgu
浏览 10提问于2011-04-17得票数 11
如果运行以下代码：
public static void main(String[] argsv) {
long whichFib = 45;
long st;
st = System.currentTimeMillis();
System.out.println(recursiveFib(whichFib));
System.out.println("Recursive version took " + (System.currentTimeMillis() - st) + " milliseconds.");
浏览 4提问于2013-01-12得票数 2
回答已采纳
2回答
我在读。其中一个提到：
让编译器生成尾递归代码似乎是一个简单的想法。但是大多数用于通用语言的编译器，包括C和Pascal，都不这样做，因此这些语言不能仅用过程调用来表示迭代过程。在这些语言中，尾递归的困难在于它们的实现使用堆栈来存储过程参数和局部变量以及返回地址。
如果堆栈用于过程参数、局部变量和返回地址，我无法理解为什么不能实现尾递归。
浏览 2提问于2014-12-22得票数 4
回答已采纳
5回答
tailrec在有尾递归的地方优化函数。为什么编译器不只是优化它呢？
C编译器优化尾递归。您不必将该方法标记为有尾递归。编译器只是注意到最后一个操作是递归的。就是这样。
为什么这个看似过度的关键字存在？我错过了什么吗？这纯粹是为了编译器而不是用户的方便吗？
浏览 0提问于2018-08-01得票数 27
2回答
我对pascal三角形有如下函数。为什么打电话
pascal_cont(a-1, b-1, (x:Int) => pascal_cont(a, b-1, (y:Int) => cont(x + y)))
尾巴不是递归的吗？
def pascal(c: Int, r: Int): Int = {
def pascal_cont(a:Int, b:Int, cont: (Int) => Int): Int = {
if (a==0 || a==b) cont(1)
else pascal_cont(a-1, b-1, (x:Int) => pascal_
浏览 0提问于2013-09-29得票数 1
回答已采纳
既然.net有操作码，这能用来判断一个F#函数是否真的是尾递归的吗？
如果这是真的，有没有人做了一个识别尾部和非尾部函数的VS插件？
浏览 0提问于2012-03-14得票数 4
回答已采纳
1回答
尾递归:比较两种情况
、、、
为什么这是尾部递归：
def navigate(myList : List[Int]) : (Int, List[Int]) = {
def navigate(step: Int, offset: Int, myList: List[Int]): (Int, scala.List[Int]) = {
if //some test and exit condition, then a definition of jump
else navigate(step + 1, offset + jump, myList)
}
navigate(0, 0
浏览 1提问于2017-12-06得票数 1
简短的问题是:如果编译器或解释器支持尾调用递归优化(TCO)或尾递归消除(TRE)，什么才能满足它的要求？
这个问题的摘要在下面这一节“或者说，一种最简单的思考它的方式”中。
我也看到了堆栈溢出问题“什么是尾递归消除？”，并阅读了关于如何发生尾调用递归的不同描述。
第一项：
尾调用是作为一个过程的最终动作执行的子例程调用(Wikipedia截至2016年1月10日)
第二项：
当递归调用返回的值本身立即返回时(编程访问暴露，Wiley，2013年)
第三项：
当一个函数调用自己时，它不能使用包含局部变量的值执行任何操作，只需返回它。此调用发生在函数的末尾，因此堆栈中的任何局部变量或“状态”(在
浏览 0提问于2016-01-10得票数 3
1回答
这不是尾递归吗？(堆栈溢出错误)
、、、、
这是我写的一个小函数，用来检查一个整数是否为质数：
int prime(int x, int y = 2)
{
if(y <= x/2)
{
if((x % y) == 0)
return 0;
}
else
return 1;
return prime(x, ++y);
}
现在，我用visual Studio2012编译它，如果我给它一个很大的值，比如105943，就会发生堆栈溢出错误，代码会中断。现在，这个函数不是尾递归的吗？如果是这样，那么不应该为递归调用维护堆栈，并且不应该发生溢出
浏览 2提问于2013-06-20得票数 2
回答已采纳
我编写了三个版本的fibonacci序列，我不太确定它们的时间/空间复杂性(以及为什么)：
变体1:头递归
int fibonacci_h(int n) {
if (n == 1 || n == 2) {
return 1;
}
return fibonacci_h(n - 1) + fibonacci_h(n - 2);
}
变体2:尾递归
int fibonacci_t(int n, int s_last = 0, int last = 1) {
if (n == 1) {
return last;
}
return fibonacci_t(n -
浏览 0提问于2020-10-23得票数 1
3回答
我见过很多在二进位排序树中搜索的搜索算法，但它们都使用了相同的方法:递归。我知道与循环相比递归花费很大，因为每次我们调用搜索函数时，都会为该方法创建一个新的堆栈框架，如果二叉树太大，最终会占用大量内存。
为什么我们不能像这样搜索二进制搜索树：
while (root!=NULL)
{
if (root->data==data)
return 0;
else if (data > root->data)
root=root->right;
else
root=root->left;
}
我认为这
浏览 5提问于2014-08-09得票数 0
回答已采纳
3回答
我目前正在阅读计算机程序(SICP)的结构和解释。在这本书的过程中，“您可以通过将递归过程写成尾递归来优化递归过程”的课程一遍又一遍地向读者灌输。事实上，我已经有将近100页了，而且还没有看到一个for或while循环--都是递归的。这开始让我担心了。据我所知，优化尾调用的方式可以有效地将尾递归过程转换为迭代过程，这在现代编程语言中并不常见。这给了我一个问题:如果我使用的是一种没有对尾递归进行优化的语言，我如何应用SICP教授的这些课程？知识是可以转让的吗？
浏览 0提问于2020-11-15得票数 2
回答已采纳
4回答
在“像程序员一样思考”一书中，下面的递归函数被说成“效率很低”，我不知道为什么(这本书没有解释)。似乎没有任何不必要的计算正在进行。这是因为调用这么多函数(好，同一个函数多次)，从而为每个函数调用设置环境的开销吗？
int factorial(int n) {
if (n == 1) return 1;
else return n * factorial(n-1);
}
浏览 4提问于2013-12-12得票数 3
回答已采纳
2回答
def singlesR(xs):
if xs != [] :
return [[xs[0]]] + singlesR(xs[1:])
else :
return []
如何转换为尾递归函数？
#result value
singlesR([1,2,3,4]) == [[1], [2], [3], [4]]
浏览 4提问于2022-03-21得票数 1
回答已采纳
2回答
在Scala2.8.x中，添加了一个新的注释(@tailrec)，如果编译器不能对带注释的方法执行尾调用优化，则会产生编译时错误。
在loop/recur方面，是否有类似的工具
编辑:在阅读了我的问题的第一个答案(谢谢，Bozhidar )并在Clojure文档中进一步搜索之后，我看到了以下内容：
(重述exprs*)
按顺序计算exprs，然后并行地将递归点的绑定重新绑定到exprs的值。如果递归点是fn方法，则重新绑定params。如果递归点是循环，则重新绑定循环绑定。执行然后跳回递归点。重新出现的表达式必须与递归点的一致性完全匹配。特别是，如果递归点是变量fn方法的顶部，则不需要收集re
浏览 2提问于2010-04-26得票数 9
回答已采纳
1回答
了解如何将递归转换为蹦床
、、、
我最近读到过关于蹦床是一种消除尾部呼叫的方法。我想把我的一个功能转换成使用蹦床的东西，但是我很难开始工作(我是从OO世界来的)。
def buildTree (X:DenseMatrix[Double], Y:DenseVector[Double], minBucket:Int):Node = {
// Get the split variable, split point and data for this data
val (splitVar, splitPoint, leftX, leftY, rightX, rightY) = chooseSplit(X
浏览 5提问于2014-04-01得票数 0
回答已采纳
这里的helper函数是：
def zipWith[B]: (MyList[B], (A, B) => B) => MyList[B] = {
(list, function) => {
def helper: (MyList[B], MyList[A], MyList[B]) => MyList[B] = {
(consList, originalList, modList) =>
val wrapList = if (modList.isEmpty) list else modList
if (origi
浏览 1提问于2022-03-17得票数 0
回答已采纳
2回答
函数编程中有这样的CPS技巧，即采用非尾递归函数，并以连续传递方式(CPS)重写它，从而使其成为尾递归函数。很多问题都涉及到这个问题，比如
举个例子
let rec count n =
if n = 0
then 0
else 1 + count (n - 1)
let rec countCPS n cont =
if n = 0
then cont 0
else countCPS (n - 1) (fun ret -> cont (ret + 1))
第一个版本的count将在每个递归调用中累
浏览 6提问于2016-02-01得票数 7
回答已采纳
显然，关于Python是否需要尾部调用优化(TCO)，存在着很大的争议。当有人的时候，这件事到了极点，因为他没有“明白”。我和在同一条船上。我理解尾叫优化的概念。我只是想不出为什么Python真的需要它。
为了使我更容易理解这一点，使用TCO将大大简化的代码片段是什么？
浏览 6提问于2009-05-20得票数 20
回答已采纳
2回答
我从下面的程序中解释的是它是尾递归的，因为在函数返回的最后，没有什么需要计算的了。我说的对吗？
void fun(int x)
{
if(x > 0)
{
fun(--x);
printf("%d\t", x);
fun(--x);
}
}
浏览 0提问于2018-12-15得票数 2
4回答
我认为在函数式编程语言中非常有用。那C呢？
C语言或编译器是否支持尾调用消除
程序是否为新调用创建新的堆栈框架？
来自wiki：
可以在不向调用堆栈添加新堆栈帧的情况下实现尾调用。当前过程的大部分框架不再需要，它可以被尾调用的框架所取代，并根据需要进行修改(类似于对进程的覆盖，但对于函数调用)。
然后，程序可以跳到被调用的子例程。产生这样的代码而不是标准的调用序列称为尾呼叫消除。
浏览 5提问于2016-02-02得票数 0
回答已采纳
1回答
我注意到新版本的JSLint不喜欢某些形式的for循环。我发现这很奇怪，于是开始寻找一些解释。在JsLint的中，您可以找到以下内容：
ES6最重要的新特性是正确的尾调用。这没有新的语法，所以jsLint没有看到它。但是它使递归更有吸引力，这使得循环，特别是循环，变得更加吸引人。
这是：
jsLint不建议使用for语句。而是使用像forEach这样的数组方法。for选项将禁止某些警告。jsLint接受的forms格式受到限制，不包括新的ES6表单。
这两条语句给我留下了一个混乱的字节。我一直觉得for循环是最好的循环方式，主要是因为：
有些迭代方法还没有得到很好的支持。
浏览 1提问于2015-05-21得票数 8
回答已采纳
3回答
F#内存管理
、、、
在F#中，当您在循环中传递一个数组(递归函数调用自身)时，数组是否放在堆栈上(添加内存消耗)？在循环列表或引用对象时，它是如何工作的？您能以某种方式将内存消耗降到最低吗?也许可以使用ref (引用)？
浏览 2提问于2015-05-28得票数 2
回答已采纳
我们先从
boom :: Int -> Maybe a -> Maybe a
boom 0 x = x
boom n x = boom (n-1) (x >>= (\y -> Just y))
它是一个简单的函数，它只是重复(>>=)将一个Maybe值推入一个普通的\y -> Just y函数中。
现在，程序
main = do
let z = boom 10 (Nothing :: Maybe Int)
putStrLn $ show z
一刹那就跑得很快。然而，该计划
main = do
let z = boom 10
浏览 0提问于2015-03-29得票数 4
回答已采纳
我碰巧在Scala上看到了一个由Mr.Martin Odersky编写的Mr.Martin。要找到一个数字的阶乘，这是我写的函数。
def factorial(n: Int): Int = {
if (n == 0) 1
else n * factorial(n - 1)
}
然而，当我看到这段视频时，奥德斯基先生是这样说的。
def factorial(n : Int): Int = {
def loop(acc: Int, n: Int): Int = {
if (n == 0) acc
else loop(acc * n, n-1)
}
浏览 2提问于2015-03-11得票数 1
回答已采纳
2回答
这是尾递归吗？
、、、、
我试图找出尾递归的例子，但我真的看不到规则和尾之间的区别。如果这不是尾递归，有人能告诉我为什么不是吗？
public static long fib(long index) {
// assume index >= 0
if (index == 0) // Base case
return 0;
else
if (index == 1) // Base case
return 1;
else
// Reduction and recursive calls
return fib(index - 1) + fib(index - 2);
浏览 1提问于2013-09-03得票数 4
回答已采纳
Emacs lisp是LISP的一种方言，尤其是Scheme。大多数scheme解释器都有尾递归的优化，但emacs lisp没有。我在‘`info elisp’中搜索了一下原因，但我没有找到它。
附注:是的，在elisp中还有像‘`while’这样的其他迭代语法，但我仍然找不到一个很好的理由来解释为什么他们没有像其他模式解释器那样实现尾递归。
浏览 8提问于2016-07-21得票数 8
回答已采纳
2回答
我试图在n! % m中使用递归计算C。这是我正在使用的
#include<stdio.h>
#define m 1000000007
long long int fact(long long int n) {
if(n == 1)
return (1);
long long int n2 = (long long int)(fact(n-1));
long long int k = (n*n2)%m;
return k;
}
int main() {
printf("%lld",fact(1000000))
浏览 4提问于2014-09-05得票数 0
回答已采纳
3回答
我在方案中实现了这个递归函数：
(define f (lambda (n)
(cond ((= n 0) 0)
((= n 1) 2)
((= n 2) 37)
((odd? n) (+ (f (- n 3)) 1))
(else (+ (f (- (/ n 2) 1)) 7))))
)
在很多练习中，我被问到我的解决方案是否是尾递归，老实说，不管我读了多少次尾递归的定义，我就是不明白。如果我要定义尾递归，它会是这样的。
定义:无论输
浏览 4提问于2015-09-14得票数 1
回答已采纳
3回答
我正在阅读标准haskell库(^)的实现代码：
(^) :: (Num a, Integral b) => a -> b -> a
x0 ^ y0 | y0 < 0 = errorWithoutStackTrace "Negative exponent"
| y0 == 0 = 1
| otherwise = f x0 y0
where -- f : x0 ^ y0 = x ^ y
f x y | even y = f (x * x) (y `quot` 2)
浏览 2提问于2016-07-26得票数 8
回答已采纳
1回答
为什么这段代码会在堆中溢出CMUCL？即使我给它400 on的内存，(setq extensions:*bytes-consed-between-gcs* 400000000) CMUCL仍然会被它阻塞。
; [GC threshold exceeded with 12,012,544 bytes in use. Commencing GC.]
; [GC completed with 188,064 bytes retained and 11,824,480 bytes freed.]
; [GC will next occur when at least 400,188,064 byte
浏览 2提问于2013-03-15得票数 1
1回答
我一直在试图理解延续/ CPS，从我所能收集到的内容来看，一旦我们到了列表的末尾，我们就会调用最终的计算，从而构建一个延迟计算。
我不明白的是，为什么CPS看起来类似于按照示例1中的简单方法构建嵌套函数，却防止堆栈溢出。很抱歉，很长一段时间后，CPS试图从基础方面展示这种想法(可能是出错的地方)：
所以：
let list1 = [1;2;3]
示例1：“朴素方法”
let rec sumList = function
|[] -> 0
|h::t -> h + sumList t
因此，当它运行时，迭代的结果是：
1 + sumList [2;3]
1 +
浏览 5提问于2013-04-01得票数 13
回答已采纳
3回答
我知道什么是尾部递归算法作为。然而，我正在研究这个，在18:30秒，教授说这是尾部递归算法。我无法连接这是如何进行尾递归的。我们没有在递归的任何一步进行计算，或者我们是在做计算？你能解释一下为什么这被引用为尾部递归算法的一个例子吗？请将你的答案建立在这样一个前提之上:我知道递归算法是什么。我不清楚的部分是为什么它被称为尾递归？
浏览 3提问于2012-08-08得票数 6
2回答
使用尾递归实现Tak函数
、、、
是否有可能实现
尾部递归在C/C++中的一种方式，以便使gcc/g++可以执行尾部递归优化？
我不确定嵌套的递归函数调用是否会使编译器感到困惑。
浏览 0提问于2013-11-14得票数 0
6回答
据我所知，由于函数调用的开销，递归函数通常比等效的非递归函数效率低。然而，我最近遇到了一本教科书，书中说这对Java (和C#)来说不是必须的。
它没有说明原因，但我认为这可能是因为Java编译器以某种方式优化了递归函数。
有没有人知道为什么会这样？
浏览 1提问于2011-03-11得票数 6
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
