Understanding recursion in Haskell

Question

I am having a very difficult time understand how to think about problems in a recursive way, and solve them using Haskell. I have spent hours of reading trying to wrap my head around recursion. The explanation I most often get from people who understand it is never clear and is something like "you pass a function, the name of the function as the argument, the function will then execute, solving a small piece of a the problem and calling the function again and again until you hit the base case".

Can someone please be kind enough, and walk me through the thought process of these three simple recursive functions? Not so much the functionality of them, but how the code, ends up executing and solving the problem, recursively.

Many thanks in advance!

Function 1

maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:rest) = max x(maximum' rest)

Function 2

take' n _  
    | n <= 0   = []  
take' _ []     = []  
take' n (x:xs) = x : take' (n-1) xs  

Function 3

reverse' [] = []  
reverse' (x:xs) = reverse' xs ++ [x]  

Answer 1

Guidelines

When trying to understand recursion, you may find it easier to think about how the algorithm behaves for a given input. It's easy to get hung up on what the execution path looks like, so instead ask yourself questions like:

• What happens if I pass an empty list?
• What happens if I pass a list with one item?
• What happens if I pass a list with many items?

Or, for recursion on numbers:

• What happens if I pass a negative number?
• What happens if I pass 0?
• What happens if I pass a number greater than 0?

The structure of a recursive algorithm is often just a matter of covering the above cases. So let's see how your algorithms behave to get a feel for this approach:

maximum'

maximum []     = error
maximum [1]    = 1
maximum [1, 2] = 2

As you can see, the only interesting behaviour is #3. The others just ensure the algorithm terminates. Looking at the definition,

maximum' (x:rest) = max x (maximum' rest)

Calling this with [1, 2] expands to:

maximum [1, 2]    ~ max 1 (maximum' [2])
                  ~ max 1 2

maximum' works by returning a number, which this case knows how to process recursively using max. Let's look at one more case:

maximum [0, 1, 2] ~ max 0 (maximum' [1, 2]) 
                  ~ max 0 (max 1 2)
                  ~ max 0 2

You can see how, for this input, the recursive call to maximum' in the first line is exactly the same as the previous example.

reverse'

reverse []     = []
reverse [1]    = [1]
reverse [1, 2] = [2, 1]

Reverse works by taking the head of the given list and sticking it at the end. For an empty list, this involves no work, so that's the base case. So given the definition:

reverse' (x:xs) = reverse' xs ++ [x] 

Let's do some substitution. Given that [x] is equivalent to x:[], you can see there are actually two values to deal with:

reverse' [1]    ~ reverse' [] ++ 1
                ~ []          ++ 1
                ~ [1]

Easy enough. And for a two-element list:

reverse' [0, 1] ~ reverse' [1] ++ 0
                ~ [] ++ [1] ++ 0
                ~ [1, 0]

take'

This function introduces recursion over an integer argument as well as lists, so there are two base cases.

1. What happens if we take 0-or-less items? We don't need to take any items, so just return the empty list.

   take' n _   | n <= 0    = [] 
   
   take' -1 [1]  = []
   take' 0  [1]  = []
   

2. What happens if we pass an empty list? There are no more items to take, so stop the recursion.

   take' _ []    = []
   
   take' 1 []    = []
   take  -1 []   = []
   

The meat of the algorithm is really about walking down the list, pulling apart the input list and decrementing the number of items to take until either of the above base cases stop the process.

take' n (x:xs) = x : take' (n-1) xs

So, in the case where the numeric base case is satisfied first, we stop before getting to the end of the list.

take' 1 [9, 8]  ~ 9 : take (1-1) [8]
                ~ 9 : take 0     [8]
                ~ 9 : []
                ~ [9]

In the case where the list base case is satisfied first, we run out of items before the counter reaches 0, and just return what we can.

take' 3 [9, 8]  ~ 9 : take (3-1) [8]
                ~ 9 : take 2     [8]
                ~ 9 : 8 : take 1 []
                ~ 9 : 8 : []
                ~ [9, 8]

Answer 2

Recursion is a strategy to apply a certain function to a set. You apply the function to the first element of that set, then you repeat the process to the remaining elements.

Let's take an example, you want to double all the integers inside a list. First, you think about which function should I use? Answer -> 2*, now you have to apply this function recursively. Let's call it apply_rec, so you have:

apply_rec (x:xs) = (2*x)

But this only changes the first element, you want to change all the elements on the set. So you have to apply the apply_rec to the remaining elements as well. Thus:

apply_rec (x:xs) = (2*x) : (apply_rec xs)

Now you have a different problem. When does apply_rec ends? It ends when you reach the end of the list. In other words [], so you need to cover this case as well.

apply_rec [] = []
apply_rec (x:xs) = (2*x) : (apply_rec xs)

When you reach the end you do not want to apply any function, hence the function apply_rec should "return" [].

Let's see the behavior of this function in a set = [1,2,3].

1. apply_rec [1,2,3] = (2 * 1) : (apply_rec [2,3])
2. apply_rec [2,3] = 2 : ((2 * 2) : (apply_rec [3]))
3. apply_rec [3] = 2 : (4 : ((2 * 3) : (apply_rec []))
4. apply_rec [] = 2 : (4 : (6 : [])))

resulting in [2,4,6].

Since you probably do not know very well recursion, the best thing is to start with simpler examples than those that you have presented. Take also a look learn recursion and at this Haskell Tutorial 3 - recursion.

Answer 3

You ask about "thought process", presumably of a programmer, not a computer, right? So here's my two cents:

The way to think about writing some function g with recursion is, imagine that you have already written that function. That's all.

That means you get to use it whenever you need it, and it "will do" whatever it is supposed to be doing. So just write down what that is - formulate the laws that it must obey, write down whatever you know about it. Say something about it.

Now, just saying g x = g x is not saying anything. Of course it is true, but it is a meaningless tautology. If we say g x = g (x+2) it is no longer a tautology, but meaningless anyway. We need to say something more sensible. For example,

g :: Integer -> Bool
g x | x<=0 = False
g 1 = True
g 2 = True

here we said something. Also,

g x = x == y+z  where
          y = head [y | y<-[x-1,x-2..], g y]    -- biggest y<x that g y
          z = head [z | z<-[y-1,y-2..], g z]    -- biggest z<y that g z

Have we said everything we had to say about x? Whether we did or didn't, we said it about any x there can be. And that concludes our recursive definition - as soon as all the possibilities are exhausted, we're done.

But what about termination? We want to get some result from our function, we want it to finish its work. That means, when we use it to calculate x, we need to make sure we use it recursively with some y that's defined "before" x, that is "closer" to one of the simplest defined cases we have.

And here, we did. Now we can marvel at our handiwork, with

filter g [0..]

Last thing is, in order to understand a definition, don't try to retrace its steps. Just read the equations themselves. If we were presented with the above definition for g, we'd read it simply as: g is a Boolean function of a number which is True for 1, and 2, and for any x > 2 that is a sum of its two preceding g numbers.