Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
LT = -1
EQ = 0
GT = 1
def fib n
case n <=> 1
when LT then
0
when EQ then
1
when GT then
fib(n-1) + fib(n-2)
end
end
def fib_loop n
stk = []
stk.push [true, n]
n = nil
a = nil
loop {
flg, a = stk.pop
if flg then
case a <=> 1
when LT then
stk.push [false, 0]
when EQ then
stk.push [false, 1]
when GT then
stk.push [true, a-2]
stk.push [true, a-1]
end
else
break if stk.empty?
flg2, a2 = stk.pop
if flg2 then
stk.push [false, a]
stk.push [true, a2]
else
stk.push [false, a+a2]
end
end
}
return a
end
(0..10).each {|n|
p fib n
}
puts "===="
(0..10).each {|n|
p fib_loop n
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.