Skip to main content

22.02.21 - Recursive Functions

Many functions can be defined in terms of other functions

Recursive Function​

Recursive - Functions can also be defined in terms of themselves

fac 0 = 1
fac n = n * fac(n-1)

Reasons why recursion are useful:

  • Some are simpler to define in terms of other functions (factorial)
  • Many can naturally be defined in terms of themselves
  • Properties of functions defined using recursion can be proved using the simple but powerful mathematical technique of induction

Recursion on Lists​

Recursion not restricted to numbers, can also be used to define functions on lists

Multiple Arguments​

Functions with more than one argument can also be defined using recursion 

zip :: [a] -> [b -> [(a,b)] -- Defines type
zip []    _    = [] -- Base Case -- If either lists are empty, cant merge, so return empty list
zip _    []    = [] -- Base Case  
zip (x:xs) (y:ys) = (x,y) : zip xs ys -- pair up the first values of the list

Quicksort​

Quicksort algorithm can be specified by:

  • The empty list is already sorted; - base case
  • Non empty lists can be sorted by the tail values ≤\le the head, sorting the tail values > the head, and then appending the resulting lists on either side of the head value