Recursion in PHP - Fibonacci
(Page 3 of 4 )
Fibonacci is another formula that works with recursion, but it also makes you examine if recursion is always the best thing to use in some cases.
The Fibonacci sequence starts with 1, and continues with each number being equal to the sum of the previous 2 numbers, so:
F(n) = F(n-1)+F(n-2)
and F(1) = 1 and F(2) = 1; |
The first few numbers in the Fibonacci sequence are 1, 1, 2, 3, 5, 8, 13, 21, 34, and 55.
So n would be the nth number in the sequence we want. In PHP code the fibonacci recursive function would look like:
<?php
function fibonacci ($n)
{
if ($n == 1 || $n == 2)
{
return 1;
}
else
{
return fibonacci( $n - 1)+fibonacci( $n - 2 );
}
}
?> |
It looks fairly simple and it is. It will even work correctly. This is when caution needs to be taken. Let's see what a function trace for fibonacci(5) looks like (I'll use f in place of fibonacci):
f(5)=f(4)+f(3)
f(4)=f(3)+f(2) f(3)=f(2)+f(1)
f(3)=f(2)+f(1) |
So let's see what we've got:
1 call to f(5)
1 call to f(4)... not so bad..
2 calls to f(3)... hmmm...
3 calls to f(2)... not so good.
2 calls to f(1) |
As you can see, there are a lot of redundant calls in there. I chose f(5) as an example because beyond that, the amount of redundant function calls gets worse even quicker. This shows that recursion may not be the best way to calculate the Fibonacci sequence. When your function will be making numerous calls with the same arguments, your algorithm is wasting time (and memory) recalculating the values of stuff it's already done.
If you are interested in how to calculate the Fibonacci sequence in a non-recursive manner, I've put together a short section at the end of this tutorial explaining an iterative method of calculating the sequence.
Another use of recursive functions would be to traverse a directory structure. In pseudo code it could look like this:
function traverse_dir($dir)
{
open $dir
read in files
put directories in an array
loop through array foreach dir as $subdir
{
do something with $subdir
traverse_dir($subdir)
}
} |
If this code were actual PHP code, it would allow you to start with a starting directory and go through each of the subdirectories doing something. When all of them had been visited the function would exit. The exit condition in this case would be that the array of directories for that particular function call was empty.
I think I've typed enough for now, but hopefully this will give you some idea of what a recursive function is, how to create one, what they are good for and when or when not to use them.
Next: Iterative Fibonacci >>
More Miscellaneous Articles
More By Codewalkers
