Recursion

Permutations

We will design a function that lists all permutations of a string.
A permutation is simply a rearrangement of the letters:
```
"eat"
"eta"
"aet"
"ate"
"tea"
"tae"
```
If a string has n letters, then the number of permutations is given by the factorial function:
```
n! = 1 x 2 x 3 x . . . x n
```
To a compute the value of a n! you could use a loop (see chapter 7), but there is also a recursive solution:
```
n! = (n - 1)! x n 
```
It is customary to define
```
1! = 1
0! = 0
```

You can therefore implement a recursive factorial function as follows:

int factorial(int n)
{
   if (n == 0) return 1;
   int smaller_factorial = factorial(n - 1);
   int result = smaller_factorial * n;
   return result;
}

previous | start | next