Memorization - Recursion

[Flikerator]

I was brushing up a bit on my recursion and I thought that the Fibinacci sequence was rather slow when done recursively (in some methods). So I thought that it was kind of silly to add so many one values together (see first code block for original recursive sequence). So I figured that the program should memorize all of the already learned values. So I wrote a basic Fib Sequence with the memorization (Obviously not the best). Its a little redundant, but the theory of memorizing answers could make questions very efficient. Try it out for other problems and see if you can optimize them using this method. Let me know your results.

WARNING: These were done without real notary for "good code" so it is sloppy, do not try to copy the style. Always have meaningful variable names and include rems.

Original Sequence

code:

function Fib (n : int) : real     if n = 1 or n = 0 then         result 1     end if     result Fib (n - 1) + Fib (n - 2) end Fib var t : int := 100 for i : 0 .. t - 1     put Fib (i), ", " .. end for put Fib (t)

Memorization

code:

var Mem : array 0 .. 100000 of real var Meme : array 0 .. upper (Mem) of boolean for i : 0 .. upper (Meme)     Meme (i) := false end for function Fib (n : int) : real     if Meme (n) then         result Mem (n)     elsif n = 1 or n = 0 then         result 1     end if     var ha := Fib (n - 1) + Fib (n - 2)     Meme (n) := true     Mem (n) := ha     result ha end Fib var t : int := 100 for i : 0 .. t - 1     put Fib (i), ", " .. end for put Fib (t)

[ericfourfour]

I remember reading that the correct term is memoization (without the "r").

Otherwise, pretty cool.

[Cervantes]

I was doing some neat calculus the other day, exploring the power series expansion of f(x) = x/(1-x-x^2). It led to discovering an explicit formula for the n'th fibonacci number, in terms of the golden ratio.

Ruby:

Phi = (1 + 5**0.5) / 2.0 def fib(n)   ((if n % 2 == 0       Phi ** n - 1.0 / Phi ** n     else       Phi ** n + 1.0 / Phi ** n     end) / 5 ** 0.5).round end 1.upto(40) {|i| puts fib(i)}

[BenLi]

isn't this what "dynamic programming" talks about