Computer Science Canada

Memorization - Recursion
Author:  Flikerator [ Wed Mar 28, 2007 11:35 pm ]
Post subject:  Memorization - Recursion
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)
Author:  ericfourfour [ Wed Mar 28, 2007 11:50 pm ]
Post subject:  RE:Memorization - Recursion
I remember reading that the correct term is memoization (without the "r").

Otherwise, pretty cool. Smile
Author:  Cervantes [ Thu Mar 29, 2007 10:09 am ]
Post subject:  RE:Memorization - Recursion
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)}
Author:  BenLi [ Thu Mar 29, 2007 11:50 am ]
Post subject:  RE:Memorization - Recursion
isn't this what "dynamic programming" talks about

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy