混淆scala递归中的调用序列

Question

我正在尝试跟踪 Scala 中的递归处理。以下是代码示例：

def factorial(n: Int): Int =
  if (n <= 1) 1
  else {
    println("Computing factorial of " + n + " - I first need factorial of " + (n-1))
    def result = n * factorial(n - 1)
    println("Computed factorial of " + n)
    result
  }
println(factorial(3))

输出如下：

Computing factorial of 3 - I first need factorial of 2
Computed factorial of 3
Computing factorial of 2 - I first need factorial of 1
Computed factorial of 2
6

这很奇怪，因为无法在参数 n-1 之前计算参数 n。我宁愿期待以下输出：

Computing factorial of 3 - I first need factorial of 2
Computing factorial of 2 - I first need factorial of 1
Computed factorial of 2
Computed factorial of 3
6

这种行为的原因是什么？

Answer 1

您预期的行为将适用于以下程序：

def factorial(n: Int): Int =
  if (n <= 1) 1
  else {
    println("Computing factorial of " + n + " - I first need factorial of " + (n-1))
    val result = n * factorial(n - 1) // here is the difference def -> val
    println("Computed factorial of " + n)
    result
  }
println(factorial(3))

Beetween 打印您正在定义一个函数：

def result = n * factorial(n - 1)

但这并不意味着您正在调用它。函数 (def) 被延迟求值，而值 (val) - 被急切求值。这只是一个定义。之后您继续第二个 println 和 result，其中返回值 result 函数被调用，产生 n - 1.

的打印语句

Answer 2

递归很酷，尾递归更好。

def factorial(n: Long): Long = {
  @annotation.tailrec
  def go(fact: Long, n: Long): Long = {
    if (n < 2) fact * n
    else go(fact * n, n - 1)
  }
  if (n == 0) 1 else go(1, n)
}

混淆scala递归中的调用序列

Confusing call sequence in scala recursion

algorithm

scala

recursion

functional-programming

lazy-evaluation

递归很酷，尾递归更好。