Fibonacci numbers - newbie question.

[salai]

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.

 

[Justin Collins]

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

Notice the difference between the two when x is 0.

-Justin

 

[Stefano Crocco]

|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.

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

 

[jzakiya]

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: http://en.wikipedia.org/wiki/Fibonacci_number

 

[Sergio Arbeo]

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: 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

 

[Todd Benson]

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.

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

 

[Jörg W Mittag]

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

 

[Todd Benson]

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 =3D 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:

=A0 =A0 =A0 =A0fibs =3D 0 : 1 : zipWith (+) fibs (tail fibs)

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

Ha! That is just cool.

Todd

 

[Jay Anderson]

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

Attachments:
http://www.ruby-forum.com/attachment/3876/lazy.rb