Fibonacci numbers - newbie question

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

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

3

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

···

On Sunday 12 July 2009, salai wrote:

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

4

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

···

On Jul 12, 5:40 am, Stefano Crocco <stefano.cro...@alice.it> wrote:

On Sunday 12 July 2009, salai wrote:

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

5

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

···

2009/7/12 jzakiya <jzakiya@mail.com>:

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

--
http://sergio.arbeo.net
http://www.serabe.com

6

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

···

On Sun, Jul 12, 2009 at 12:15 PM, jzakiya<jzakiya@mail.com> wrote:

On Jul 12, 5:40 am, Stefano Crocco <stefano.cro...@alice.it> wrote:

On Sunday 12 July 2009, salai wrote:

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

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.

7

Todd Benson 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

Ha! That is just cool.

Todd

···

2009/7/13 Jörg W Mittag <JoergWMittag+Usenet@googlemail.com>:

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

9

Todd Benson wrote:

···

2009/7/13 J�rg W Mittag <JoergWMittag+Usenet@googlemail.com>:

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

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

--
Posted via http://www.ruby-forum.com/\.