当前位置: 首页 > 知识库问答 >
问题:

在返回中两次调用自己——尾递归与否?

谭兴学
2023-03-14

我理解尾部递归,但是我被分配写一个代码来看看第N个斐波那契数是什么。首先,这段代码确实有效。这不是最好的方法,但它是一种方法——但是我开始担心它不是尾部递归的。代码如下:

static int fib_tail_helper(int n, int result) {
if (n == 0) {
    return result;
}   
else if (result == 0) {
    return fib_tail_helper(n - 1, result + 1);
}
else {
    return fib_tail_helper(n - 1, result + fib_tail_helper(n - 1, 0));
}
}

int fib_tail(int n) {
/*
// REQUIRES: n >= 0
// EFFECTS: computes the Nth Fibonacci number
//          fib(0) = 0
//          fib(1) = 1
//          fib(n) = fib(n-1) + fib(n-2) for (n>1).
// MUST be tail recursive
*/
return fib_tail_helper(n, 0);
}

我最担心的是“返回fib_tail_helper(n-1,结果fib_tail_helper(n-1),0”。我觉得这好像会使用另一个堆栈,因此是非尾递归的...有人能给出一些输入吗?

谢谢

共有3个答案

徐嘉谊
2023-03-14

尾递归是递归的巧妙实现,它不使用堆栈空间。

它的工作原理是这样的:如果一个函数调用自己,作为它的最后一个动作,那么这称为“尾部递归”<在这种特殊情况下,编译器可以放弃执行实际的函数调用。它可以执行返回函数开头的转到。函数的代码将再次运行,就像它已被调用一样。当函数终止时,它将返回堆栈上的最后一个地址,即最初调用递归函数的函数。

这种方法保证堆栈不会溢出,无论递归有多深。这就是尾部递归的优点所在。

坏消息是C不自动支持尾部递归。

好消息是实现尾递归非常容易。
您只需将最终函数调用替换为goto回到函数的开头。
(这只是您编写编译器会编写的goto,如果它支持尾递归的话。)

隗高旻
2023-03-14

为了证明它不是尾部递归,转换可能会有所帮助:

static int fib_tail_helper(int n, int result) {
    if (n == 0) {
        return result;
    }   
    else if (result == 0) {
        return fib_tail_helper(n - 1, result + 1);
    }
    else {
        int tailrecursivePreventingValue = fib_tail_helper(n - 1, 0);
        return fib_tail_helper(n - 1, result + tailrecursivePreventingValue);
    }
}

它与您的代码完全相同,但引入了一个解释变量。您可以看到在最后一个els-block中有2次对fib_tail_helper()的调用。这意味着指数运行时间,因为第二个值取决于第一个值。

杨飞语
2023-03-14

不,它不是尾递归的。

编译器需要首先计算fib\u tail\u helper参数,这意味着它将在继续调用最后一个fib\u tail\u helper作为返回值之前创建n-1个调用堆栈。

 类似资料:
  • 我对函数式编程很陌生,尤其是下面使用的Scheme。我正在尝试使以下函数是递归的,尾递归的。基本上,该函数的作用是对两个字符串的对齐方式进行评分。当给定两个字符串作为输入时,它会比较每个“列”字符,并根据在称为 scorer 的函数中实现的评分方案(由下面的代码中的函数调用)来累积该对齐的分数。 我有一个想法,用一个帮助函数来累积分数,但我不太确定如何去做,因此我该如何让下面的函数尾递归呢?

  • 我有以下递归javascript函数,它在Backbone.Marionette CollectionView的子级上循环,该子级具有依次为CollectionViews的ItemViews: 我是这样称呼它的: var view=DocumentManager.Documents.TreeRoot.FindViewByCID(model.cid); 问题是这一行: 如果我有这样的等级 然后te

  • 我想我理解了教科书中对尾部递归函数的定义:在函数调用后不执行任何计算的函数。我还发现,作为一个结果,尾部递归函数的内存效率会更高,因为它每次调用只需要一条记录,而不是每次都需要保留一条记录(就像在普通递归中那样)。 我不太清楚的是,这个定义如何应用于嵌套调用。我将提供一个例子: 我最初给出的答案是,根据定义,它不是尾部递归的(因为外部调用是在计算内部调用之后执行的,所以其他计算是在第一次调用之后完

  • 尾递归优化 recur 尾递归优化是函数式编程不能缺少的一个性能优化方案. 没有尾递归, 常有的递归调用也会形成很深的调用栈消耗内存. cljs 和 Clojure 类似, 都需要通过声明 recur 进行优化. 最终代码会被编译为 white 结构的 js 代码,从而提高性能. (defn factorial [acc n] (if (<= n 1) acc (recur (* ac

  • 我只是想知道这样的函数是否可以递归地完成。我觉得很难,因为它自己叫了两次。 这是我在javascript中的非尾部递归实现。(是的,我知道大多数javascript引擎不支持TCO,但这只是理论上的。)目标是找到给定数组(arr)中具有特定长度(大小)的所有子列表。例如:getSublistsWithFixedSize([1,2,3],2)返回[[1,2]、[1,3]、[2,3]]

  • 我试图了解如何将各种递归函数转换为尾递归。我已经查看了许多将斐波那契和阶乘转换为尾递归的示例,并理解了这些示例,但很难跳到具有某种不同结构的问题。一个例子是: 如何将其转换为尾部递归实现? 我已经看过类似的问题,例如:将正常递归转换为尾部递归,但这些似乎并没有转化为这个问题。