Created
January 20, 2016 06:46
-
-
Save spilledmilk/d5b14b247cfced4753bb to your computer and use it in GitHub Desktop.
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) | |
n <= 1 ? n : recursive_fib(n - 1) + recursive_fib(n - 2) | |
end | |
# recursive_fib | |
# the method takes argument n (digit desired of fibonacci sequence) | |
# first checks if n equals either base case (0 and 1), if so, returns n | |
# if not, sum the two previous digits of n; this will result in two recursive actions, of which | |
# will continue until each recursion (and their subsequent recursions) reaches the base cases (0 and 1) | |
# and returns the [total] sum (the nth digit of the sequence) | |
def iterative_fib(n) | |
fib_seq = [] | |
(0..n).each do |num| | |
if num <= 1 | |
fib_seq << num | |
# p "less than one seq = #{fib_seq}" | |
else | |
# p "n = #{n} // seq(-1) = #{fib_seq[-1]} // seq(-2) = #{fib_seq[-2]} // seq = #{fib_seq}" | |
fib_seq << fib_seq[-1] + fib_seq[-2] | |
# p "last is prev two added = #{fib_seq}" | |
end | |
end | |
fib_seq.last | |
end | |
# iterative_fib | |
# the method takes argument n (digit desired of fibonacci sequence) | |
# from the first digit in the fibonacci sequence, 0, to n (digit desired), | |
# if n is either 0 or 1 append the number to the array [and return the last number in the array]; | |
# otherwise, append the sum of the last two digits in the array (in this case, getting the first two digits from the right) | |
# to get the nth digit of the sequence [and return it] | |
# note: (0..n), the ".." infers that n is inclusive in the range | |
p recursive_fib(9) #34 | |
p iterative_fib(9) #34 | |
require 'benchmark' | |
num = 35 | |
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