## 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. A visual form of recursion known as Droste-Effect where a picture is recursively appearing within itself. (Pink Floyd‘s 4th album Ummagumma)

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$

$1! = 1 \newline 2! = 2 \cdot 1\newline 3! = 3 \cdot 2 \cdot 1\newline4! = 4 \cdot 3 \cdot 2 \cdot 1\newline\newline5! = 5 \cdot 4 \cdot 3 \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