Another common use of recursion is implementing Greatest Common Division (GCD) of two numbers. In GCD calculation, we will continue until a remainder becomes 0. It can be expressed as follows:

Now, if we implement recursively using PHP 7, it will look like this:

function gcd(int $a, int $b): int { 
    if ($b == 0) { 
     return $a; 
    } else { 
     return gcd($b, $a % $b); 
    } 
}

Another interesting part of this implementation is that unlike a factorial, we are not returning from a base case to other steps in the call stack. The base case will return the calculated value. This is one of the optimized ways to do recursion.