Is this definition of tail recursive fibonacci function tail recursive?
I saw around the following F # definition of the continuation-erase fibonacci function, which was always thought to be tail-recursive:
let fib k = let rec fib' k cont = match k with | 0 | 1 -> cont 1 | k -> fib' (k-1) (fun a -> fib' (k-2) (fun b -> cont (a+b))) fib' k id
When testing equivalent code in Scala, I used the existing @tailrec and was caught off guard when the Scala compiler informed me that recursive calls are NOT in the tail:
def fib(k: Int): Int = {
@tailrec def go(k: Int, cont: Int => Int): Int = {
if (k == 0 || k == 1) cont(1)
else go(k-1, { a => go(k-2, { b => cont(a+b) })})
}
go(k, { x => x })
}
I believe my Scala implementation is equivalent to F # one, so I'm left wondering why the function is not recursive?
source to share
The second call go
on line 4 is not in the tail position, it is wrapped inside an anonymous function. (It is in the tail position for this function, but not for itself go
.)
For the continuation style, you need correct tail calls, which Scala unfortunately does not. (In order to provide PTC to the JVM, you need to manage your own stack, not use the JVM call stack, which breaks compatibility with other languages, however, compatibility is the main design goal of Scala.)
source to share
JVM support for tail call elimination is limited.
I can't talk about the F # implementation, but in scala you have nested calls, so it is not in the tail position. The easiest way to think about this is in terms of stacks: is there any other information that the stack needs to "remember" when making a recursive call?
In the case of nested calls, there is obviously a call, since the internal call must be completed before the computation "returns" and completes the external call.
Fib can be recursively defined as follows:
def fib(k:Int) = {
@tailrec
def go(k:Int, p:Int, c:Int) : Int = {
if(k == 0) p
else { go(k-1, c p+c) }
}
go(k,0 1)
}
source to share
Unfortunately the JVM does not yet support tail call optimization (?) (In fairness, it can sometimes optimize some calls). Scala implements tail-recursion optimization by transforming the program (each tail-recursion function is equivalent to a loop). This is usually sufficient for simple recursive functions, but full optimization is required for mutual recursion or continuing traversal.
This is really problematic when using advanced functional templates like CPS or monadic style. To avoid stack bloat you need to use Trampolines . It works, but it is not as convenient and efficient as proper tail call optimization. Edward Kemmet 's comments on this issue are good read.
source to share