21 June, 2011 - 21:28 — Amp

This is going to be a bit of a change from my normal rants on here, but I figure that I should give a prelude to some future guides I may be doing. Also, I strong recommend having some basic knowledge of high level programming for this guide.

One recent concept that I have worked with is recursion. For those not in the know, recursion is the process of solving a problem by breaking it down into smaller versions of itself. When somebody first hears about such a concept, they usually don't immediately catch the concept in full until they actually take a detailed look into an example that handles such a concept. When an algorithm implements such as method, it is usually known as a recursive method. Now, one example of recursion that many people don't know is the Fibonacci sequence. This sequence is a unique one where the number in each part of the sequence is determined by the adding the last two numbers in the sequence before it. For a computer to calculate the fibonacci sequence recursively, the following algorithm is usually implemented in the following pseudocode below.

method fibonacci takes an input value that represents the position in the fibonacci sequence and returns the number in that position

if the input value is 0 or 1 then a value is returned for the position that is equal to the input value given

otherwise, the return value is determined by adding the numbers together from the two previous positions in the fibonacci sequence

When implementing this in a high level programming language, it will usually look like so.

public static int fibonacci(int n){

if(n == 0 || n == 1){

return n;

}

else{

return fibonacci(n-1) + fibonacci(n-2);

}

}

So when somebody enters in the value of 3 for the position of the Fibonacci sequence they are looking for, the program checks to see if it is equal to 0 or 1 (which is obviously isn't) then returns the numbers from the two positions before it which would respectively be 2 and 1. The fibonacci method is then executed again for the second and first positions. For the second position, it checks to see if it is equal to 0 or 1 which is isn't, so it returns the numbers from the two positions before it which would be 0 and 1. When the sequence is executed for the first position, it returns 1 as the if statement given is true. Likewise, when the if statement for position 0 will cause it to return 0 as the if statement given is also true for that number. By breaking it down in this way, the program can eventually find the third position which would be 2 it adds together the numbers from it's previous positions which would both be 1.

Now, I will state that this may not be the most efficient way of doing this when trying to figure out higher portions of the fibonacci sequence such as the 100th position, but it is a good introduction to this topic.

Postnote: If people are interested in more guides covering basic programming concepts such as this, please do give feedback. Also, feedback about how to improve this part would be appreciated.

- Amp's blog
- Login or register to post comments