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!