November 5, 2016 · Developer in Training

Recursion...What?! 😩 Recursion...Yeah! 🙌🏽

Recursion is one of those programming concepts that really hurts the brain. Recursion describes a function that calls itself.

function recursion(  
    isHard = True
    recursion()
)

This function has a flaw, once it is called it will NEVER stop! Recursion will always be hard, and we don't want that.

Define yourself a Base case

A recursive function needs a base case, else it will just run forever...like this fun T-Shirt game between Macaulay Culkin and Ryan Gosling.

via GIPHY

And to be honest if you search for recursion GIFs, you'll see that endless recursion is the stuff of nightmares.

Your base case is essentially a condition where the problem is solved and your life is complete.

Make it trivial

If you have a problem you think can be solved with recursion, imagine the simplest most trivial version of your problem. Once you've imagined the simplest version, think simpler again. Each call to your recursive function should bring you closer and closer to your basecase.

Imagine the recursive Stack trace

When you call a function, it - along with all of its variables, gets added to a part of computer memory called the stack. Now you can imagine the stack as a sort of paper tray.

You could imagine your function call as sheet of paper with the state of that function call and its variables written on it. When you call the function you put it into the paper tray. When you have a recursive function, if you didn't solve the problem the first time, putting your paper on the stack forces you to take a new piece of paper to try to solve the problem again. The variables as you left them in your previous attempt become the input for your next try. Didn't solve it? That piece of paper goes on top of the stack. And so on, and so on until you get it!

Now though - you have a big stack of paper. But also you know how to solve all the of the problems (function calls) that came before. You've cracked it, your function returns. We should probably tidy up. Thing is, the stack has this LIFO policy - Last In First Out. Meaning we can only handle one bit of paper at a time and every time only from the top. So we take our recently solved problem, scrumple up the paper and recycle it - because we're good like that. Using our new understanding of the problem we solve the next sheet of paper down, scrunch and recycle.

This keeps going until we get to the first time we tried to solve the problem. This time, pffft...this is easy! We tear up our paper into confetti, celebrate with an embarrassing dance, sweep up the mess and recycle.

Problem solved.

Yeah...but what is recursion good for?

Well all sorts of things. There are some pretty standard computer science and maths problems that can be solved with recursion. Some we've been exploring in my masters are puzzles like the Towers of Hanoi.

via GIPHY

Algorithms to find the shortest path from A to B. We've made a recursive program that solves any Sudoku puzzle - so if you're wanting to win one those newspaper Sudoku competitions, drop me a line and I will suck all of the fun out it for you.

Here is an animation of a recursive program I made finding all the paths to find the star in a maze.

A recursive function navigating a maze

Recursion allows you to solve complex problems with minimalist and elegant code. Simple is hard. I've found working it out in your head - hurts. Try sketching it out or even role playing, imagine you are a recursive algorithm.


Subscribe to my Letters to the Ether to hear about projects I'm working on and occasional notes from a Developer in Training.

Comments powered by Disqus