标签: tail-recursion

我想让这个函数递归，但我不知道从哪里开始。

let rec rlist r n =
    if n < 1 then []
    else Random.int r :: rlist r (n-1);;

let rec divide = function
    h1::h2::t -> let t1,t2 = divide t in
        h1::t1, h2::t2
    | l -> l,[];;

let rec merge ord (l1,l2) = match l1,l2 with
    [],l | l,[] -> l
    | h1::t1,h2::t2 -> if ord h1 h2
        then h1::merge ord (t1,l2)
        else h2::merge ord (l1,t2);;

有没有办法测试一个函数是否是递归的？

如果 i 是偶数则 bar 调用 bar(i/2)，否则调用 bar(3*i + 1)，则递归函数 bar 将进行尾递归。

const int bar(const int i) 
{
  if (i < 2) return i;
  return i % 2 ? bar(i/2) : bar(3*i + 1);
}

但是，如果 bar 调用 bar 或 foo，而后者具有与 bar 完全不同的局部变量集，该怎么办？

const int bar(const int i) 
{
  if (i < 2) return i;
  return i % 2 ? bar(i/2) : foo(3*i + 1);
  // where foo is very complicated recursive call that has 
  // 11 different user-defined/primitive type of …

我在Kotlin写了这个递归函数:

fun recursive(target: String, population: Population, debugFun: (String) -> Unit) : Population {
    if (population.solution(target).toString() == target) {
        return population
    }
    debugFun.invoke(population.solution(target).toString())
    return recursive(target, population.evolve(target), debugFun)
}

它将运行不确定的次数(因为我使用随机性来收敛进化算法中的解决方案).我经常得到堆栈溢出.Kotlin/JVM语言的最大堆栈深度是多少？我应该非递归地编写函数吗？

我认为下面的阶乘函数是尾递归的，当我测试它时，它可以正常工作到 10 并且在 20 时变得奇怪（负输出），当我插入 100 时，答案是 0：

def factorial(n: Int, m: Int = 1): Int = 
    if (n == 0) m else fact(n-1, m * n)

但是当我把@tailrec放在它上面时，我收到以下错误：

error: not found: type tailrec

我不明白为什么这个函数不是尾递归的。堆栈递归阶乘函数是：

def factorial(n: Int): Int = 
    if (n == 0) 1 else n * factorial(n-1)

上面的函数在每次递归调用时修改else 之后的外部表达式。而第一个函数只修改函数内部的内容。现在，要创建递归阶乘函数，他们所做的是在函数内部创建一个函数。但是，是否可以仅使用此问题中的第一个函数的主体来创建递归阶乘函数？

另外，前一个函数中的“m”是变量吗？

编辑：现在按照答案中的建议进行操作后，如果函数不是尾递归的，我会收到错误消息：

error: could not optimize @tailrec annotated method factorial: it contains a recursive call not in tail position

下面，sumAllIf是尾递归，sumAllFold不是。但是，sumAllIf实际上具有相同的实现。这是 Scala 编译器（或 Scala 库）的缺点，还是我忽略了某些东西？

def maybeNext(in: Int): Option[Int] = if in < 10 then Some(in + 1) else None

// The Scala library implements Option.fold like this:
// @inline final def fold[B](ifEmpty: => B)(f: A => B): B =
//   if (isEmpty) ifEmpty else f(this.get)
@annotation.tailrec
def sumAllIf(current: Int, until: Int, sum: Int): Int =
  val nextOption = maybeNext(current)
  if (nextOption.isEmpty) sum else sumAllIf(nextOption.get, until, sum + nextOption.get)

// However, with Scala 3.1.0 …

我无法理解尾递归的概念，我想为类似斐波那契的函数制作一个尾递归版本， p1= n-3 ， p2= n-2 ， fx( p1 ) + fx( p2 ) 到目前为止是我想出的，但我不知道这是否是正确的方法，有人可以帮助我，任何帮助将不胜感激 p1= n-3 , p2= n-2 Long doCalc( long n ) { return n = = 0 ? 0 : ( n == 1 ? 1 : ( n == 2 ? 1 : (make( p1 ) + make( p2 )) ) ); }

代码输出正确的结果

但是当我实现尾递归时，我的方法是分裂和征服，但它不起作用并且输出是错误的

Long factor3(Long n, Long a)
{
    if( n == 0){
        return 0l;
    } else if( n == 1 || n …

除典型之外,还有哪些其他与语言无关的设计递归函数的方法:

if (counter < 1) 
    return output;
else
   callSelf(); 

还有其他方法吗？每当查看示例时,我总会看到上面代码的一个版本.

谢谢!:)

我有几行scala代码定义了一个函数A,它重复调用functionB直到n为零(函数B n次).每次迭代n减少1,并且如上所述更新x0.

def functionA(c: Double, x0: Double, n: Int): Double = {
    require(x0>0) //This is a must
    while(n>0){
       x0=functionB(c, x0) //functionB predefined
       n--
    }
   x0
}

问题在于变量似乎无法像线条那样改变

x0=functionB(c, x0)
n--

正在返回错误.如果当前结构没有改变并且总行数保持不变,我该如何正确地写行？

我有一些递归代码我想重构使用Enumerator的尾递归,我可以简化这种递归看起来像这样,请忽略这个功能想要实现的功能.

@tailrec
def doStuff: List[Int] => Int = {
      case Nil => 0
      case x :: xs => doStuff(xs)
    }

如果我摆脱tailrec注释,它工作正常,结构看起来像这个doStuff(doStuff(doStuff(..))).它将具有stackoverflow异常.

那么如果它是一个函数,我怎么能使它递归递归

我有Merge Sort的这种实现:

import scala.annotation.tailrec

object MergeSort {
  def sortBy[T]: ((T, T) => Int) => Seq[T] => Seq[T] = comparator => seqToSort => {
    @tailrec
    def merge(xs : Seq[T], ys : Seq[T], accum : Seq[T] = Seq()) : Seq[T] = (xs, ys) match {
      case (Seq(), _) => ys ++ accum
      case (_, Seq()) => xs ++ accum
      case (x::rx, y::ry) =>
        if(comparator(x, y) < 0)
          merge(xs, ry, y +: accum)
        else
          merge(rx, ys, x +: accum)
    }

    @tailrec
    // Problem …