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

I am learning Scala with the use of Functional Programming in Scala book. Its Github companion notes say that a || go(x) is still a tail call-optimised recursion while 1 go(x) is not. How is that computation different and why can compiler optimise one but not the other?

CodePudding user response：

To explain it more succinctly: for tail recursion, the final operation must be the recursive call.

In 1 go(x) the final operation is the addition.

On the other hand, the || operator is lazy: if a is true the expression a || go(x) just evaluates to true; only if a is false is go(x) evaluated, so go(x) is the final operation, thus it's tail recursive.

CodePudding user response：

Lets say you have following method.

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

Now, this function is not tail recursive. Why ? Lets look at logical execution of sumOfN(3).

While executing this, the stack will look like,

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

Any, recursive method which grows on stack is NOT tail recursive.

But, if we look at the case of that boolean method

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

This will be tail recursive due to branch optimizations for boolean OR. This roughly means that two branches of the stack will be created, the branch with isZeroSomewhere(n - 1) will be evaluated only if (n == 0) is not true ((n == 0) banch will be terminated).

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, you can see the stack size in this case is not growing at all. So, this is tail recursive.

Keep in mind that this branch optimization is done from left to right. So, this following method is NOT tail recursive. It's actually an infinite loop in left branch and will always cause stack overflow.

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