Introduction

In programming, we often want to repeat the same action multiple times, and this concept is called looping. Imperative languages have syntax for defining loops in their programs (usually in forms of for and while), and programming without loops is almost unimaginable. However, in Haskell, there is no such syntax for loops, and the basic mechanism for looping is recursion.
Recursive functions are those that are defined in terms of themselves, i.e. the function body includes a call to the function itself. That means a function could call itself over and over again without stopping, creating an infinite loop. This is why when we define recursive functions, we usually include a special pattern that, when matched, does not call the function any more but returns some value instead – this pattern is called the base case, while patterns that do call the function again are called recursive cases. Let's consider a simple function that calculates the sum of all natural numbers up to n:
1
sumN :: Int -> Int
2
sumN 0 = 0 -- base case
3
sumN x = x + sumN (x - 1) -- recursive case
Copied!
That is, the sum of all natural numbers up to zero is zero, and for any other integer x, it can be defined as that number x plus the sum of all natural numbers up to x - 1. Let's take a closer look at what the actual execution looks like:
1
sumN 4
2
= 4 + sumN 3
3
= 4 + 3 + sumN 2
4
= 4 + 3 + 2 + sumN 1
5
= 4 + 3 + 2 + 1 + sumN 0
6
= 4 + 3 + 2 + 1 + 0 -- the base case stops further looping
7
10
Copied!
Recursion is very powerful in Haskell when it is combined with lists. In fact, the map function we defined with a list comprehension is actually defined with recursion in the Prelude:
1
map _ [] = []
2
map f (x:xs) = f x : map f xs
Copied!
Like before, we have a base case in which we do not care about the function that is passed to map as the list it is supposed to operate on is empty and we simply return []. The recursive case, however, applies the function to x (the head of the list) and joins the result with the result of the recursive call on the remainder of the list (the tail of the list).

Higher-order Functions - Previous

The filter Function

Next - Recursion

4 Steps to Defining Recursive Functions

Last modified 1yr ago

Copy link