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

Question

我正在尝试用以下方式编写尾递归函数，但编译器抛出错误：

方法应用的参数过多：特征 Function1 中的 (v1: Int)Int 否则阶乘（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)

Answer 1

`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

您可以使用语法糖（scala 中的函数语法使用 =>）而不是使用 interface/trait Function2。

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 = $$Lambda92/1204822967@5c83ae01

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

Answer 2

你 apply 里面 Function1 必须只带一个参数，当你传递两个参数时。

您可以改写如下：

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)
  }
}

Answer 3

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)

Answer 4

您可以看到这个 answer，它很好地解释了您的问题。您的问题是 您试图将 apply 定义为尾递归，但您没有在递归调用中调用自身 ，而是调用 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

Answer 5

或者，如果你喜欢一些语法糖，你可以这样写：

  val f: (Int) => BigInt = (x) => {
    if (x <= 1) 1
    else x * f(x - 1)
  }

  println(f(30))

或真正的尾递归函数：

  val f: (Int) => BigInt = (x) => {

    @tailrec
    def helper(x: Int, acc: BigInt = 1): BigInt = {
      if (x <= 1) acc
      else helper(x - 1, x * acc)
    }

    helper(x)
  }

  println(f(30))

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

Writing a factorial tail recursive function in Scala

scala

function

recursion

functional-programming

tail-recursion

`Function2` 接受 3 个类型参数。最后一个是输出类型。

Scala REPL

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

Writing a factorial tail recursive function in Scala

scala

function

recursion

functional-programming

tail-recursion

Function2 接受 3 个类型参数。最后一个是输出类型。

Scala REPL

`Function2` 接受 3 个类型参数。最后一个是输出类型。