Skip to content

Instantly share code, notes, and snippets.

@Bablzz
Last active December 13, 2019 13:32
Show Gist options
  • Save Bablzz/6df80e46a7888ec87981ba11da5ab952 to your computer and use it in GitHub Desktop.
Save Bablzz/6df80e46a7888ec87981ba11da5ab952 to your computer and use it in GitHub Desktop.
Fibonacci with memoization
memo = Hash.new(0)
def fib_rec (number, memo)
if number == 0
return number
elsif (number == 1) || (number == 2)
return 1
end
if (memo.has_key?(number))
return memo[number]
end
puts "computing #{number}"
result = fib_rec(number - 1, memo) + fib_rec(number - 2, memo)
memo.store(number, result)
return result
end
puts fib_rec(7, memo)
# computing 7
# computing 6
# computing 5
# computing 4
# computing 3
# => 13
# in the same time without memoization
# computing 7
# computing 6
# computing 5
# computing 4
# computing 3
# computing 3
# computing 4
# computing 3
# computing 5
# computing 4
# computing 3
# computing 3
# =>13
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment