*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*.

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:

- has a string less then 2 characters then it’s a palindrom
- 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

where

a \mod b = a - b \lfloor \frac a b\rfloorfunction 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