Finding the nth Fibonacci number using recursive technique

Question

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[11] 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.

Thoughts? Any advice?

Answer 1

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)\$

Answer 2

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