I recently chatted with someone about functional programming and why you would not want to have a look at it these days (something I cannot understand at all 😉 ). Aside from the usual stuff like “to ivory tower”, “to abstract”, “to much math”, “to different” and so on I was told:

I just don’t understand the recursive stuff.

To be honest I was a bit shocked.

There in front of me was a *coder* who did not understand recursion – really?

Just look at posts like Why Can’t Programmers .. Programm? – there might be a problem here.

In my opinion recursion is not just *the functional programmers goto* or a *pure mans loop* – it’s a way (if not *the* way) to think about and solve problems. It’s the Divide et impera of our trade.

Yeah of course you should try to avoid writing your own recursive code – not because recursion is bad, harmful or complicated but because you usually just reinvent the wheel (most likely you can use an catamorphism or another higher-order-function that is already there instead).

But no matter what: You should be able to solve a problem using recursive thinking – it’s a key-ability to have as a (good) programmer.

Let me give you the classic example:

### the tower of hanoi

I think this is sufficient infamous (it’s used in a *lot* of games and it seems that it still frustrates people) but if you really don’t know it go on and have a look at the Wikipedia article.

Even if you have absolutely no clue how to solve it recursive thinking will give you a solution almost for free:

- Dr. Evil: “You there! Can you get
`n`

disks from one peg to the other?” - Minion: “Sorry, I have no clue how to do this boss.”
- Dr. Evil: “
*sigh*… What if**I**can*magically*move`n-1`

disks from one peg to another for you – could you*then*deal with the last one yourself?” - Minion: “Err of course boss – if you move all but the big disks on the third peg for me, I could move the big one to the target-peg. If you then
*kindly*move the other stack again …” - Dr. Evil: “Ok …
**MiniMe**come here! I need you to move`n-2`

disks for me …”

That’s it that is all there is to say about recursion: you just pretend to know how to do the *smaller* problem and go on to solve the trivial stuff – the rest is **magic**.

Of course we have to translate this into programming constructs – *Dr. Evil* will be a function and instead of asking *MiniMe* we use recursive calls. A simple **Haskell** implementation could look like this:

data Peg = A | B | C deriving (Show, Eq) type Move = (Peg, Peg) hanoi :: Integer -> [Move] hanoi n = move n A B C where move 0 _ _ _ = [] move m src dest temp = move (m-1) src temp dest ++ [(src, dest)] ++ move (m-1) temp dest src

and here is a sample run of this:

λ> hanoi 3 [(A,B),(A,C),(B,C),(A,B),(C,A),(C,B),(A,B)]

### ok – where can you learn this?

Here are some options:

– Get yourself a introduction on algorithms.

– Look at problem sites like HackerEarth, CodeWars, ..

– Look for “Interview questions” (there are books, blogs, …) – many of those questions deal with recursion or can easily be solved using recurision

**or**

– **Learn a functional programming language**: one of the basic data-structures in FP (the list) is recursive and a good introduction will ask you to write plenty of recursive functions.

Of course you can just drop me a message – if some of you are interested I might look around and provide some nice exercises…