# Tail call optimization

Hi
I am new to crystal and trying small programming exercises to understand the language.
This exercise is about use tail recursion to implement Fibonacci series.

``````def fib(n, x = 1_i64, y = 1_i64)
n <= 1 ? y : fib(n - 1, y, x + y)
end

puts fib(46)
``````

it works, but it can be called wrong, like so `fib(42, 2, 4)`

what i want to be able to do is something like

``````def fib(n)
def fib_impl(n, x = 1_i64, y = 1_i64)
n <= 1 ? y : fib_impl(n - 1, y, x + y)
end
fib_impl(n)
end

puts fib(46)
``````

How can i achieve something like this?
Thanks

``````def fib(n)
fib(n, 1, 1)
end

private def fib(n, a, b)
n <= 1 ? b : fib(n - 1, b, a + b)
end
``````
``````def fib(n : Int64)
fib = nil
fib = ->(n : Int64, a : Int64, b : Int64) { n <= 1 ? b : fib.not_nil!.call(n - 1, b, a + b) }
fib.not_nil!.call(n, 1i64, 1i64)
end
``````

Thank you!
I tried the private implementation approach.
What i really wanted was your second solution, a way to use procs.

I do prefer the private approach personally, I think it’s a little cleaner :)

1 Like

Just exploring the crystal toolbox.
I wanted to learn how to call a proc recursively. thanks for showing me the `fib = nil` trick

Admittedly it shouldn’t be necessary. There’s nothing wrong with a proc capturing a local variable it’s being assigned to.

@radha I don’t think that llvm’s tail call optimization explained in http://llvm.org/docs/CodeGenerator.html#tail-call-optimization will be applied. We don’t meet those requirements.

If you want to see how the call is emitted in llvm, a slightly modified version of the program that can be compiled without the std-lib prelude can be compiled without debug information and with either `--emit=llvm-ir` or `DUMP=1`

``````def fib(n, x = 1_i64, y = 1_i64)
n <= 1 ? y : fib(n &- 1, y, x &+ y)
end

fib(46)
``````

`\$ DUMP=1 crystal build --prelude=empty --no-debug foo.cr`

``````; Function Attrs: uwtable
define i64 @"*fib<Int32, Int64, Int64>:Int64"(i32 %n, i64 %x, i64 %y) #0 {
entry:
%0 = icmp sle i32 %n, 1
br i1 %0, label %then, label %else

then:                                             ; preds = %entry
br label %exit

else:                                             ; preds = %entry
%1 = sub i32 %n, 1
%2 = add i64 %x, %y
%3 = call i64 @"*fib<Int32, Int64, Int64>:Int64"(i32 %1, i64 %y, i64 %2)
br label %exit

exit:                                             ; preds = %else, %then
%4 = phi i64 [ %y, %then ], [ %3, %else ]
ret i64 %4
}
``````

I actually was curious about this exact question the other day! For a simple Fibonacci implementation like the first one I had above (I didn’t check for the second one), in `--release` mode LLVM does actually turn it into tail calls!

2 Likes

I am sorry, reading llvm-ir is out of my league, but i can confirm optimizations are applied in release builds.

``````> time ./fibonacci
2971215073

________________________________________________________
Executed in   10.56 secs   fish           external
usr time   10.56 secs  825.00 micros   10.56 secs
sys time    0.01 secs  189.00 micros    0.01 secs
``````
``````> time ./fibonaccitail
2971215073

________________________________________________________
Executed in    9.61 millis    fish           external
usr time    0.59 millis  589.00 micros    0.00 millis
sys time   10.35 millis  141.00 micros   10.21 millis
``````

maybe because i built crystal from source against llvm 10?

``````> crystal --version
Crystal 0.35.0-dev [9057e8d80] (2020-06-08)

LLVM: 10.0.0
Default target: x86_64-pc-linux-gnu
``````

please let me know if i can provide any more details

1 Like