4 ms·
I don't understand why you would use memoization for fibonacci ever and hence its relevance for dynamic programming. It can be solved with a tail recursive func
by thefaux 3y ago
I don't understand why you would use memoization for fibonacci ever and hence its relevance for dynamic programming. It can be solved with a tail recursive function with three input parameters. Solution left to the reader as an exercise.
- peterfirefly 3y agoMemoization generalizes much better than accumulator parameters.
- TotoHorner 3y agoBecause it's a good example to teach dynamic programming?
- deleted 3y ago[deleted]
- qsantos 3y agoBut 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....
- aetimmes 3y agoI don't understand why you would use tail recursive functions for fibonacci ever and hence its relevance for dynamic programming. It can be solved with a simple equation with one input parameter. Solution left to OP as an exercise.