3 ms·
Calculating the nth member of the Fibonacci sequence is a commonly-used example of where a naive, literal-translation-to-code recursive solution is inordinately
by mannykannot 6y ago
Calculating the nth member of the Fibonacci sequence is a commonly-used example of where a naive, literal-translation-to-code recursive solution is inordinately costly - so now I am trying to figure out if the method described in this article, applied mechanically to the literal recursive solution, results in an efficient solution, or merely tranfers the data complexity of its stack frames to the heap (I think you are suggesting it would result in the latter, which seems plausible to me.)
- jpcooper 6y agoMight be worth checking https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ https://www.geeksforgeeks.org/program-for-nth-fibonacci-numb....
- ufo 6y agoThe mechanical transformation described in the article does not change the asymptotic complexity of the program. It just changes it from using an implicit (recursion) stack, to using an explicit stack. The neat thing about that transformation, in my opinion, is that it works even for complicated algorithms. Sometimes you really do need to rewrite something to use an explicit stack, and that can be quite tricky to get right!
- mannykannot 6y agoPoint taken - thanks!