Hacker News Reader

Comment by thefaux | Hacker News Reader

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.

View on HN

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.

> But how to you systematically deduce the tail recursion version?

Here's one way: https://gist.github.com/tmoertel/5798134

Thanks! 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-L....

Yeah, 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-itera....

Memoization generalizes much better than accumulator parameters.

Because it's a good example to teach dynamic programming?

I 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.

Reply on news.ycombinator.com