Ben Reichelt’s Weblog

I’d like to do a little educational series a la target=_blank>Raymond Chen and
target=_blank>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 target=_blank>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:

style="MARGIN: 0in 0in 0pt; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: blue; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">static style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes"> style="COLOR: blue">int fact(int
n)

style="MARGIN: 0in 0in 0pt; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">{

style="MARGIN: 0in 0in 0pt; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: blue; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">if style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes"> (n ==
1)

style="MARGIN: 0in 0in 0pt 0.5in; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: blue; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">return style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">
1;

style="MARGIN: 0in 0in 0pt; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: blue; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">else

style="MARGIN: 0in 0in 0pt 0.5in; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: blue; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">return style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes"> n *
fact(n – 1);

style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">}

style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes; mso-fareast-font-family: 'Times New Roman'; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA">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.

style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes; mso-fareast-font-family: 'Times New Roman'; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA">The first way that we will generate the fibonacci numbers is
using recursion.

style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes; mso-fareast-font-family: 'Times New Roman'; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA">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:

style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes; mso-fareast-font-family: 'Times New Roman'; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA">

style="MARGIN: 0in 0in 0pt; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: blue; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">static style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes"> style="COLOR: blue">long Fibo(long
n)

style="MARGIN: 0in 0in 0pt; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">{

style="MARGIN: 0in 0in 0pt; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: gray; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">//

style="MARGIN: 0in 0in 0pt; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: gray; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">//
check the base cases

style="MARGIN: 0in 0in 0pt; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: gray; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">//

style="MARGIN: 0in 0in 0pt; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: blue; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">if style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes"> (n <=
1)

style="MARGIN: 0in 0in 0pt 0.5in; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: blue; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">return style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">
0;

style="MARGIN: 0in 0in 0pt 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: blue; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">if style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes"> (n ==
2)

style="MARGIN: 0in 0in 0pt 0.5in; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: blue; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">return style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">
1;

style="MARGIN: 0in 0in 0pt; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes"> 

style="MARGIN: 0in 0in 0pt; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: gray; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">//

style="MARGIN: 0in 0in 0pt; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: gray; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">//
calculate the 2 previous

style="MARGIN: 0in 0in 0pt; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: gray; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">//
numbers and add them together

style="MARGIN: 0in 0in 0pt; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: gray; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">//

style="MARGIN: 0in 0in 0pt; TEXT-INDENT: 0.5in; mso-layout-grid-align: none"> style="FONT-SIZE: 10pt; COLOR: blue; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">return style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes"> Fibo(n -
1) + Fibo(n – 2);

style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">}

style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes"> 

style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">This code is extremely simple, there are more lines of
comments than of actual code! Try this code out in a console application, start
out small by calling Fibo(4), Fibo(5), etc.  See if you notice anything as
you put in higher and higher numbers Next, we’ll inspect this function a
little, and improve upon it a little bit.

style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes"> 

style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'; mso-no-proof: yes">Thanks for reading!