为什么a || go(x)是尾调用，而1 + go(x)不是?

Question

我正在使用Scala书中的函数式编程学习Scala。它的Github同伴笔记说，a || go(x)仍然是尾部调用优化的递归，而1 + go(x)不是。计算有什么不同，为什么编译器可以优化一个而不是另一个?

Answer 1

更简洁地解释一下:对于尾部递归，最后的操作必须是递归调用。

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

另一方面，||运算符是惰性的:如果a为真，则表达式a || go(x)的计算结果为真;只有当a为假时，go(x)才会被求值，因此go(x)是最后的操作，因此它是尾部递归的。

Answer 2

假设你有以下方法:

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

6

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

但是，如果我们看看布尔方法

的情况

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

As，您可以看到在这种情况下堆栈大小根本没有增长。这是尾部递归

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

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