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 ) -- { 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] ++  -- { applying reverse }
↓
(reverse  ++ ) ++  -- { applying reverse }
↓
((reverse [] ++ ) ++ ) ++  -- { applying reverse }
↓
(([] ++ ) ++ ) ++  -- { 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 : ( ++ [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 )) -- { 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 []  -- { 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"
``````

As an example `product` function will be used during next steps.

1. define the type
``````product :: [Int] -> Int
``````
1. enumerate the cases
``````product :: [Int] -> Int
product []       =
product (n : ns) =
``````
1. define the simple cases
``````product :: [Int] -> Int
product []       = 1
product (n : ns) =
``````
1. define the other cases
``````product :: [Int] -> Int
product []       = 1
product (n : ns) = n * product ns
``````
1. 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.