3 ms·
Wouldn't you get the same result using memoization idiomatic syntaxes? k[v] ||= k[v-1] + k[v-2]
by psychoslave 3y ago
Wouldn't you get the same result using memoization idiomatic syntaxes?
k[v] ||= k[v-1] + k[v-2]
- devoutsalsa 3y agoThat was the first thing I tried, but it blew the stack :) You can still blow the stack if you pick a number that's too high, like k[20000] or something. But if you pick a lower number & cache that, then you can (eventually) call a higher number without blowing the stack. This recursive approach is a horribly inefficient algorithm anyway, so I don't think it's worth optimizing :)
- vidarh 3y agoNo, because that is equivalent to k[v] || (k[v] = k[v-1] + k[v-2]) And that first k[v] (unlike k.key?(v)) will trigger the Hash.new block again, so it'll recurse until it runs out of stack. But neither check is necessary, because the Hash.new block will only ever get called if k.key?(v) is false. If you want a more compact version, you could do: fib = Hash.new do |k,v| next 1 if v == 0 || v == 1 k[v] = k[v-1] + k[v-2] end