Recursion is a challenging concept for beginners in web programming as it is used in applications such as recursive menus and hierarchical categories. However, not many people truly understand this algorithm. Therefore, in this basic PHP series, we will explore recursion in more detail.

The content includes:

• What is recursion?
• Linear recursion
• Binary recursion
• Mutual recursion
• Recursion elimination

1. What is a recursive algorithm?

Recursion is highly related to mathematics. Let’s take a brief look back at mathematics. A property in mathematics is called recursive if it involves a class of objects with similar properties and a relationship between them. The result of step 1 becomes a component of step 2, step 2 becomes a component of step 3, and so on.

For example: My father is Mr. A, my grandfather is Mr. B, and so on. Through this recursive process, we can find the origin of my family (excuse the simplicity), and this can be considered a recursive program to determine my family’s origin. Recursive algorithms can also be called divide-and-conquer methods (breaking down the problem into smaller parts and then combining them for easier solving).

To use recursion, you must know how to write a function because each recursive call is the function calling itself. A recursive program must have a base case, as without it, the program will call itself indefinitely (infinite loop). For example, when calculating the sum from 1 to n, the base case is when n is reached and no further calculation is needed. If we calculate from n down to 1, the base case is when n = 1.

2. Linear Recursion

This type of recursion involves the recursive function calling itself only once.

For example: Given n = 100, calculate the sum of numbers from 1 to 100.

If we use a loop, it is straightforward. We iterate from 1 to 100, accumulating the sum in each iteration. The solution with a loop is as follows:

<?php 
	function calculateSum($n){
	    $sum = 0;
	    for ($i = 1; $i <= $n; $i++){
	        $sum += $i; // accumulate the sum in each iteration
	    }
	    return $sum;
	}
?>

With the recursive algorithm, the idea is that in each recursive call, we take the number and add it to the function itself, passing the number decreased by 1 as an argument. The base case is when the number reaches 1, stopping the recursion and returning the result. To analyze it further, each recursive step is equivalent to one iteration, and accumulating the sum of each recursive step is equivalent to accumulating the sum of each iteration, resulting in the same solution as the loop above.

<?php
	function calculateSum($n){
	    if ($n == 1){ return $n; }
	    return $n + calculateSum($n-1);
	}
	echo calculateSum(100);
?>

In this recursive algorithm, the function calls itself only once (with the code segment calculateSum($n-1)). In each recursive step, the value of $n is added to the result of calculateSum($n-1). This recursion continues until the variable $n passed to the function equals 1, which stops the recursion. The problem can be visualized as follows:

The variable $n passed in is 100, and the return value is 100 + recursive step 2 with the argument as follows: calculateSum(100-1). This process continues, where each recursive step is the value passed in plus the result of the next recursive step.

The addition flow is as follows: 100 + (100-1 = 99) + (99-1 = 98) + …. + (2-1 = 1) <=> 100 + 99 + 98 + …. + 1

3. Binary Recursion

Binary recursion is a type of recursion where the function calls itself two times.

Example: Output the 100th element of the Fibonacci sequence.

The Fibonacci sequence is a sequence that starts with 1 and continues up to the nth element, where each element is the sum of the two preceding elements. For example, the first 8 elements of the Fibonacci sequence are: 1 – 1 – 2 – 3 – 5 – 8 – 13 – 21.

In the Fibonacci sequence, the first and second elements have a value of 1. This is also the termination condition for the sequence.

Solution:

<?php
	// Function to calculate the value of the nth element in the Fibonacci sequence
	function Fibonacci($n){
	    if ($n <= 2){
	        return 1;
	    } else {
	        return (Fibonacci($n - 2) + Fibonacci($n - 1));
	    }
	}
	  
	// Test with input 100
	echo Fibonacci(100);
?>

In this solution, the function Fibonacci calculates the value of the nth element in the Fibonacci sequence. If the value of n is less than or equal to 2, the function returns 1, which is the base case. Otherwise, it recursively calls itself with the arguments $n - 2 and $n - 1, and returns the sum of the two recursive calls. The recursion continues until the base case is reached. Finally, we test the function by passing in 100 and output the result.

4. Nonlinear Recursion

Nonlinear recursion refers to a type of recursion in which the function uses a loop to call itself.

Example: Calculate the 8th element of a sequence using the following formula:

The meaning of the sequence is as follows:

• If n is less than 6, return n itself.
• If n is greater than or equal to 6, return the sum of all numbers from 1 to n-1, with each number calculated according to the same rule. In other words, if we have a function called “calculate” and input the value 6, the sequence will be calculated as follows: calculate(5) + calculate(4) + calculate(3) + calculate(2) + calculate(1).

Solution:

<?php
	function calculate($n){
	    // If n < 6, return n itself
	    if ($n < 6){
	        return $n;
	    } else {
	        // Otherwise, calculate the sum from 1 to n-1, and for each element, call the function itself
	        $sum = 0;
	        for ($i = 1; $i < $n; $i++){
	            $sum += calculate($n - $i);
	        }
	        return $sum;
	    }
	}

	echo calculate(6);
?>

In this solution, the function calculate calculates the value of the nth element in the sequence. If the value of n is less than 6, the function returns n itself. Otherwise, it initializes a variable sum to 0 and iterates from 1 to n-1 using a loop. In each iteration, it adds the result of calculate($n - $i) to sum. This recursive call continues until the base case (n < 6) is reached. Finally, we test the function by passing in 6 and output the result.

5. Recursive Mutualism

Just by the name, we can understand the concept to some extent. Recursive mutualism refers to recursion where a function A calls another function B, and within function B, it calls function A. They call each other, hence the term “mutualism.”

Similar to the other types of recursion mentioned earlier, if both functions A and B do not have a base case, it can lead to infinite loops, which can be dangerous, so you need to be careful.

Example: Calculate the value of the following sequence:

We can see that both recursive functions call each other, and each function has a base case. At this point, I hope I don’t need to explain the meaning of these two functions anymore. Based on the structure of these two functions, I have a solution as follows:

<?php
	// Recursive function U
	function U($n){
	    if ($n < 5){ // base case
	        return $n;
	    } else {
	        return U($n - 1) + G($n - 2);
	    }
	}

	// Recursive function G
	function G($n) {
	    if ($n <= 8){ // base case
	        return $n - 3;
	    } else {
	        return U($n - 1) + G($n - 2);
	    }
	}

	// Call the functions

	echo G(12);
?>

6. De-Recursion

Recursive algorithms are powerful, but they can be computationally expensive. Therefore, people often seek alternative algorithms to replace recursion. However, in practice, there is no definitive algorithm for this, meaning not every problem can be effectively transformed. And this part is a process, so I don’t have the time or expertise to solve all recursive problems. As you saw in the example of linear recursion, I used a for loop to calculate the sum, which is a way to de-recursive.

7. Conclusion

Recursive algorithms can be challenging, don’t you think so? To fully grasp them, you need to practice a lot. I hope this article serves as a foundation for those of you passionate about exploring algorithms. In the next article, we will learn about another sorting algorithm called the bubble sort algorithm.