What is Recursion?

Recursion is the process of repeating items in a self-similar way. Matryoshka dolls are a good example of recursion.

In Haskell, the most important data structure is defined in a recursive way. A list is either empty or it is a value followed by a list.

  data [a] = [] | a : [a]

This is also why lists in Haskell can be infinite! Finite lists always require an empty list ([]) at the end.

The same principle can be applied to functions. Recursion is, if a function is defined in terms of itself.

  factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

Progress and Controlling

A recursive function must make progress towards a base case. If the base case is never reached, the function will never terminate.

  countFromTo :: Int -> Int -> [Int]
countFromTo from to | from < to = from : (countFromTo (from+1) to) -- count upwards towards to
                    | from > to = from : (countFromTo (from-1) to) -- count downwards towards to
                    | otherwise = [to] -- base case

If a function requires some preparation before the recursive call, it is common to define a helper function.

  gcd :: (Integral a) => a -> a -> a
gcd 0 0 = error "gcd 0 0 is undefined" gcd x y = gcd' (abs x) (abs y)
  where gcd' a 0 = a
        gcd' a b = gcd' b (a `rem` b)

Mutual Recursion

Mutual recursion is a special case of recursion, where two or more functions are defined 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)

Tail Recursion

A function is tail recursive, if the recursive call is the last thing the function does (outermost call). See the difference between the two implementations of sum below.

  sum :: Num a => [a] -> a -- not tail recursive sum [] = 0
sum (i:is) = i + sum is -- addition is the last thing the function does

sum :: Num a => [a] -> a -- tail recursive sum l = sum' 0 l
  where sum' acc [] = acc
        sum' acc (i:is) = sum' (i+acc) is -- tail call

Loops vs Recursion

Every loop can be expressed as a recursive function and vice versa.

  • Loops are controlled by a variable that changes with each iteration
  • The loops condition is the negation of the base case
  • The loops body is the recursion call
  int sum(int n) {
    int sum = 0;
    while(n > 0) {
        sum += n;
        n--;
    }
    return sum;
}
  
  sum :: Int -> Int
sum 0 = 0
sum n = n + sum (n-1)