4 ms·
TCO works if you write it properly: fib(0) -> 0; fib(1) -> 1; fib(N) when is_integer(N), N >= 2 -> fib(N, 2, fib(0) + fib(1), fib(1)).
by toast0 5y ago
TCO works if you write it properly:
fib(0) -> 0;
fib(1) -> 1;
fib(N) when is_integer(N), N >= 2
-> fib(N, 2, fib(0) + fib(1), fib(1)).
fib(N, N, Current, _Last) -> Current;
fib(N, I, Current, Last) ->
fib(N, I + 1, Current + Last, Current).
But if you write the same thing in C, it'll still blow your stack (of course, you can transform it into a loop), and you'll need to use bigints somehow, these numbers get big fast. It does use a lot of cpu though; takes not quite 10 seconds to run fib(1000000) on my Pentium G2020. Closed form is certainly faster, although I didn't benchmark it :D
- toast0 5y agoToo late to edit, but if you do fib(N) when ... -> fib(N - 2, fib(0) + fib(1), fib(1)). Then you can check for N = 0 to return Current, and do N - 1 in the iteration. One less value to pass in each recursion should make it faster, and it's less to think about.