# 5 step process to write recursive functions

Writing a recursive function takes some practice. Hutton recommends a 5-step process for beginners for writing recursive functions. I am finding the process very useful to systematically think through the problem so I thought to take a note.

## Steps

- Define type
- List cases
- Define simple case(s)
- Define other case(s)
- Generalize and simplify

## For example…

### sum

Calculate `sum`

of a list of numbers:

- Define
**type**- let's define the sum initially for integers only:

```
sum :: [Int] -> Int
```

**List**cases - here we look at the argument(s) and see what are possible cases. For`sum`

, we have one argument - a list. So the cases will be empty list and non-empty list:

```
sum [] =
sum (x:xs) =
```

- Define
**simple case**- for the empty list, sum is 0 since 0 is identity for sum. This often is the*base*case.

```
sum [] = 0
sum (x:xs) =
```

- Define
**other cases**- this often is the recursive case. Here we need to think about how sum, x, xs and any other library function(s) can be used to handle this case. For sum, it is the addition of`x`

and`sum`

of`xs`

:

```
sum [] = 0
sum (x:xs) = x + sum xs
```

- Now can we
**generalize**the type? In this case, addition can be applied to numbers of any type and not just integers, so we can modify the type:

```
sum :: Num a => [a] -> a
sum [] = 0
sum (x:xs) = x + sum xs
```

### take

`take`

a given number of elements from the start of a list:

- Define
**type**- here we realize that`take`

can be applied to list of any type:

```
take :: Int -> [a] -> [a]
```

**List**cases - since there are two arguments, an Int and a list, there are four possible cases:

```
take 0 [] =
take n [] =
take 0 (x:xs) =
take n (x:xs) =
```

- Define
**simple case**- taking 0 elements from any list should give us the empty list. Let's also propose that taking n elements from an empty list gives an empty list too:

```
take 0 [] = []
take n [] = []
take 0 (x:xs) = []
take n (x:xs) =
```

- Define
**other cases**- taking n elements from a non-empty list is equivalent to head consed to taking (n-1) elements from tail:

```
take 0 [] = []
take n [] = []
take 0 (x:xs) = []
take n (x:xs) = x : take (n-1) xs
```

- Now can we
**generalize**the type? Well, the type is already general, but we note from the above cases that when we take 0 elements, we always get an empty list, so we can use a wild-card pattern to combine the two cases. We can also replace n when the list is empty by wild-card since n is never used in defining that case.

```
take :: Int -> [a] -> [a]
take 0 _ = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
```

### last

Select the `last`

element of a non-empty list:

- Define
**type**- can again be defined as a list of any type:

```
last :: [a] -> a
```

**List**cases - a singleton and a non-empty list with two or more elements:

```
last [x] =
last (x:xs) =
```

- Define
**simple case**- a list with single element should return that element:

```
last [x] = x
last (x:xs) =
```

- Define
**other cases**- all other lists throw the head away and apply the function to the tail:

```
last [x] = x
last (x:xs) = last xs
```

- Generalize and simplify - no further simplification is needed here:

```
last :: [a] -> a
last [x] = x
last (x:xs) = last xs
```