# Finding the nth Fibonacci number using recursive technique

EDIT

So I've been working on this according to the challenge @PeterTaylor gave me. I'm not very good at math, so I've been doing a lot of reading and found this link on the Binet form. Fibonacci algorithms

Unfortunately, when I use this in Ruby, it typically returns Infinity above 1000 or so for n. It works well for smaller equations, but not so much for very large numbers.

Here is the code I wrote for it.

a = (1 + Math.sqrt(5))/2

b = (1 - Math.sqrt(5))/2
#here, n == 5
f = ((a**5) - (b**5))/(a-b)


When you round f.to_i, it returns 5.

Back to the drawing board.

Original post below

Practicing recursion some more, and I'm wondering if this is the proper solution for this exercise I'm doing.

First, my code in Ruby:

def fibonacci(num, fact=[1,1])
x = fact[fact.length-1]
y = fact[fact.length-2]
if fact[num-1]
return fact[num-1]
else
fibonacci(num, fact.push(x+y))
end
end

p fibonacci(5)
p fibonacci(12) == 144
p fibonacci(20) == 6765
p fibonacci(8200)


The exercise is this: Write a recursive method that computes the nth Fibonacci number, where nth is an argument to the method.

So, the 12th fibonacci number (which would be fact due to indexing) is 144.

I know that I am returning the correct number, and that the recursion stops once fact[num-1] returns true. I can't help but feel that this is not the best way to do this, or even the proper way to do this.

Firstly, a minor point. fact? Have you refactored a recursive factorial method and forgotten to rename the accumulator?

That aside, I find this hilarious. Almost certainly the intended solution was along the lines of

def fibonacci(num)
if num < 2
return 1
else
return fibonacci(num - 2) + fibonacci(num - 1)
end
end


which is the naïve recursive definition, and a classic teaching example of how naïve implementations can be insanely inefficient.

Your answer meets the rather vague spec (it is recursive), but is much better than the intended solution because it takes linear time (or maybe quadratic if push is linear, but I doubt it) rather than exponential.

If you want an additional challenge, here are two:

1. Your solution takes linear time and linear space. Can you modify it to take linear time and constant space?
2. Can you modify it further to take logarithmic time and constant space?

Hint for the second one:

$F(m+n) = F(m+1) F(n) + F(m) F(n-1)$

• I'll try. I should mention that I am not very good at this (I've been learning for the past couple of years, but only recently go serious about programming since I want to change careers) and my math sucks. But, I'll research it and try to come up with my own solution. It might take me a few days, but I'll get back to you. Oct 14, 2017 at 5:10
• I've been working on this, and so far I've done a lot of reading. I actually came upon this equation for the Binet form here: whitman.edu/Documents/Academics/Mathematics/2015/… So I thought that would be a good thing to try. Unfortunately, it looks like it returns Infinity when you get into some higher numbers, typically above 1000 or so. I will update my main post shortly. Oct 15, 2017 at 6:40
• @Nathan, the first challenge only requires very minor changes to replace the list with a fixed number of integers. The second challenge is (in disguised form) matrix exponentiation. Oct 15, 2017 at 7:20

Your problem is that Math.sqrt(5) returns a Float, so your answer is also a Float. Your answer is only precise to about Float::DIG decimal digits (about 15 digits), and can't go above Float::MAX (about $10^{308}$) without overflowing to infinity.

Ruby's BigDecimal can calculate $\sqrt 5$ with more precision. BigDecimal(5).sqrt(30) would calculate $\sqrt 5$ to 30 digits. I believe that fib(n) is an integer with at most $\lceil n \div 4 \rceil$ digits, so we want that many digits of $\sqrt 5$. Ruby's n / 4 would round down, so I write (n + 3) / 4 to round up. I modify your code to get

require 'bigdecimal'

def fib(n)
sqrt5 = BigDecimal(5).sqrt((n + 3) / 4)
a = (1 + sqrt5) / 2
b = (1 - sqrt5) / 2
f = (a**n - b**n) / (a - b)
f.round
end

(0..300).each{|n| printf "fib(%s) = %s\n", n, fib(n)}


The output ends with

fib(298) = 84885164052257330097714121751630835360966663883732297726369399
fib(299) = 137347080577163115432025771710279131845700275212767467264610201
fib(300) = 222232244629420445529739893461909967206666939096499764990979600


I get $\lceil n \div 4 \rceil$ from taking the logarithm, base 10, of fib(n). That's because a positive integer with $d$ digits has about as many digits as $10^d$, and $\log_{10}(10^d) = d$. We can't take the logarithm of zero, so I assume $n \ge 1$ in

\eqalign{ d &= \log_{10}(\frac{\alpha^n - \beta^n}{\alpha - \beta}) \\ &= \log_{10}(\alpha^n - \beta^n) - \log_{10}(\alpha - \beta) \\ &= \log_{10}(\alpha^n) - \log_{10}(1 - \frac{\beta^n}{\alpha^n}) - \log_{10}({\alpha - \beta)} \\ &\le \log_{10}(\alpha^n) - \log_{10}(1 - \frac{\beta^2}{\alpha^2}) - \log_{10}({\alpha - \beta)} \\ &< \log_{10}(\alpha^n) + 0.07 - 0.34 \\ &< \log_{10}(\alpha^n) = \frac{\log_\alpha(\alpha^n)}{\log_\alpha(10)} = \frac{n}{\log_\alpha(10)} < \frac{n}{4.78} < \frac n 4 }

This applies a few of Wikipedia's logarithmic identities, and exploits $\beta^n \div \alpha^n \le \beta^2 \div \alpha^2$. It shows that fib(n) has about the same number of digits as $\alpha^n$, which seems correct because $\alpha$ is the golden ratio. I use Ruby to calculate the values 0.07, 0.34, 4.78:

irb(main):001:0> a = (1 + Math.sqrt(5)) / 2
=> 1.618033988749895
irb(main):002:0> b = (1 - Math.sqrt(5)) / 2
=> -0.6180339887498949
irb(main):003:0> -Math.log(1 - b**2 / a**2, 10)
=> 0.06849027833194808
irb(main):004:0> Math.log(a - b, 10)
=> 0.3494850021680094
irb(main):005:0> Math.log(10, a)
=> 4.784971966781666