Fibonacci sequence in Ruby (recursion)

I'm trying to implement the following function, but it keeps giving me the `stack level too deep (SystemStackError)` error.

Any ideas what the problem might be ?

def fibonacci( n )
[ n ] if ( 0..1 ).include? n
( fibonacci( n - 1 ) + fibonacci( n - 2 ) ) if n > 1
end

puts fibonacci( 5 )

Use matrix exponentiation:
==============

Don't use recursion because the stack accumulates and you'll hit a limit at some point where the computer can't handle any more. That's the `stack level too deep (SystemStackError)` you're seeing. Use matrix exponentiation instead:

def fib(n)
(Matrix[[1,1],[1,0]] ** n)[1,0]
end

fib(1_000_000) #this is too much for a recursive version

This one uses memoization and recursion:

def fib(num, memo={})
return num if num <= 1

if memo[num]
return memo[num]
else
memo[num] = fib(num - 2, memo) + fib(num - 1, memo)
end
end

A nice little intro to Ruby [Fiber](

[To see links please register here]

) -

```rb
def fibs x, y
Fiber.new do
while true do
Fiber.yield x
x, y = y, x + y
end
end
end
```

Above we create an infinite stream of `fibs` numbers, computed in a very efficient manner. One does not simply `puts` an infinite stream, so we must write a small function to collect a finite amount of items from our stream, `take` -

```rb
def take t, n
r = []
while n > 0 do
n -= 1
r << t.resume
end
r
end
```

Finally let's see the first `100` numbers in the sequence, starting with `0` and `1` -

```rb
puts (take (fibs 0, 1), 100)
```

```none
0
1
1
2
3
5
8
13
21
34
55
.
.
.
31940434634990099905
51680708854858323072
83621143489848422977
135301852344706746049
218922995834555169026
```

PHI = 1.6180339887498959
TAU = 0.5004471413430931

def fibonacci(n)
(PHI**n + TAU).to_i
end

You don't need recursion.

**Linear**

module Fib
def self.compute(index)
first, second = 0, 1
index.times do
first, second = second, first + second
end
first
end
end

**Recursive** with caching

module Fib
@@mem = {}
def self.compute(index)
return index if index <= 1

@@mem[index] ||= compute(index-1) + compute(index-2)
end
end

**Closure**

module Fib
def self.compute(index)
f = fibonacci
index.times { f.call }
f.call
end

def self.fibonacci
first, second = 1, 0
Proc.new {
first, second = second, first + second
first
}
end
end

None of these solutions will crash your system if you call `Fib.compute(256)`

1) Example, where max element < 100


def fibonachi_to(max_value)
fib = [0, 1]
loop do
value = fib[-1] + fib[-2]
break if value >= max_value
fib << value
end
fib
end

puts fibonachi_to(100)

Output:

0
1
1
2
3
5
8
13
21
34
55
89

2) Example, where 10 elements


def fibonachi_of(numbers)
fib = [0, 1]
(2..numbers-1).each { fib << fib[-1] + fib[-2] }
fib
end

puts fibonachi_of(10)

Output:

0
1
1
2
3
5
8
13
21
34

yet another ;)

```
def fib(n)
f = Math.sqrt(5)
((((1+f)/2)**n - ((1-f)/2)**n)/f).to_i
end
```

will be convenient to add some caching as well
```
def fibonacci
@fibonacci ||= Hash.new {|h,k| h[k] = fib k }
end
```

so we'll be able to get it like

```
fibonacci[3] #=> 2
fibonacci[10] #=> 55
fibonacci[40] #=> 102334155
fibonacci #=> {3=>2, 10=>55, 40=>102334155}
```

Try this

def fibonacci( n )
return n if ( 0..1 ).include? n
( fibonacci( n - 1 ) + fibonacci( n - 2 ) )
end
puts fibonacci( 5 )
# => 5

check this post too

[To see links please register here]

and more ..

[To see links please register here]

You have now been bombarded with many solutions :)

regarding problem in ur solution

you should return `n` if its `0` or `1`

and `add` last two numbers not last and next



> New Modified version

def fibonacci( n )
return n if n <= 1
fibonacci( n - 1 ) + fibonacci( n - 2 )
end
puts fibonacci( 10 )
# => 55


> One liner

def fibonacci(n)
n <= 1 ? n : fibonacci( n - 1 ) + fibonacci( n - 2 )
end
puts fibonacci( 10 )
# => 55

# This approach is fast and makes use of memoization:

fib = Hash.new {|hash, key| hash[key] = key < 2 ? key : hash[key-1] + hash[key-2] }

fib[123] # => 22698374052006863956975682


In case you're wondering about how this hash initialization works read here:

[To see links please register here]