Fibonacci recursion

What are Fibonacci numbers? Fibonacci numbers are numbers that are made up of two lower-value numbers added together to make a sum. This sum and the previous sum is then added together to create a new sum, which is the next Fibonacci number in the series. Wow, I suck at explaining, don’t I?
Basically, it goes like this:
1, 1, 2, 3, 5, 8, 13, 21, 34 ......

Click image to enlarge.

What is happening here, is that the first two numbers, 1 and 1, are added together. We get 2. Then, we add 1 and 2 and get 3. Going further, we add 2 and 3 to get 5. This continues ad infinitum until you get absolutely enormous numbers. It never stops. Of course, there are restrictions in computer programs, as the biggest native variable currently available in the Gcc compiler is the “unsigned long long int”, which can hold a value up to 18,446,744,073,709,551,615. That’s eighteen quintillion four hundred and forty-six quadrillion seven hundred and forty-four trillion seventy-three billion seven hundred and nine million five hundred and fifty-one thousand six hundred and fifteen different values. Using “unsigned long long integers” in the program is probably the best course of action for the best amount of flexibility.
Here, we create a function called “fibonacciList”, which will have the formidable task of calculating and displaying the desired series of fibonacci numbers. In the function, we have the integer “first”, which will be added to the integer “second”. The integer “sum” will hold the final sum of “first” and “second”.

The first thing that happens in the function, is the addition of “first” and “second”, applying the sum to “sum”. After this, we get an “if”-statement. The “listFractions” boolean tells whether or not to list “first” and “second”. If this wasn’t here, it would duplicate the last two sums again and it would we a complete mess of an output. Later in the function, when we call it recursively, we set “listFractions” to false in order to avoid this problem, thus the “first” and “second” will only be printed the first run through.

Below the printing of the new “sum”, we set “first” to “second” and “second” to sum” to prepare for another run through the function. That is, assuming “sum” doesn’t exceed the maximum limit we have set in the “if”-statement.

The initial values of “first” and “second” are free to be changed to whatever value is desired. If there is a need for decimal values, replace the integers variables with either float or double variables.


Leave a Reply

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

You are commenting using your 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