PHP Master | Understanding Recursion

Core points

• Recursion is a problem-solving method that involves the function calling itself directly or indirectly (via a function call loop). It is especially useful when it comes to iterating through trees and lists or performing most O(n log n) sorts.
• Recursive functions must have a base case or protection clause to prevent them from calling themselves infinitely, resulting in a stack overflow error. This base example is a condition that stops the function from making further recursive calls when a specific condition is met.
• There are two types of recursion: direct recursion and indirect recursion. Direct recursion means that the function calls itself directly, while indirect recursion means that the function indirectly calls itself through another function. This article focuses on direct recursion.
• While recursion can be a powerful tool, it must be used with caution. PHP does not optimize recursive functions, and they are usually not as efficient and fast as their iterative counterparts. However, recursion may be more efficient in some cases, such as searching for or traversing uncertain depths in a file system.

In a previous post I wrote about iterators and how to use them. Today, I want to see the iterative siblings: recursion. However, before we discuss recursion, let's take a look at this code:

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

Factories are the result of a number multiplying by all positive integers smaller than that number. The function above uses a simple loop to calculate the factorial of any given number. Now let's rewrite this example like this:

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

When we call these two functions, we get the same result, but note that the second function calculates factorial by calling itself. This is called recursion.

What is recursion?

Recursive functions refer to functions that call themselves directly or through function calls loops. Recursion can also refer to a problem-solving method that first solves a smaller version of the problem and then uses that result to add some other calculations to form an answer to the original question. Typically, in the process of solving smaller versions, this approach will solve smaller versions of the puzzle, and so on, until an easy-to-solve "base example" is reached. To write a recursive function, you need to provide it with some return method, otherwise it will keep calling itself forever (or until the call stack bursts, script timed out, or memory runs out). This is called a protection clause or a base case. The simplest form of a recursive function is as follows:

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函数无限运行的基例/保护子句
        return simple value;
    }
    else {
        // 使用更简单的参数再次调用函数
        my_recursive_func(argsSimplified);
    }
}

Recursive type

When a function calls itself directly, it is called direct recursion. A function's final call to itself in a function call loop is called indirect recursion. Please check out the following example of indirect recursion:

<?php
function A($num) {
    $num -= 1;
    if($num > 0) {  
        echo "A is Calling B($num)\n";
        $num = B($num);
    }
    return $num;
}

function B($num) {
    $num -= 2;
    if($num > 0) {
        echo "B is Calling A($num)\n";
        $num = A($num);
    }
    return $num;
}

$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);

<code>Calling A(4)
A is Calling B(3)
B is Calling A(1)
Result: 0</code>

The above example is actually useless code, just to show you how a function calls itself indirectly through another function. Calling A(n>4) or B(n>4) causes a function called from another function call. It is important to know that functions can call themselves indirectly like this, but in this article we only deal with direct recursion.

A practical example

To show you the power of recursion, we will write a function that searches for keys in an array and returns the results.

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

Everything went smoothly, but note that we only iterated to the second layer of the array, so searching for "Fibonacci" in the third layer failed. If we were to search for arrays of uncertain depth, this would not be enough. We can rewrite the search as a recursive function:

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函数无限运行的基例/保护子句
        return simple value;
    }
    else {
        // 使用更简单的参数再次调用函数
        my_recursive_func(argsSimplified);
    }
}

Using recursive functions, we can search several layers of deep arrays because we don't have the depth of hardcoded functions. It just keeps running until iterates through all the values ​​in the array.

Head recursion and tail recursion

In all our examples so far, we have been using so-called header recursion. When a function calls itself, it waits for the result from the call before returning its own value. You can write a function that does not operate on the return value, but passes all required values ​​as parameters. This is called tail call (or tail recursion). This method is usually preferred because the language's runtime can sometimes optimize calls, so there is no danger of blasting the call stack, but PHP does not do so. The following is our factorial example, modified to make a tail call. Note that the result of the recursive call is returned, rather than manipulating it further.

<?php
function A($num) {
    $num -= 1;
    if($num > 0) {  
        echo "A is Calling B($num)\n";
        $num = B($num);
    }
    return $num;
}

function B($num) {
    $num -= 2;
    if($num > 0) {
        echo "B is Calling A($num)\n";
        $num = A($num);
    }
    return $num;
}

$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);

General Suggestions

Any code that can be written in iteratively can be written in recursively. However, this is not always easy to do (even wise). Recursion is excellent when it comes to iterating through trees and lists or performing most O(n log n) sorts. Recursion is more suitable than iterative methods when you need to divide repetitive problems, such as searching in a file system, and you also need to go to any subdirectory to search. Recursion works well when traversing uncertain depths. Remember that PHP does not optimize recursive functions, and even if you write them for tail calls, recursive functions are usually inefficient and slower than their iterative counterparts, although they sometimes do the job better, as in the code example above Shown. Recursion is usually the preferred alternative to iteration in functional programming, so most functional languages ​​optimize recursive functions. If you are using XDebug, be sure to check the configuration of your system. By default, you will limit 100 recursive calls, and if you exceed this limit, your script will throw a "Maximum nesting limit has been reached" error. If you need to change this setting, you can update the debug.max_nesting_level configuration value. Finally, it is best to read the explanation of stack heap and recursion causing stack overflow to understand what happens to call the stack during recursion.

Conclusion

In this article, I introduce you extensively to recursion and its comparison with iteration. I also showed you how to write recursive functions, when to write them, and why. I'm also trying to warn you about some pitfalls you might encounter when using recursion. Recursion is like this, even many experienced programmers may not use it for years, and many others have never even heard of it, which is a shame because it is a truly powerful concept. I hope that through this post I can give you enough knowledge to start writing your own recursive functions. But remember that just like using fire, you must always use this tool with caution.

Picture from Alexandre Duret-Lutz by Flickr

FAQs on Understanding Recursion in PHP (FAQ)

What is the basis example in PHP recursive function?

The basic example in PHP recursive functions is a condition that prevents the function from calling itself infinitely. It is a key part of any recursive function. Without a base case, the recursive function will call itself infinitely, resulting in a stack overflow error. In PHP, basic examples are usually defined using the "if" statement at the beginning of a function. The function checks this condition before proceeding with the recursive call. If the condition is met, the function returns a value and stops calling itself.

How do recursive functions in PHP work?

The recursive function in PHP calls itself in its own function body until a specific condition called the base case is satisfied. When a recursive function is called, it performs a specific task and then calls itself to repeat the task. This process continues until the base case is satisfied, and the function stops calling itself. Each time a function is called, a new layer is created on the call stack, storing the variables and return addresses of the function calls. Once the base case is met, the function starts to return and untie the call stack layer by layer.

Can all problems in PHP be solved using recursion?

While recursion can be a powerful tool in PHP, not all problems can or should be solved using recursion. Recursion is best suited for problems that can be broken down into smaller, more similar problems, such as traversing file directories or sorting arrays. However, if used improperly, recursion can lead to high memory usage and stack overflow errors. It is also usually slower than iterative solutions due to the overhead of function calls. Therefore, it is very important to understand the problem at hand and choose the right approach.

How to prevent stack overflow in PHP recursive functions?

Stack overflow in recursive functions can be prevented by carefully defining the basis instances that the function will eventually reach. The base case is a condition, and when this condition is met, the function stops making further recursive calls. Without a base case, the function will call itself infinitely, causing a stack overflow. It is also important to make sure that each recursive call brings the function closer to the base case to avoid infinite recursion.

What is tail recursion in PHP?

Tail recursion is a special type of recursion, where the recursive call is the last operation in the function. This means no need to keep track of previous function calls, allowing the compiler or interpreter to optimize recursion and reduce the risk of stack overflow. However, PHP itself does not support tail recursive optimization. So while you can write tail recursive functions in PHP, they are not optimized and will still consume stack space for each recursive call.

How to compare recursion with loop in PHP?

Both recursion and looping can be used to repeat a set of instructions in PHP. However, they work differently and have different advantages and disadvantages. Recursion is a powerful tool for solving complex problems that can be broken down into smaller, more similar problems. It is especially useful for traversing tasks like trees or graphs. Loops, on the other hand, are often more suitable for simple repetitive tasks. They use less memory than recursion and are unlikely to cause stack overflow.

Can I use recursion to iterate over arrays in PHP?

Yes, recursion can be a very effective way to traverse arrays (especially multidimensional arrays) in PHP. You can use a recursive function to iterate over each element in an array, and if the element itself is an array, the function can call itself to iterate over the array. This process continues until all elements are accessed. However, remember that recursion may be slower than iterative solutions and will use more memory, especially in the case of large arrays.

What is mutual recursion in PHP?

Mutual recursion refers to two or more functions being called with each other in a loop. In PHP, this means that function A calls function B, and function B calls function A. This can be a powerful tool for solving certain types of problems, but it can also be harder to understand and debug than simple recursion. As with any recursive function, it is important to define a base case to prevent infinite recursion.

How to debug recursive functions in PHP?

Debugging recursive functions in PHP can be challenging because the function calls itself multiple times. However, there are several strategies you can use. One way is to use a print statement or a debugger to track the function call and view the status of the variables in each step. Another way is to draw a recursive tree to visualize function calls. It is also important to double-check the base case and recursion case to make sure they are correct.

What are the limitations of using recursion in PHP?

While recursion can be a powerful tool in PHP, it does have some limitations. One of the main limitations is that if the recursion is too deep, there is a risk of stack overflow. This is because each recursive call adds a new layer to the call stack and the stack size is limited. Due to the overhead of function calls, recursion may also be slower than iterative solutions and will use more memory. Furthermore, recursive functions may be harder to understand and debug than iterative solutions.

The above is the detailed content of PHP Master | Understanding Recursion. For more information, please follow other related articles on the PHP Chinese website!