Recursive Algorithms

Recursion in computer science is an approach to solve complex problems by splitting them into smaller, similar ones. Often a defined function is being applied in it’s own definition. To not end up in an infinite loop or a stack overflow, the function definition reaches a base case, where no further recursive call occurs.

Let’s have a look at some typical examples

1. Factorial

Factorial is very popular in mathematics and is encountered in many areas like combinatorics or algebra. The factorial n! of a postive integer n is the product of all postive integers less than or equal to n.

n! = n \cdot (n-1) \cdot (n-2) \cdot \dotso \cdot 2 \cdot 1

When we look closer, we see that some part of a line appears in the line before. When replace that with what we have seen before we can write

1! = 1 \newline 2! = 2 \cdot 1! \newline 3! = 3 \cdot 2! \newline 4! =4 \cdot 3! \newline 5! = 5 \cdot 4!

and come to the general notation

n! = n \cdot (n-1)!

or

n! = \begin{cases} 1 &\text{if } n = 1\\ n \cdot (n-1)! &\text{if } n > 1\end{cases}

So we can write the factorial function like

function factorial(int $n): int 
{
    if ($n === 1) { 
        return 1; 
    } 

    return $n * factorial($n - 1); 
}

Of course we could have written this method with a simple iterative approach. Normally recursion is used to solve much more complex problems, where the iterative method would come to its limit.

2. Fibonacci Numbers

In mathematics, the Fibonacci numbers form a sequence such that each number is the sum of the two preceding ones, starting from 0 and 1. The first numbers of that sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

and describe it in following formula:

fib(n) := \begin{cases} 0 &\text{if } n = 0\\ 1 &\text{if } n = 1\\ fib(n-1) + fib(n-2) &\text{if } n > 1\end{cases}

function fib(int $n): int 
{
    if ($n === 0) {

        return 0;
    }

    if ($n === 1) {

        return 1;
    }

    return fib($n - 1) + fib($n - 2);
} 

3. Check wether a string is palindrome

A palindrome is a word, sentence, verse, or even number that reads the same backward or forward. It derives from Greek roots that literally mean “running back” (palin is “again, back” and dromos “running.”)

• wow
• noon
• radar
• madam
• racecar
• my gym
• step on no pets
• no lemon no melon

The longest palindrome in English is often considered tattarrattat, coined by James Joyce in his 1922 Ulysses to imitate the sound of a knock on the door.

With the further definition that if the string is empty or only consists of 1 letter it is considered a palindrom also, we can describe the algorithm like this:

1. has a string less then 2 characters then it’s a palindrom
2. if the first and last letter differ, it’s not a palindrom, otherwise strip the first and last letter from the string and determine wether the remaining substring is a palindrom

function isPalindrom(string $str): bool 
{
    $length = strlen($str); 

    if ($length <= 1) { 

        return true;
 
    } 

    if (substr($str, 0, 1) === substr($str, -1, 1)) { 

        return isPalindrom(substr($str, 1, $length - 2));
 
    } 

    return false; 
}

4. Greatest common divisor

The greatest common divisor (gcd) of 2 integers a and b is the largest positive integer which divides both of the given integers a and b. We assume that not both of them are zero.

Euklid‘s algorithm to calculate the greatest common divisor can be described as

gcd(a,b) = \begin{cases} a &\text{if } b = 0\\ gcd(a, a\mod b) &\text{else }\end{cases}

where

a \mod b = a - b \lfloor \frac a b\rfloor

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

5. Directory Listing

A typical use case for using recursion is a directoty listing. A directory may have files and directories as subfolders. We just check if an item in the list is a directory and apply the listFiles method on them recursively.

function listFiles(string $directory, array $files = []): array 
{
    $cdir = scandir($directory);

    foreach ($cdir as $value) {

        if (!in_array($value, ['.', '..'])) {

            $path = realpath($directory . DIRECTORY_SEPARATOR . $value);

            if (is_dir($path)) {

                $files = array_merge(listFiles($path, $files));

            } else {

                $files[] = $path;
            }
        }
    }

    return $files;
}

Summary

As we have seen in these we are now able to summarize the basic idea of a recursive algorithm

Each recursive call should be applied on a smaller instance of the original problem

Eventually the calls must reach a base case which will return without any further recursive call