So I spent a decent chunk of today trying to refresh my memory on recursion. The concept itself made sense to me but being able to write recursive functions was another thing altogether.

The way recursion works in my head is kind of like the movie Inception – multiple dreams within dreams, but instead of dreams we’re talking about functions. The top/final/base level (I’ll refer to it as the base level for now) has a puzzle. But you need a clue from the next level to solve it. But then that level also has a puzzle, and you need to go to the *next* level to find a clue for that. And you keep going down until you finally find a clue! Then you go back up a level, use the clue to solve the puzzle, get another clue! Go up another level, use this clue to solve the next puzzle, get another clue! When you finally make your way back up to the base level, you can solve the whole puzzle! Huzzah! I’ve used my beautiful artistic skills to help explain this visually too 😛

I found a great coded example in The Bastards Book of Ruby which helped, but was still a bit massive for me to wrap my head around. I simplified the code and ran it through the Python Tutor Ruby visualiser (yes, Python tutor has visualisers in several languages other than python. Go figure).  The code I ran is below, and I’m going to try and explain it in English too!  It might help to go read the original explanation of the problem, but the essence is – given a pile of rocks with different weights, how can we determine the heaviest rock?

As mentioned earlier, this code was adapted ever so slightly from The Bastards Book of Ruby. The only changes I made were to replace the randomly generated 30-rock array with a pre set 8-rock array. This cut the visualiser’s steps to work through from 280 down to 45 – much more manageable! My code is below – I highly recommend running it through the visualiser yourself to see what I’m talking about!

1 def rock_judger(rocks_arr)    
2    if rocks_arr.length <= 2  # the base case
3      a = rocks_arr[0]
4      b = rocks_arr[-1]
5    else
6      a = rock_judger(rocks_arr.slice!(0,rocks_arr.length/2))
7      b = rock_judger(rocks_arr)
8    end    
9    
10    return a > b ? a : b
11 end
12
13 
14 rocks = [199, 94, 31, 179, 173, 14, 54, 116]
15 puts "Heaviest rock is: #{rock_judger(rocks)}"

So the first thing that attempts to run is the ‘puts’ on line 15, but of course this calls our rock_judger method on the rocks array.

The first if statement looks at the length of ‘rocks’. If it was only two it knows it could solve the problem right now. Unfortunately we have 8 rocks in our array so we split the rocks array in two,  and call the rock_judger method on each half of the array. The fact that we are calling our method from inside the method is what makes this method recursive – it calls itself.

So, first  line 6 will be evaluated, by calling rock_judger on Rock array a. Since the length of this is still greater than 2,  it once again splits this array in half and calls the rock_judger method on each half. We’ve reached line 6 again so our original array ‘a’ is split into smaller arrays (which I’ll call ‘aa’ and ‘ab’). At this point Rock array ‘b’ is still untouched.

Alright, so we’ll call our rock_judger method (yes, AGAIN) on Rock Array ‘aa’. We’ll check if it’s 2 of fewer rocks….and it is! Finally! So now all we have to do is tell the method that ‘a’ is the weight of the first rock (199) and ‘b’ is the weight of the last rock (94). We use the ternary operator on line 10 to return whichever rock is heavier – in this case the first one.

 We jump up a level, and finally reach line 7 of our method. We now call rock judger on Rock Array ‘ab’,  which is quickly evaluated since it also only has two rocks, and it returns the heavier rock.

Now we can jump up again and go past line 7 down to line 10, and decide out of Rock aa and Rock ab, which rock is heavier. We return 199 and jump up another level.  We now have to go through and call rock_judger on Rock Array ‘b’, which (because it is more than two rocks long) will be split into two arrays, and then each will have the rock_judger method called. This all runs exactly as it did for Rock Array A, so I won’t explain it all again but have included the diagrams of each step.

So eventually we end up back at our base level. Our value for ‘a’ is the heaviest rock from the first half of our initial rocks array. Our value for ‘b is the heaviest rock from the second half.  We hit line 10 for the last time and finally return our heaviest rock – ironically it was the very first rock we started with.

Now this is not a situation where you’d want to actually use recursion, since there are many other methods or loops that could get the job done in less time. But hopefully it’ll give you a good introduction to how it works. When in doubt – grab some butcher’s paper and a sharpie and try to figure it out in english or pictures first!

Overall the pattern should look like this

Am i simple enough to solve?

=> yes? Return result

=> no? Run another recursion cutting out some of the information to simplify.

Good luck! Now go make sure your spinning tops eventually fall over…