you should be able to think recursively

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

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…