4 ms·
Fibonacci (as implemented here) shouldn't be aided by any TCO. The execution trace will be something like: F(N) -- F(N-2) ... | F(N-1) -- F(N-3) ...
by Jtsummers 8y ago
Fibonacci (as implemented here) shouldn't be aided by any TCO. The execution trace will be something like:
F(N) -- F(N-2) ...
|
F(N-1) -- F(N-3) ...
|
F(N-2) -- F(N-4) ...
But each has to return to the original caller because a summation still has to happen. The actual tail call is to the +/2 function.
F(N) can't complete until F(N-1) and F(N-2) have completed so it can sum up the values. If you pass the earlier computation, F(N-1), down to F(N-2) as a second parameter, you could get a tail call on the last part.
fib(0, Val) -> Val + 1;
fib(1, Val) -> Val + 1;
fib(N, Val) ->
T = fib(N-1,Val),
fib(N-2,T).
(I think I wrote that correctly, can't test here.)
But that's a non-obvious tranformation. I really would like to see the compiler that recognized that this was a valid (computational) equivalent to the original.
- jcranmer 8y agoBut it is aided by tail-call optimization. Suppose you have a function as follows: int foo(int x) { if (test(x)) return C; return evaluate(x) + foo(adjust(x)); } I can turn that function into: int foo(int x) { int accum = C; for ( ; !test(x); x = adjust(x)) { accum += evaluate(x); } return accum; } In the case of fibonacci, that equates to: int fib(int x) { int accum = 1; for (; x > 1; x -= 2) { accum += fib(x - 1); } return accum; } We still turned the recursive call (or one of them, at least), into a while loop. And this idiom is recognized by both gcc and llvm. In fact. llvm has a test that specifically makes sure fib is transformed as thus: https://github.com/llvm-mirror/llvm/blob/30fa583f8430bfc7935bf66b1aab50cfefd6cc11/test/Transforms/TailCallElim/accum_recursion.ll https://github.com/llvm-mirror/llvm/blob/30fa583f8430bfc7935...