### Decomposing a problem using recursion

Following on from finding the factorial of a number, here is the same problem solved in Python using recursion.

#### Find the factorial of a number

The mathematical definition of `n!`

can be given as:

```
n! = n x (n-1)! where n > 1
n! = 1 where n = 0
```

This is a *recursive* definition with a *base case*.

The *recursive* definition defines factorial in terms of itself. This definition can be applied several times *recursively* to get the answer.

The definition also includes a *base case*, which tells you when to stop. This base case is crucial. Without it the recursive definition would repeat endlessly.

Here is an example:

```
4! = 4 x 3! apply the recursive definition
4! = 4 x 3 x 2! apply the recursive definition again
4! = 4 x 3 x 2 x 1! apply the recursive definition again
4! = 4 x 3 x 2 x 1 x 0! apply the recursive definition again
4! = 4 x 3 x 2 x 1 x 1 apply the base case
4! = 24
```

So, a recursive function is always defined in terms of itself and some base case where the final value is returned.

We can do this in Python.

#### Give the function a sensible name

```
factorial
```

#### Work out the inputs to the function and give them sensible names

```
n
```

#### Write out the first line of the function definition, including the arguments

```
def factorial(n):
```

#### Decide on the *base case*

```
n == 0
```

#### Add a test for the *base case*

```
print factorial(0) == 1
```

#### Add a return value for your function using the value that your test is expecting

```
def factorial(n):
if n == 0:
return 1
print factorial(0) == 1
```

#### Run your test and check that it passes

```
True
```

#### Decide on the next case

```
n == 1
```

In the case of a function like `factorial`

, which computes a number that is part of a sequence, it is easy to decide on the each successive test case. In this case, the next value is *n! = 1*, where `n == 1`

.

#### Add another test using the next case

```
print factorial(1) == 1
```

#### Decide on whether you are ready to compute a recursive solution

Sometimes more than one base case is required before the general recursive solution can be found. But in this case the problem is a simple one:

*For any value of n, multiply n by each predecessor until you reach the base case.*

#### Sketch out the framework of a possible solution

A general recursive solution often requires that:

```
some function of n
```

is combined with:

```
some operator
```

to a recursive call to the original function with

```
some successor to n
```

This schema will not work in every case, but is a sensible starting point.

This is the heart of recursive programming. You are calling a function *within the function itself*. That is, you are calling it *recursively*.

This is a very important and powerful technique in programming.

#### Attempt to fill in the blanks

This is where the big intuitive leap is required.

```
n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1
```

From the form of the solution to n!, probably the first thing to see clearly is that:

```
some operator of n = *
```

The second thing to see is that:

```
some function of n = n
```

This comes from the first term in the series.

The final thing to see is that:

```
some successor to n = n - 1
```

Which should be clear from the way in which each term of n! is one less than its predecessor.

#### Now attempt a general solution to the problem

```
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
^ ^ ^
function of n operator successor to n
```

#### Add more test cases

```
print factorial(0) == 1
print factorial(1) == 1
print factorial(2) == 2
print factorial(3) == 6
print factorial(4) == 24
```

#### Run the tests

```
True
True
True
True
True
```

Which confirm that this is probably a good general solution.