Fibonacci Sequence – Part 1

This is not a simple topic in the perception of a programmer. The first two things which we must learn using this sequence are

  • Iteration – which is nothing but a simple for loop
  • Recursion – which is nothing but a Recursion
function fib(n)                    // get the nth term
{
    // 0 1 1 2 3 5 8 13 21 34 55 ...
    if (n == 1 || n == 2)
        return n - 1;              // 1st term is 0 and 2nd term is 1
    var first  = 0;                // initializing the same; 1st term is 0
    var second = 1;                // 2nd term is 1
    var current;                   // this variable is going to hold the value of nth term
    for(var i = 3; i <= n; ++i) {
       current = first + second;
       first   = second;
       second  = current;
    }
    return current;
}
alert(fib(1) + " " + fib(5) + " " + fib(10));

I hope that the code is sufficiently documented.
Currently, I am using Firefox v11. So, to execute this JavaScript code, I used Tools -> Web Developer -> Scratchpad.
We are defining that the 1st term as zero and the 2nd term as one.
To calculate any other terms (i.e. n >= 3), we use the for loop.
The nth term is nothing but the sum of (n – 1)th term and (n -2)th term.
The 1st term for the next calculation is nothing but the 2nd term of current calculation.
And, the 2nd term for the next calculation is the current calculated term.
It looks so simple.

Now, let us see the recursive version.

function fib(n)                        // get the nth term
{
    // 0 1 1 2 3 5 8 13 21 34 55 ...
    if (n == 1 || n == 2)
        return n - 1;                  // 1st term is 0 and 2nd term is 1
    return fib(n - 2) + fib(n - 1);    // fib(nth term) = fib(n - 1)th term + fib(n -2)th term
}
alert(fib(1) + " " + fib(5) + " " + fib(10));

That is the simplicity of the Recursion.
Here, recursion is nothing but the function to call itself.
Hope you have understood both the programs clearly.

Note: Before defining the function completely, we are calling it.
This may not be possible in all the languages.

Now, let us see the Perl translation of these two programs.

sub fib {                                 # 0 1 1 2 3 5 8 13 21 34 55 ...
    my $n = pop @_;                       # get the argument passed

    return $n - 1 if $n == 1 or $n == 2;  # 1st term is 0 and 2nd term is 1

    my $first  = 0;                       # initializing the same; 1st term is 0
    my $second = 1;                       # 2nd term is 1
    my $current;                          # this variable is going to hold the value of nth term
    for(my $i = 3; $i <= $n; ++i)    {
       $current = $first + $second;
       $first   = $second;
       $second  = $current;
    }
    return $current;
}
print fib(1), " ", fib(5), " ", fib(10);

This is a Perl v5 code. I am not sure about v4 or v6.
If you are a JavaScript programmer, trying to learn Perl, you can see so many weird things.
(Yes, I have coded a few JavaScript before moving to Perl.)
Listing a few …

  • Dollar prefixed variable names
  • Line no.4 -> if statement (in fact, in Perl, we call it as a statement modifier).
  • my replacing var
  • or operator
  • No formal arguments
  • print without any parentheses.

 

I am showing how to learn Perl comparing with the JavaScript.
This blog being not intended as a Perl tutorial, please learn from other sites, if you would like to.

If you are a Perl programmer and trying to learn JavaScript, nothing I need to explain.
Obviously, you will find it easier.

Let us see the recursive version too.

sub fib {                                 # 0 1 1 2 3 5 8 13 21 34 55 ...
    my $n = pop @_;                       # get the nth term

    return $n - 1 if $n == 1 or $n == 2;  # 1st term is 0 and 2nd term is 1
    return fib($n - 2) + fib($n - 1);     # fib(nth term) = fib(n - 1)th term + fib(n -2)th term
}
print fib(1), " ", fib(5), " ", fib(10);

A few more posts about the Fibonacci are in the way.

Advertisements

2 thoughts on “Fibonacci Sequence – Part 1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s