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[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?
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 &lt; 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:


Your solution takes linear time and linear space. Can you modify it to take linear time and constant space?
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)\$