Hi friends.
I am having trouble understanding this piece of code:
<h2>Fibonacci sequence using recursion</h2>
<table cellspacing=”0” border=”0” style=”width: 20em; border:
1px solid #666;”>
<tr>
<th>Sequence #</th>
<th>Value</th>
</tr>
$iterations = 10;
function fibonacci( $n ) {
if ( ( $n == 0 ) || ( $n == 1 ) ) return $n;
return fibonacci( $n-2 ) + fibonacci( $n-1 );
}
for ( $i=0; $i <= $iterations; $i++ )
{
?>
<tr<?php if ( $i % 2 != 0 ) echo ‘ class=”alt”’ ?>>
<td>F<sub><?php echo $i?></sub></td>
<td><?php echo fibonacci( $i )?></td>
</tr>
<?php
}
?>
</table>
From the book I am reading, the following is an explanation of how it works:
How It Works
Most of the code is similar to the script in Chapter 4. The script displays an XHTML header, then
creates a table to display the results. It also uses a for loop to display the Fibonacci numbers F0 to F10,
much like the Chapter 4 script.
The difference is in how the Fibonacci numbers are computed. The iterative version in Chapter 4 uses
two variables, $num1 and $num2, to hold the current two Fibonacci numbers, computing new numbers
as it iterates through the loop. This script, on the other hand, uses a recursive function, fibonacci(),
to compute the Fibonacci number for any given sequence number. This function is then called from
within the for loop to display the Fibonacci numbers F0 to F10.So how does the fibonacci() function work? You can see that it accepts the current sequence
number, $n, as an argument. The first line of the function itself represents the base case:
if ( ( $n == 0 ) || ( $n == 1 ) ) return $n;
This code checks if the sequence number is 0 or 1; if it is then it immediately exits the function and
returns the sequence number (because F0 is 0 and F1 is 1). So once this condition is met, the function
finishes and control is passed back to the calling code.
If the base case hasn’t yet been reached, the second line of code is run:
return fibonacci( $n-2 ) + fibonacci( $n-1 );
This code calls the fibonacci() function twice recursively — once to compute the Fibonacci number
two positions lower in the sequence, and once to compute the Fibonacci number that’s one position
lower in the sequence. It then adds these two Fibonacci numbers together to produce the Fibonacci
number for the current sequence number, which it then returns to the calling code (which will either
be the code within the for loop, or another instance of the fibonacci() function).
So when this function is run with a sequence number of, say, 10, it calls itself to obtain the numbers at
positions 8 and 9. In turn, when called with the sequence number 8, the function computes the
Fibonacci number at this position by calling itself to obtain the numbers at positions 6 and 7, and so
on. This process continues until the function is called with a sequence number of 0 or 1; at this point, it
no longer calls itself but merely returns the value 0 or 1.
You can see that the function calls itself in a pattern that resembles a tree, with the initial function call
as the root of the tree and the various recursive calls as branches of the tree. In fact, recursive functions
are well suited to working on data organized like a tree, as you see when working with files and
folders in Chapter 11.
You see, I find a number of things very confusing about this.
Now just to try and keep this as simple as possible I will tell you how i (personally) understand this code. And if you can tell me where i am misunderstanding things, it will be greatly appreciated.
Here is my understanding:
1) A 'for loop' is created and is set to repeat 10x
2) Within the 'for loop', we call the fibonacci function (passing the argument of $i):
<td><?php echo fibonacci( $i )?></td>
........ now because $i is equal to '0' or '1' for the first couple of calls to the function, the following line will return our value to the calling code:
if ( ( $n == 0 ) || ( $n == 1 ) ) return $n;
.... and the following line will not be executed:
return fibonacci( $n-2 ) + fibonacci( $n-1 );
3) when $i exceeds the value of '1', the function will finally execute this line:
return fibonacci( $n-2 ) + fibonacci( $n-1 );
.... and this will repeat until $i is less than or equal to $iterations.
Now clearly, my theory is a bit different from the explanation given by the book i am reading. But I can't help but think that the author may have mixed his words up slightly. As there are some things in his explanation that just don't sound right. Like the following remarks he made:
The first line of the function itself represents the base case:
if ( ( $n == 0 ) || ( $n == 1 ) ) return $n;
From what i can see, the only thing this snippet of code does is keep returning the value of $i back to its calling code until it is bigger than the value of '1',,,, not allowing the following line:
return fibonacci( $n-2 ) + fibonacci( $n-1 );
..... to execute until $i is above the value of '1'.
And i also cannot understand how:
fibonacci( $n-2 )
references what the value of $i was, two iterations ago? Because to me it just looks like it is subtracting 2 from whatever the current value of $i is.
Can someone please explain. This is so confusing.
Paul.