Re:Why is learning functional programming so damned hard? (2...
by toast0 on Monday August 16, 2021 @12:43AM
(#28194998)
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
Re:Why is learning functional programming so damned hard? (2...
by toast0 on Monday August 16, 2021 @03:17AM
(#28195700)
Too 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.
And if you're using memoization, you could do that in C.
And, even a naive implementation wouldn't blow your stack, it would just melt your CPU into a puddle of slag.
Or am I missing something here?