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

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 2

I too have always found it hard to think recursively. Going through the http://learnyouahaskell.com/ recursion chapter a few times, then trying to re-implement his re-implementations has helped solidify it for me. Also, generally, learning to program functionally by carefully going through the Mostly Adequate Guide and practicing currying and composition has made me focus on solving the core of the problem then applying it in other ways.

Back to recursion...Basically these are the steps I go through when thinking of a recursive solution:

1. The recursion has to stop, so think of one or more base cases. These are the case(s) where further calls to the function are no longer necessary.
2. Think of the simplest non-base case (the recursive case), and think of how you can call the function again in a way that will result in the base case...so that the function doesn't keep calling itself. The key is focusing on the simplest non-base case. That will help your mind wrap around the problem.

So, for example, if you have to reverse a list, the base case would be an empty list or a list of one element. When moving to the recursive case, don't think about [1,2,3,4]. Instead think of the simplest case ([1,2]) and how to solve that problem. The answer is easy: take the tail and append the head to get the reverse.

I'm no haskell expert...I just started learning myself. I started with this which works.

reverse' l
  | lenL == 1 || lenL == 0 = l
  where lenL = length l
reverse' xs ++ [x]

The guard checks if it's a 1 or 0 length list and returns the original list if it is.

The recursive case happens when the list is not length 0 or 1 and gets the reverse of the tail, appending the head. This happens until the list is 1 or 0 length and you have your answer.

Then I realized you don't need the check for a singleton list, since the tail of a one element list is an empty list and I went to this which is the answer in learnyouahaskell:

reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]

I hope that helps. At the end of the day, practice makes perfect, so keep trying to solve some things recursively and you'll get it.

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.

Answer 4

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 5

Looking at Function 3:

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

Let's say you called reverse' [1,2,3] then...

1. reverse' [1,2,3] = reverse' [2,3] ++ [1]

   reverse' [2,3] = reverse' [3] ++ [2] ... so replacing in equation 1, we get:

2. reverse' [1,2,3] = reverse' [3] ++ [2] ++ [1]

   reverse' [3] = [3] and there is no xs ...

  ** UPDATE ** There *is* an xs!  The xs of [3] is [], the empty list. 

   We can confirm that in GHCi like this:

     Prelude> let (x:xs) = [3]
     Prelude> xs
     []

   So, actually, reverse' [3] = reverse' [] ++ [3]

   Replacing in equation 2, we get:

3. reverse' [1,2,3] = reverse' [] ++ [3] ++ [2] ++ [1]

   Which brings us to the base case: reverse' [] = []
   Replacing in equation 3, we get:

4. reverse' [1,2,3] = [] ++ [3] ++ [2] ++ [1], which collapses to:

5. reverse' [1,2,3] = [3,2,1], which, hopefully, is what you intended!

Maybe you can try to do something similar with the other two. Choose small parameters.
Have success!

Answer 6

Maybe the way your are presenting your issue is not the good one, I mean this is not by studding implementation of existing recursive function that you will understand how you can replicate it. I prefer to provide you an alternative way, it could be view as a methodical process which help you yo write standard skeleton of recursive call and then facilitate reasoning about them.

All your example are about list, then the first stuff when you work with list is to be exhaustive, I mean to use pattern matching.

rec_fun [] = -- something here, surely the base case
rec_fun (x:xs) = -- another thing here, surely the general case  

Now, the base case could not include recursive otherwise you will surely end up with a infinite loop, then the base case should return a value, and the best way to grasp this value is to look to the type annotation of your function.

For example :

reverse :: [a] -> [a]

Could encourage you to consider the base case as a value of type [a], as [] for reverse

maximum :: [a] -> a 

Could encourage you to consider the base case as a value of type a for maximum

Now for the recursive part, as said the function should include a call of herself.

rec_fun (x:xs) = fun x rec_fun xs 

with fun to denote the use of another function which are responsible to realize the chaining of recursive call. To help your intuition we can present it as an operator.

rec_fun (x:xs) = x `fun` rec_fun xs 

Now considering (again) the type annotation of your function (or more shortly the base case), you should be able to deduce the nature of this operator. For reverse, as its should return a list the operator is surely the concatenation (++) and so on.

If you put all this stuff together, it shouldn't be so hard to end up with the desired implementation.

Of course, as with any other algorithm, you will always need to thinks a little bit and there are no magical recipe, you must think. For example, when you know the maximum of the tail of the list, what is the maximum of the list ?