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.

Hello World

This being my first post, let me write the custom Hello World
My interest revolves around three things as of this writing.
So, here I post the three "Hello World" programs using them.

  • Perl
perl -e 'print "Hello World\n"'

perl invokes the interpreter and -e (hyphen e) tells that a program is following it.
Using 5.10 and above versions, we can write like the following

perl -M5.010 -e 'say "Hello World"'

-M loads the module 5.010 for us and hence the say function works as expected.

  • Oracle SQL
select 'Hello World' from dual;

dual is a special table that comes with the Oracle database.
from clause is a must in Oracle (not like MySQL).

Though I distinguished SQL and PL/SQL here, usually I don’t. Its just the “Oracle.”
My experience is with only one database and it is Oracle.
So, if you want to learn about any other database, this is not the site.

  • Oracle PL/SQL
set serveroutput on
exec dbms_output.put_line('Hello World');

The above code is not a PL/SQL as a whole. First line is an SQL*Plus command.
And exec of the second line is also an SQL*Plus command.
Here comes the pure PL/SQL program.

begin
    dbms_output.put_line('Hello World');
end;
/
  • JavaScript
<script type="text/javascript">
    alert('Hello World');
</script>

Hello World – from the omni-present JavaScript
This html code fragment (yes, it is not a complete mark-up) should show a message box.