4 ms·
But how to you systematically deduce the tail recursion version? I feel like, in this case, the recursivity in definition of Fibonacci and the recursivity in t
by qsantos 3y ago
But how to you systematically deduce the tail recursion version?
I feel like, in this case, the recursivity in definition of Fibonacci and the recursivity in the tail recursion is just a coincidence, with the second just being a contrived way to write the loop you get after applying dynamic programming and trimming the table to only the last two elements.
- tmoertel 3y ago> But how to you systematically deduce the tail recursion version? Here's one way: https://gist.github.com/tmoertel/5798134 https://gist.github.com/tmoertel/5798134
- qsantos 3y agoThanks! If I understand correctly, you would use that method, while substituting tail recursion in place of the look. However, I feel there is a lot of magic in https://gist.github.com/tmoertel/5798134#file-gistfile1-py-L83-L86 https://gist.github.com/tmoertel/5798134#file-gistfile1-py-L....
- tmoertel 3y agoYeah, deducing the incremental computation to work backwards can take some practice. I take completely different approach to explaining how to do it in https://blog.moertel.com/posts/2013-05-14-recursive-to-iterative-2.html https://blog.moertel.com/posts/2013-05-14-recursive-to-itera....