Timeline for Fibonacci sum with memoization

7 events

when toggle format	what		by	license	comment
Jul 3, 2015 at 14:34	comment	added	Michel Billaud		Welll in fact it depends how much newcomers have been exposed to imperative programming. They have to twist their mind first to adapt to iterative logic. And then you ask them to see things recursively.... But simple algebra suffices here : fp(n) = (fib(n), fib(n-1)) = (fib(n-1)+fib(n-2), fib(n-1)) by definition of fib. And thus fp(n) = (x+y, x) where (x,y)=fp(n-1).
Jul 3, 2015 at 14:06	comment	added	Dietr1ch		I know it's the same, but it's definitely harder to understand for newcomers. It's also harder to generalize for other kind of recursions, as you have to state how the previous values will be needed.
Jul 3, 2015 at 8:13	history	edited	Michel Billaud	CC BY-SA 3.0	added 402 characters in body
Jul 3, 2015 at 8:09	comment	added	Michel Billaud		1) This is essentially the same as the classical iterative solution, where the loop is is represented by terminal recursion. But recursion was required, so... 2) Yes it computes an extra value. We can also start from a fictious value fib(-1) = 1. Or add tests. See edit.
Jul 3, 2015 at 0:33	comment	added	Dietr1ch		Are you computing fib(n+1) too? Also, using a loop seems clearer than that if you won't use memoization
Jul 2, 2015 at 15:53	review	First posts
Jul 2, 2015 at 18:00
Jul 2, 2015 at 15:52	history	answered	Michel Billaud	CC BY-SA 3.0