This tutorial will teach you how to use recursion in PHP. The best way to show how to use recursion is to use the Fibonacci sequence.

The Fibonacci sequence is a sequence of numbers, each number being the sum of the two numbers before it. For example, the first ten Fibonacci numbers are { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 }. Very simple to understand. Since the first number in the sequence is first, then it is zero because there are no numbers before it to make a sum out of. The second number is 1, third is 1 because of 0 + 1 = 1. The fourth number in the sequence is where things really start to grow, where 1 + 1 = 2. Fifth is 1 + 2 = 3, so on and so forth.

What if we wanted to find the Fibonacci sequence number of 11? Simple, we take the ninth and tenth numbers in the sequence and add them together. Since we have a set above that has those numbers, lets figure it out. The ninth number is 21, and the tenth number is 34. Add them together to get the eleventh number; 21 + 34 = 55. 55 is the eleventh Fibonacci sequence number.

Now to program this sequence into PHP. With recursion, we need at least two if statements that checks for some value that we will give it. In this case, we will be checking an integer. With each if statement that we use, we must have a return statement so that the recursion will have something to work with.

Now one word of caution about recursion, you must ALWAYS have a base case where the recursion can end. If you set it to just call itself over and over without really giving it a base case then the recursive loop will never end. Think of recursion like this:

Function_Call(some_value)

—> Function_Call( Function_Call( some_value ) )

—> Function_Call( Function_Call( Function_Call( some_value ) ) )

The recursive function calls itself creating a sort of loop. Every time the function is called it gets put on hold until it reaches the base case where it stops calling itself and returns values to the previous function call. We see that there are three Function_Call() calls above. The first call waits on the second call while the second call waits on the third. The third Function_Call() hits the base case and returns a value. Now the second Function_Call() will return a value to the first Function_Call(), which returns the completed result to whatever called the function in the first place.

Now that Ive given some background on recursion, lets program it!

function fibonacci($n){
//Base case 1
if($n==1){
return 0;
}
//Base case 2
if($n==2){
return 1;
}else{
//Recursion call
return fibonacci($n-1)+fibonacci($n-2);
}
}
//Call our recursive function
$fib = fibonacci(11);
//And print it to screen
echo $fib;

Now remember, if you use this code, put it between the <?php and ?> brackets.

Now with the Fibonacci sequence, we actually will have three if statements since we have two base cases, and the recursive statement. Our first two base cases are if the inputted integer is 1 or 2, then return 0 or 1. With the recursive statement, we return the function calls of the (current Fibonacci sequence number – 1) + (current Fibonacci sequence number – 2). Lets see this work in text form up to the fourth Fibonacci sequence number:

fibonacci( 4 )

—> fibonacci( fibonacci( 4-1 ) + fibonacci( 4-2 ) )*

—> fibonacci( fibonacci( 3 ) + fibonacci( 2 ) )* //Base case reached

—> fibonacci( fibonacci( 3 ) + 1 )* //Base case 2 returns 1

—> fibonacci( fibonacci( fibonacci( 3-1 ) + fibonacci( 3-2 ))* + 1 )*

—> fibonacci( fibonacci( fibonacci( 2 ) + fibonacci( 1 ))* + 1 )* //Base case reached

—> fibonacci( fibonacci( 1+0 )* + 1 )*//Base cases: 2 returns 1, 1 returns 0

—> fibonacci( fibonacci( 1 )* + 1 )*

—> fibonacci( 1 + 1 )*//Recursive statement returns 1

—> fibonacci( 2 )*

—> 2 //recursive statement returns 2

It looks daunting, I know. But it is very easy to understand once you wrap your head around it. The recursive function calls itself until it reaches the base cases. Once it does, it returns the base case values, which then get summed up and returned through the recursive chain. Ive put an * behind each ) that has a recursive return instead of a base case return. You see that as the function makes its way down the recursive chain, the input reaches the base case then returns, which causes the recursive call to return. Very simple, but messy on paper.

Other notes:

- All PHP code needs “<?php” before and “?>” after the code to run.
- The “$n” is a variable. Use the dollar sign in front of a meaningful variable name to create variables in PHP.
- The keyword “function” tells PHP to create the function “fibonacci(){…}”.
- The double slash “//” is a comment that PHP will ignore. For bigger comments, use “/* really big comment */“.
- The “if(…){…}” is called an if statement. Use to do conditional work.
- The “==” is an operator named “equals to”. Ex: 2 == 2 is True. 2 == 0 is False.
- The “return” is the return statement used to return a value once you reach a stopping point of a function.
- The “echo” function prints whatever values you pass to it in the HTML of the webpage.