Fibonacci numbers - newbie question

Ruby
1

Dear All,

I have two Fibonacci method, and I got different result.

What wrong in my code.?

def fib(n)
if n < 2
1
else
fib(n-2) + fib(n-1)
end
end

puts fib(10) # —> 89

def fib1(x)
return x if x < 2
return fib1(x- 1) + fib1(x - 2)
end

puts fib1(10) # --> 55

regards,
salai.

2

salai wrote:

fib(n-2) + fib(n-1)

puts fib1(10) # --> 55

regards,
salai

Notice the difference between the two when x is 0.

-Justin

3

On Sunday 12 July 2009, salai wrote:

| fib(n-2) + fib(n-1)
|
|
|
|puts fib1(10) # --> 55
|
|
|regards,
|salai.

In the first case, if the number is less than 2, you always return 1. In
the
second case, you return the number itself (that is, 1 if x is 1 and 0 if
x is
0).

Stefano

4

On Jul 12, 5:40 am, Stefano C. [email protected] wrote:

|def fib(n)
|def fib1(x)
|salai.

In the first case, if the number is less than 2, you always return 1. In the
second case, you return the number itself (that is, 1 if x is 1 and 0 if x is
0).

Stefano

Many people forget (or don’t know) the series starts:

Fib(0)=0
Fib(1)=1
Fib(2)=1
…
So when x < 2 then Fib=x
These initial conditions are important for doing algebraic forms for
the series.

And actually, the full series can be extended into negative numbers.
See at url: Fibonacci sequence - Wikipedia

5

2009/7/12 jzakiya [email protected]:

And actually, the full series can be extended into negative numbers.
See at url: http://en.wikipedia.org/wik

Indeed, but salai’s problem is still that. For him, in one method F(0)
= 1 and on the other method F(0) = 0.

Cheers,

Serabe

6

On Sun, Jul 12, 2009 at 12:15 PM, jzakiya[email protected] wrote:

|
|
|regards,
Fib(0)=0
Fib(1)=1
Fib(2)=1
…
So when x < 2 then Fib=x
These initial conditions are important for doing algebraic forms for
the series.

The first time I saw this problem, I did the recursive thing, but I
just had to use #inject, so for a full list…

n = 10
(0…n-1).inject([0,1]) {|a, i| a.push(a[-2] + a[-1])}

Of course if you only want the nth number you can #shift inside the
#inject, and always keep the array size 2.

Todd

7

Todd B. wrote:

The first time I saw this problem, I did the recursive thing, but I
just had to use #inject, so for a full list…

n = 10
(0…n-1).inject([0,1]) {|a, i| a.push(a[-2] + a[-1])}

Although, when it comes to Fibonacci, Haskell just rules, IMHO:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Zipping an infinite list with itself to produce itself … brilliant.

jwm

8

Todd B. wrote:

2009/7/13 J�rg W Mittag [email protected]:

Zipping an infinite list with itself to produce itself … brilliant.

Ha! That is just cool.

Todd

Of course it can be sort of translated into ruby (see attached for lazy
list implementation):

FIBS = LL[0, LL[1, lambda{FIBS.zip_with(FIBS.tail, &:+)}]]

-----Jay

9

2009/7/13 Jörg W Mittag [email protected]:

Zipping an infinite list with itself to produce itself … brilliant.

Ha! That is just cool.

Todd