首页 文章

在Scala中编写阶乘尾递归函数

提问于
浏览 次
0

我试图以下面的方式编写尾递归函数，但编译器抛出错误：

方法适用的参数太多：（v1：Int）特征中的Int函数1否则因子（x-1，x * acc）

我曾尝试用Function2替换Function1并赋予Function2 [Int，Int，Int] = new Function2 [Int，Int，Int]

但它仍然给我带来了同样的错误 . 有人可以指出我哪里出错了吗？

import scala.annotation.tailrec
var factorial: Function1[Int, Int] = new Function1[Int, Int] {
    @tailrec override def apply (x:Int, acc:Int=1): Int = {
        if (x<=1) acc
        else factorial(x-1, x*acc)
    }
}

factorial(5)
scala function recursion functional-programming tail-recursion

4 回答

  • 0

    当你通过两个时， Function1 里面的 apply 必须只带一个参数 .

    您可以按如下方式重写它：

    var factorial: Function1[Int, Int] = new Function1[Int, Int] {
  def apply (x:Int): Int = {
    @tailrec def loop(x: Int, acc: Int = 1): Int = {
      if (x<=1) acc
      else loop(x-1, x*acc)
    }
    loop(x)
  }
}
    回复于
  • 2

    Function1 表示具有单个参数的函数（第二个用于输出）

    因此，您需要使用单个参数定义apply方法，然后在其中使用嵌套函数执行递归：

    import scala.annotation.tailrec
  var factorial: Function1[Int, Int] = new Function1[Int, Int] {

    override def apply(x: Int): Int = {
      @tailrec
      def go (x: Int, acc: Int = 1) : Int = {
        if (x<=1) acc
        else go(x-1, x*acc)
      }
      go(x)
    }
  }
  factorial(5)
    回复于
  • 0

    Function2采用3种类型参数 . 最后一个是输出类型 .

    Scala REPL

    scala> :paste
// Entering paste mode (ctrl-D to finish)

 val fac: Function2[Int, Int, Int] = new Function2[Int, Int, Int] {
    def apply(v1: Int, v2: Int): Int = if (v1 == 1) v2 else apply(v1 - 1, v1 * v2)
  }


// Exiting paste mode, now interpreting.

fac: (Int, Int) => Int = <function2>

scala> fac(5, 1)
res1: Int = 120

    你可以使用 => 来代替使用interface / trait Function2的语法糖（scala中的函数语法） .

    scala> :paste
// Entering paste mode (ctrl-D to finish)

val fac: (Int, Int) => Int = (acc, c) => if (c == 1) acc else fac(acc * c, c - 1)


// Exiting paste mode, now interpreting.

fac: (Int, Int) => Int = $$Lambda$1092/1204822967@5c83ae01

scala> fac(1, 5)
res0: Int = 120
    回复于
  • 2

    你可以看到这个answer这是你问题的一个很好的解释 . 你的问题是你试图将 apply 定义为tail-recursive但你没有在递归调用中调用自己，而是调用 factorial .

    首先，你应该使用 Function2 作为你的类型同样适用：

    import scala.annotation.tailrec

import scala.annotation.tailrec
var factorial: Function2[Int, Int, Int] = new Function2[Int, Int, Int] {
    @tailrec override def apply (x:Int, acc:Int=1): Int = {
      if (x<=1) acc
      else apply(x-1, x * acc)
    }
}

    然后，如果你得到错误 could not optimize @tailrec annotated method apply: it contains a recursive call targeting a supertype ，你应该递归调用 apply ，因为函数是尾递归的，它总是应该被称为最后一个语句 .

    scala> factorial(5, 1)
res3: Int = 120
    回复于

相关问题