Built recursive and iterative methods to return the Fibonacci sequence up to a given n, then ran benchmarks to test performance
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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