7 minutes

# Exploring Haskell: Recursive Functions

In Haskell recursion serves as the basic mechanism for looping.

## Basic Concepts

It is possible to define a function which can call itself. This is the basic principle behind recursion.

```
-- Without recursion
fac :: Int -> Int
fac n = product [1 .. n]
-- With recursion
fac :: Int -> Int
fac 0 = 1
fac n = n * fac (n - 1)
-- Which can be traced as:
fac 3 -- { applying fac }
↓
3 * fac 2 -- { applying fac }
↓
3 * (2 * fac 1) -- { applying fac }
↓
3 * (2 * (1 * fac 0)) -- { applying fac }
↓
3 * (2 * (1 * 1)) -- { applying * }
↓
6
```

Same for the multiplication function, which can be defined via multiple additions.

```
(*) :: Int -> Int -> Int
m * 0 = 0
m * n = m + (m * (n - 1))
4 * 3 -- { applying * }
↓
4 + (4 * 2) -- { applying * }
↓
4 + (4 + (4 * 1)) -- { applying * }
↓
4 + (4 + (4 + (4 * 0))) -- { applying * }
↓
4 + (4 + (4 + 0)) -- { applying + }
↓
12
```

## Recursion on Lists

Previously mentioned `product`

function can be defined with recursion.

```
product :: Num a => [a] -> a
product [] = 1
product (n : ns) = n * product ns
product [2,3,4] -- { applying product }
↓
2 * product [3,4] -- { applying product }
↓
2 * (3 * product [4]) -- { applying product }
↓
2 * (3 * (4 * product [])) -- { applying product }
↓
2 * (3 * (4 * 1)) -- { applying * }
↓
24
```

Function `length`

can be defined in a similar way.

```
length :: [a] -> Int
length [] = 0
length (_ : xs) = 1 + length xs
```

Defining `reverse`

can be done this way.

```
reverse :: [a] -> [a]
reverse [] = []
reverse (x : xs) = reverse xs ++ [x]
reverse [1,2,3] -- { applying reverse }
↓
reverse [2,3] ++ [1] -- { applying reverse }
↓
(reverse [3] ++ [2]) ++ [1] -- { applying reverse }
↓
((reverse [] ++ [3]) ++ [2]) ++ [1] -- { applying reverse }
↓
(([] ++ [3]) ++ [2]) ++ [1] -- { applying ++ }
↓
[3,2,1]
```

And `++`

operation.

```
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x : xs) ++ ys = x : (xs ++ ys)
[1,2,3] ++ [4,5] -- { applying ++ }
↓
1 : ([2,3] ++ [4,5]) -- { applying ++ }
↓
1 : (2 : ([3] ++ [4,5])) -- { applying ++ }
↓
1 : (2 : (3 : ([] ++ [4,5]))) -- { applying ++ }
↓
1 : (2 : (3 : [4,5])) -- { list notation }
↓
[1,2,3,4,5]
```

Here’s a recursive function that inserts values to an ordered list.

```
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y : ys) | x <= y = x : y : ys
| otherwise = y : insert x ys
insert 3 [1,2,4,5] -- { applying insert }
↓
1 : insert 3 [2,4,5] -- { applying insert }
↓
1 : 2 : insert 3 [4,5] -- { applying insert }
↓
1 : 2 : 3 : [4,5] -- { list notation }
↓
[1,2,3,4,5]
```

Using previously defined function creating insertion sort becomes easy.

```
isort :: Ord a => [a] -> [a]
isort [] = []
isort (x : xs) = insert x (isort xs)
isort [3,2,1,4] -- { applying isort }
↓
insert 3 (insert 2 (insert 1 (insert 4 []))) -- { applying insert }
↓
insert 3 (insert 2 (insert 1 [4])) -- { applying insert }
↓
insert 3 (insert 2 [1,4]) -- { applying insert }
↓
insert 3 [1,2,4] -- { applying insert }
↓
[1,2,3,4]
```

## Multiple Arguments

For example library function `zip`

takes two lists and produces a list of pairs.

```
zip :: [a] -> [b] -> [(a, b)]
zip [] _ = []
zip _ [] = []
zip (x : xs) (y : ys) = (x, y) : zip xs ys
zip ['a','b','c'] [1,2,3,4] -- { applying zip }
↓
('a',1) : zip ['b','c'] [2,3,4] -- { applying zip }
↓
('a',1) : ('b',2) : zip ['c'] [3,4] -- { applying zip }
↓
('a',1) : ('b',2) : ('c',3) : zip [] [4] -- { applying zip }
↓
('a',1) : ('b',2) : ('c',3) : [] -- { list notation }
↓
[('a',1), ('b',2), ('c',3)]
```

In a similar way the `drop`

function is defined which removes a given number of elements from a list.

```
drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop _ [] = []
drop n (_ : xs) = drop (n - a) xs
```

## Multiple Recursion

It is also possible to use recursive function multiple times.

```
-- Get fibonacci at n-th positions
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 2) + fib (n - 1)
```

Quicksort also demonstrates how multiple recursions occur inside a single function.

```
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x : xs) = qsort smaller ++ [x] ++ qsort larger
where
smaller = [ a | a <- xs, a <= x ]
larger = [ b | b <- xs, b > x ]
```

## Mutual Recursion

Functions can also be defined recursively in terms of each other.

```
even :: Int -> Bool
even 0 = True
even n = odd (n - 1)
odd :: Int -> Bool
odd 0 = False
odd n = even (n - 1)
even 4 -- { applying even }
↓
odd 3 -- { applying odd }
↓
even 2 -- { applying even }
↓
odd 1 -- { applying odd }
↓
even 0 -- { applying even }
↓
True
```

Another pair of functions `evens`

and `odds`

can be defined similarly.

```
evens :: [a] -> [a]
evens [] = []
evens (x : xs) = x : odds xs
odds :: [a] -> [a]
odds [] = []
odds (_ : xs) = evens xs
evens "abcde" -- { applying evens }
↓
'a' : odds "bcde" -- { applying odds }
↓
'a' : evens "cde" -- { applying evens }
↓
'a' : 'c' : odds "de" -- { applying odds }
↓
'a' : 'c' : evens "e" -- { applying evens }
↓
'a' : 'c' : 'e' : odds [] -- { applying odds }
↓
'a' : 'c' : 'e' : [] -- { string notation }
↓
"ace"
```

## Advice on Recursion

As an example `product`

function will be used during next steps.

- define the type

```
product :: [Int] -> Int
```

- enumerate the cases

```
product :: [Int] -> Int
product [] =
product (n : ns) =
```

- define the simple cases

```
product :: [Int] -> Int
product [] = 1
product (n : ns) =
```

- define the other cases

```
product :: [Int] -> Int
product [] = 1
product (n : ns) = n * product ns
```

- generalize and simplify

```
product :: Num a => [a] -> a
product [] = 1
product (n : ns) = n * product ns
```

Recursion is an important milestone to reach and understand. End.