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 ) echoclass=”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.

    If you don't understand the Fibonacci sequence, it doesn't make a lot of sense.

    If you do, it makes more sense. 0 and 1 are the first two numbers in the sequence, so the function returns them without computation.

    The 3rd number in the sequence is the sum of the first two. The fourth number in the sequence is the sum of the 2nd and 3rd, and so on.

    And i also connot 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.

    If you mean "$n-2", you're correct, but "fibonacci($n-2)" isn't the same thing. 😉

      It can be very difficult to get your mind around recursion. In computing, recursion means that a function calls itself. The key to successfully writing a successful recursive function is making sure that the function will quite at some point rather than calling itself infinitely. This means you must design your function to go in a particular direction (always up or always down) and quit once it reaches a certain point. Your fibonacci function is well designed in this respect because it always goes down. I.e., if you call it on some number N, then it will call itself on N-1 and N-2. However, it has a potentially serious problem. Take a closer look at it:

      function fibonacci( $n ) {
        if ( ( $n == 0 ) || ( $n == 1 ) ) return $n;
        return fibonacci( $n-2 ) + fibonacci( $n-1 );
        }
      

      What happens if you call fibonacci(-1) ? In that case, it will keep calling itself forever (or until memory runs out or some other limit is reached).

      You should try and walk through what it does when you call it with various numbers. 0 and 1 are easy -- it simply returns the supplied value of $n. 2 is where it starts to get interesting (and a bit complicated).

        You have made a good argument for bounds-checking. As the Fibonacci sequence starts, by definition, at zero, there should be an error state or message declared if a number less than zero is submitted.

        The 'beauty' here is that the Fibonacci sequence lends itself perfectly to solution by recursive iterations ...

          when you say:

          If you mean "$n-2", you're correct, but "fibonacci($n-2)" isn't the same thing.

          ..... fibonacci($n-2) is clearly not a built in function is it?

          so i just don't understand how:

          $n-2

          .... when specified inside the user-defined fibonacci() function would work any differently to:

          $n-2

          ...... on its own.

          Is this something conman to all functions?

            Paul help!;11049403 wrote:

            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'.

            Your observation here is correct. But his assertion that zero and 1 are the "base case" is also correct. If you want to define a sequence where each member depends on the two prior elements, you first have to describe what happens when you don't have two prior elements. You are both correct, but the phrase "base case" is not especially meaningful or precise in this context. Your explanation is more literal and "computery."

            Paul help!;11049403 wrote:

            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.

            That code is not referencing any prior iterations. That code will literally cause the computer to go through all the steps to completely calculate the fibonacci value of $n-2, which involves quite a bit of work on the computer's part. If $n is 23 (meaning you are trying to calculate the 23rd number in the Fibonacci sequence) then that tiny bit of code tells the computer to go off and calculate the fibonacci value of 21 - because 23 minus 2 is equal to 21. It should be apparent that this fibonacci function is going to be doing a lot of work as you get to higher numbers because it has to call itself twice for every value of $n greater than 1. The fact that it has to call itself to accomplish this means that function is going to be running a lot.

            Consider modifying it to echo some output as it runs and you'll get a clearer idea of what is happening:

            function fibonacci( $n ) {
              echo "I, fibonacci(), have been asked to calculate the " . $n . "th number in the sequence.<br>";
              if ( ( $n == 0 ) || ( $n == 1 ) ) {
                echo "\t" . $n . " represents one of the two base cases so I am returning " . $n . "<br>";
                return $n;
              }
            
              echo "\tUh oh! This is not a base case. Since the " . $n . "th Fibonacci number is the sum of the " . ($n-2) . "th and " . ($n-1) . "th Fibonacci numbers, I must calculate them first, which I will do right now<br>";
              $result = fibonacci( $n-2 ) + fibonacci( $n-1 );
              echo "\tI have finally calculated F(" . ($n-2) . ") + F(" . ($n-1) . ") and the result is " . $result . "<br>";
              return $result;
            }
            
              Write a Reply...