I find it incredibly reassuring when I google ‘recursion’, the concept I really struggled with on this week’s challenge, this post on topcoder.com came up as one of the top results:
‘It is often hard, however, to see how a problem can be approached recursively; it can be hard to “think” recursively’
Yep, you can say that again. Of course it’s hard to think recursively. I’ve been educated my whole life to ‘get to the point’. To ‘stop going round in circles’. And now, I’ve find out that actually this is one of the most powerful tools in programming. I had some unlearning to do!
Our challenge this week was to complete chapters 9 – 14 of Chris Pine’s ‘Learn to Program’. We had been advised to work on each exercise for a maximum of 1 hour before checking the solutions at the back of the book. I was doing ok until chapter 10, where we had to construct our own sorting algorithm. EASY! Ruby has an in built sort method: .sort! Oh wait, we’re not allowed to use it. Uh oh.
Ok, so where do we start? I decided to plan out how I would do that manually, and then I would try and put it in to computer terms.
- Use .min to find the lowest value in the unsorted array, move it to a new array called ‘sorted’ and delete it from the unsorted array.
- Re-iterate process on the remaining elements in the unsorted array.
The biggest problem I found was actually writing the code in such a way that my computer would understand. As I am not yet Ruby-fluent, I got frustrated by lines of code which kept returning errors, when I thought they would work. This task became more about understanding Ruby grammar than it did learning vocabulary.
My first answer looked like this:
It needed improving. It failed the rspec tests since any duplicate values would both be deleted from the array. Also, I wasn’t even sure if .min was entirely allowed since Chris Pine recommends using ‘>’.
Just getting to this stage was such an uphill struggle. I got so wound up thinking my logic was the problem when in reality, a lot of it was down to unnecessary code, such as sorted =  (which created a new empty array on every recursion), or using the wrong notation, e.g.  instead of ().
Getting past those mental barriers though gave me the confidence to try a new approach and my solution eventually passed the test!
Check it out on my GitHub!