为什么是|| go(x) 是尾调用 ins 调用而 1 + go(x) 不是？

Question

我正在使用 Functional Programming in Scala 书学习 Scala。它的 Github 伴随说明说 a || go(x) 仍然是尾调用优化的递归，而 1 + go(x) 不是。这种计算有何不同？为什么编译器可以优化一个而不是另一个？

Answer 1

假设您有以下方法。

def sumOfN(n: Int): Int = 
  if (n <= 0)
    0
  else
    n + sumOfN(n - 1)

现在，这个函数不是尾递归的。为什么？让我们看看 sumOfN(3).

的逻辑执行

执行此操作时，堆栈将如下所示，

sumOfN(3)

3 + sumOfN(2)

sumOfN(2)
3 + sumOfN(2)

2 + sumOfN(1)
3 + sumOfN(2)

sumOfN(1)
2 + sumOfN(1)
3 + sumOfN(2)

1 + sumOfN(0)
2 + sumOfN(1)
3 + sumOfN(2)

sumOfN(0)
1 + sumOfN(0)
2 + sumOfN(1)
3 + sumOfN(2)

0
1 + sumOfN(0)
2 + sumOfN(1)
3 + sumOfN(2)

1 + 0
2 + sumOfN(1)
3 + sumOfN(2)

1
2 + sumOfN(1)
3 + sumOfN(2)

2 + 1
3 + sumOfN(2)

3
3 + sumOfN(2)

3 + 3

任何在堆栈上增长的递归方法都不是尾递归的。

但是，如果我们看一下那个布尔方法的情况

def isZeroSomewhere(n: Int): Boolean = 
  (n == 0) ||  isZeroSomewhere(n - 1)

由于 boolean OR 的分支优化，这将是尾递归的。这大致意味着将创建堆栈的两个分支，仅当 (n == 0) 为 not true 时才会评估具有 isZeroSomewhere(n - 1) 的分支（(n == 0) 分支将被终止）。

isZeroSomewhere(3)

// branch 1              // branch2
(3 == 0)                 isZeroSomewhere(2)
// false,terminate       // needs further evaluation

isZeroSomewhere(2)

// branch 1              // branch2
(2 == 0)                 isZeroSomewhere(1)
// false,terminate       // needs further evaluation

isZeroSomewhere(1)

// branch 1              // branch2
(1 == 0)                 isZeroSomewhere(0)
// false,terminate       // needs further evaluation

isZeroSomewhere(0)

// branch 1              // branch2
(0 == 0)                 isZeroSomewhere(-1)
// true                  // the other branch is true, terminate

因为，您可以看到本例中的堆栈大小根本没有增长。所以，这是尾递归。

请记住，此分支优化是从左到右完成的。所以，下面这个方法不是尾递归的。它实际上是左分支的无限循环，并且总是会导致堆栈溢出。

def isZeroSomewhere(n: Int): Boolean =
  isZeroSomewhere(n - 1) || (n == 0)

Answer 2

解释得更简洁：对于尾递归，最后的操作一定是递归调用。

在1 + go(x)中最后的操作是加法。

另一方面，|| 运算符是惰性的：如果 a 为真，则表达式 a || go(x) 的计算结果为真；否则仅当 a 为 false 时才对 go(x) 进行评估，因此 go(x) 是最终操作，因此它是尾递归的。

Why is a || go(x) a tail call ins call and 1 + go(x) is not?