Stack overflow in Fibonacci tail recursion

[mabDc]

Stack Overflow when calc Fibonacci tail recursion

fun fib(n, a, b){
    return n == 1 ? a : fib(n-1, a + b, a)
}
fun main(){
    print(fib(1234, 1, 1))
}

[hythl0day]

I tried my self with this version:

      fun fib(n0, n1, c){
        if (c == 0) {
          return n0
        }
        else if (c == 1) {
          return n1
        }
        return fib(n1, n0 + n1, c - 1)
      }

      fun main(){
          print(fib(0, 1, 1020))
      }

I can go as far as 1020, on 1021, it returned a negative number I don't know why ,and beyond that is stack overflow...

It might be because the bytecode version interpreter right now hetu use doesn't support BigInt like Dart does.

Or it is because there are some other limit this recursion touched...

[hythl0day]

And the result is wrong when the nth is higher, I'm still testing.

[hythl0day]

after fib(92), the result reached the limit of int64(which is the limit of the current bytecode interpreter).

however why the stack overflowed after 1020 is still unclear

[rockingdice]

It's quite near 1024.
Maybe it's a limitation set by the OS or Dart VM.

[mabDc]

@rockingdice let's be close to the topic: tail recursion should not cause stack overflow that make sense

[rockingdice]

@mabDc Sure, so this could be a bug.