Skip to content

Instantly share code, notes, and snippets.

@amyhenning
Last active September 1, 2018 00:56
Show Gist options
  • Save amyhenning/ea6acb8744c60059093c81a10ca8fbb4 to your computer and use it in GitHub Desktop.
Save amyhenning/ea6acb8744c60059093c81a10ca8fbb4 to your computer and use it in GitHub Desktop.
Built recursive and iterative methods to return the Fibonacci sequence up to a given n, then ran benchmarks to test performance
def recursive_fib(n)
# sets the first two values (0 and 1) by default
if n < 2
return n
# if n is greater than or equal to 2, the nth number in the fibonacci
# is the sum of the function called on n-1 and the function called on
# n-2
else
return recursive_fib(n-1) + recursive_fib(n-2)
end
end
def iterative_fib(n)
# set initial values of the first two fibonacci numbers (?)
a = 0
b = 1
# loop n times
n.times do
# set a placeholder to be equal to a (in the base case, 0)
# in the second loop, it will equal 1
# in the third loop, placeholder = 1
# in the fourth loop, placeholder = 2
placeholder = a
# set a to equal b (in the base case, a will now equal 1)
# in the second loop, a will now equal 1
# in the third loop, a = 2
# in the fourth loop, a = 3
a = b
# set b to equal placeholder + b (1 + 0)
# in the second loop, it will be 1 + 1 = 2
# in the third loop, b = 1 + 2 = 3
# in the third loop, b = 2 + 3 = 5
b = placeholder + b
end
# in the first loop, it'll return 1
# in the second loop, it'll return 1
# in the third loop, it'll return 2
# in the fourth loop, it'll return 3
return a
end
puts recursive_fib(4)
puts iterative_fib(4)
require 'benchmark'
num = 45
Benchmark.bm do |x|
x.report('recursive_fib') { recursive_fib(num) }
x.report('iterative_fib') { iterative_fib(num) }
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment