public Blog<BenR>

CSci 101 Part I

I'd like to do a little educational series a la Raymond Chen and Larry Osterman.  Now, this series will NOT be nearly as technical, nor as difficult or in depth as these two can get, its just something that I thought I would try out.  If I like it, maybe someday I will have some really cool stuff to give a tutorial on, and I can do that, but for now, we're going to keep it fairly academic, being as I just graduated from college, this seems appropriate.

I'm going to talk about the fibonacci numbers, and a few different ways to go about generating them.  The fibonacci numbers are a sequence of numbers that are calculated by adding the previous two numbers in the sequence.  The first two numbers are given, they are 0 and 1, respectively. So the 3rd number in the sequence is 0 + 1 = 1, the 4th is 1 + 1 = 2, and so on.

In my first computer science class at school, one of the first concepts they try to beat into you is recursion. A recursive function is one that makes a call to itself.  A classic example of recursion is the way that you can write a factorial function.

We can rewrite n! as n * (n-1)!, which we can rewrite as n * (n - 1) * (n - 2)!, etc.  The way this would be represented in our code would be:

static int fact(int n)

{

if (n == 1)

return 1;

else

return n * fact(n - 1);

}

Notice how the fact function calls itself.  Its important to have a base case so that the recursion ends at some point; in this example the base case occurs when n == 1, at that point we simply return 1 because 1! = 1, so we can stop recursing.

The first way that we will generate the fibonacci numbers is using recursion.

The base cases for our function will be when n == 0 or n == 1, because those fibonacci numbers are given to us. If n > 1, then we will calculate the 2 previous fibonacci numbers, by recursively calling the same function, and adding them together.  Here's the code: