CODEWITHSUNDEEP
ruby
CheeseFry
CheeseFry

Reputation: 1319

Improve recursive methods

This Fibonacci method works with small numbers but the calculations won't work when factored out very far. How can I store what is done at lower level cycles to be reused for later cycles?

def fib(n)
  return 0 if n==0
  return 1 if n==1
  fib(n-1) + fib(n-2)
end

Upvotes: 0

Views: 32

Answers (2)

Jordan Running
Jordan Running

Reputation: 106027

Here's a very basic way to memoize a method like this with a Hash.

@fib_memo = {}

def fib(n)
  return 0 if n == 0
  return 1 if n == 1
  return @fib_memo[n] if @fib_memo.key?(n)
  @fib_memo[n] = fib(n - 1) + fib(n - 2)
end

And it doesn't take much imagination to see how that could be shortened to this:

@fib_memo = { 0 => 0, 1 => 1 }

def fib(n)
  @fib_memo[n] ||= fib(n - 1) + fib(n - 2)
end

Or, as spickermann demonstrates, you can do it all in a Hash's default proc, but that's just showing off. ;)

Upvotes: 3

spickermann
spickermann

Reputation: 106882

You could use a hash to store lower level cycles:

fibonacci = Hash.new { |h, k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }
fibonacci[100]
#=> 354224848179261915075

Upvotes: 2

Related Questions