What is recursion?

As I said, recursion is a solution to a big problem by breaking it down into smaller problems. In general, recursion is referred to as a call to the function itself. It may sound strange to say this, but in recursion, functions really do have to call themselves.

A chestnut

In mathematics, for example, we all know the concept of “factorial”. For example, 5 factorial is 5 times 4 times 3 times 2 times 1.

  • 5! = 5 times 4 factorial.
  • 4! = 4 times 3 factorial.
  • 3! = 3 times 2 factorial.
  • 2! = 2 times 1 factorial
  • 1! Equals 1 times 0 factorial.
  • 0! = 1

We can summarize the rule for finding n factorial, which is n factorial. = n * (n -1) !

So this is recursion. And you can see from this, we’re taking the factorial of 5 step by step and turning it into another little problem.

Properties of recursive algorithms

  • Each recursive call must be based on a small subproblem. For example, 5 factorial is 5 times 4 factorial.
  • Recursion must have a Base case. For example, the Base case of factorial is 0, and when the condition is 0, the recursion stops.
  • Avoid circular calls in recursion, otherwise the computer will eventually display stack overflow errors.
function factorial(int $n): int
{
    if ($n = 0) {
        return 1;
    }
    
    return $n * factorial($n - 1);
}
Copy the code

If we look at the code above, we can see that we have a basic condition for the solution to the factorial problem which is that we return 1 when n is 0. If it doesn’t, we return n times factorial of n, which satisfies the first and third properties of recursion. We avoid circular calls because we decompose each recursive call into a small subproblem of a larger problem. The algorithm idea above can be expressed as:

Recursion Vs iteration

The above recursive code can also be implemented using iterative methods

function factorial(int $n): int
{
    $result = 1;
    
    for ($i = $n; $i > 0; $i--) {
        $result*= $n;
    }
    
    return $result;
}
Copy the code

Why use recursion when a problem can easily be solved using iteration?

Recursion is used to deal with more complex problems, not all problems can be solved simply by iteration. Recursion uses function calls to manage the call stack, so it uses more time and memory than iterative recursion. Also, in iteration, we have a result for each step, but in recursion we have to wait until the base Case is finished before we have any result. Looking at the example above, we see that in the recursive algorithm we don’t have any variables or declarations to store the result, whereas in the iterative algorithm we use $result to store the result each time.

Fibonacci numbers

In mathematics, the Fibonacci sequence is a special sequence of integers in which each number is produced by summation of two other numbers. Here are the rules:

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

Greatest common factor

Another common problem with recursive algorithms is finding the greatest common factor of two numbers.

function gcd(int $a, int $b)
{
    if ($b == 0) {
        return $a;
    }
    
    return gcd($b, $a % $b);
}
Copy the code

Recursive type

  • Linear recursive

In each recursive call, the function calls itself only once, which is called linear recursion.

  • Binary recursive

In binary recursion, each recursive call to the function calls itself twice. The algorithm to solve the Fibonacci sequence is binary recursion, in addition to binary search, divide-and-conquer algorithm, merge sort and so on also use binary recursion.

  • Tail recursion

Tail recursion is called when a recursion returns with no waiting operations. In Fibonacci, the return value is multiplied by the return value of the previous recursion, so it is not tail recursion, and the algorithm for solving the largest common factor is tail recursion. Tail recursion is a form of linear recursion.

  • Mutually recursive

For example, each recursive call in which A() calls B() and B() calls A() is called reciprocal recursion.

  • Nested recursion

Nested recursion occurs when a recursive function calls itself recursively as an argument. A common chestnut is the Ackermann function, see the following expression.

Looking at the last line, you can see that the second argument is the recursive function itself.

The next section,

The next article will use recursion to solve some real-world development problems, such as building n-level classifications, building nested comments, traversing directory files, and so on.

More content

Directory address for PHP Basic Data Structures: github.com/… The basic data structures and algorithms are summarized using PHP syntax. There are also some basic knowledge that we tend to ignore in daily PHP development and some practical advice on specification, deployment and optimization in modern PHP development, as well as in-depth research on the characteristics of Javascript language.