Two’s complement is a way of representing signed (positive and negative) integers using bits.

The left most bit is reserved for dictating the sign of the number, 0 being positive, 1 being negative.

The magnitude of the integer is a bit weirder.

0001 is two’s complement binary for the decimal 1

1111 is two’s complement binary for the decimal -1

How in the name of all that is good and sensible did we get from 0001 to 1111 you might ask?

Repeat after me:

‘Flip the bits and add one’

0001 with all its bits flipped around is 1110, then we add 0001 to it and we get 1111.

Why on earth would you do something so wilfully perverse as this?

Because:

• A number system with two zeros is a pain in the arse.
• We should really simplify the lives of those long suffering hardware engineers, who have to take these representations of numbers, and make the computers do maths with them.

Two’s complement solves both of these problems.

To understand why, let’s try and reinvent signed 4 bit integers.

SIGN AND MAGNITUDE

Our first attempt will be as follows:

The left most bit is used to tell us the sign (1 for negative, 0 for positive), and the remaining three bits are used to represent the magnitude of the integer.

Looks simple enough. 1 is 0001, -1 is 1001.

Let’s kick our new system in the balls a bit.

What does 0000 represent? Easy, zero.

What about 1000? Easy, negative zero.

AHHHHhhhhhhh…. that’s a problem. I bet those hardware people aren’t going to like that. They’re always complaining about stuff like this.

I think we are wasting a slot in our binary integer, as we’ve got a redundant representation of zero, and our hardware will have to somehow account for this positive and negative zero when implementing any maths functionality. Sigh. OK.

After checking, the hardware engineers inform us that yes, this is a pain and no, they won’t have it (fussy fussy hardware engineers).

Also, it turns out that this representation is somewhat fiddly to do subtraction with.

0010 + 0001 in our naive signed binary is 2 + 1 in decimal. Which is 3 in decimal, or 0011 in binary.

0010 + 1001 in our naive signed binary is 2 - 1 in decimal. Which is 1 in decimal, and should be 0001 in binary.

However, if we add our binary representations in the simplest way we get 1001, or -1. Balls.

I assume there are ways around this, but those damned hardware people won’t do it because reasons. Grrr.

So to recap, ‘sign and magnitude system’; two representations of zero; painful to do basic maths with.

Fine we’ll throw that out.

ONE’S COMPLEMENT

Okieeee so what if we flip all the bits when we turn something negative? So 1 is 0001, -1 is 1000.

Now we can try our previous subtraction problem and just add them in the dumbest way possible and we’ll get the right answer I think? Let’s try it:

2-1 is represented as 0010 + 1110, which gives us 0000 with a one carried over.

Which is… still not right.

‘You should take the carry and stick it on the end’

What’s that Gwyneth?

‘Take. The carry. Stick it on the end’

Fine. At this point what do I have to lose.

0000 with the carry stuck on the end is 0001. Which is correct! Well done Gwyneth.

Still. I bet they won’t have that double zero stuff. Probably they’re going to kick up a fuss about this moving carries around as well.

TWO’S COMPLEMENT

Tabatha, what are you guys are chanting in the corner there? By the candles and the… wait is that blood?

‘Flip the bits and and one’

‘Flip the bits and and one’

‘Flip the bits and and one’

‘Flip the bits and and one’

‘Flip the bits and and one’

Not totally happy with this blood situation, but that’s not a bad idea Tabatha!

Let’s give it a go:

2 - 1 = 1

In two’s complement:

0010 + 1111 = 0001 with a one carried

The chanting has changed…

‘Discard the carry’

‘Discard the carry’

‘Discard the carry’

‘Discard the carry’

‘Discard the carry’

You know what I think you’re right, we don’t need it. We’ve got the right answer. Finally 2 - 1 = 1 without any messy carries!

Also, I think I’ve just spotted something even neater. This gets rid of our duplicate zero right?

Two’s complement of 0000:

flip the bits:

1111

add one:

0000 with a carry of 1

discard the carry:

0000

The circle is complete.

YES!!! How do you like that hardware people!?!

I am trying to develop my intuition for recursion.

To this end I spent some time trying to solve mazes with recursive functions.

Along the way I discovered a hidden and dramatic universe, where collections of function calls band together, sacrificing whole family trees in the pursuit of a secure future for their species.

First, let’s solve some mazes:

Specifically, let’s start with this one, and use it as an example to develop a general strategy for solving mazes:

Right, tell me how to get from the entrance (always top left) to the exit (always bottom right).

Seems simple enough, just walk down until you hit the bottom, then go right. Piece of piss.

Ah but computers don’t work that way, they don’t like ambiguity. Try and be a bit more precise. Also what if the hedges in the maze are arranged differently? Does that plan still always work?

OK:

1) We already know where the exit is, so start there and work backwards, keeping track of where we’ve been, then we’ll have a nice ordered list of grid locations we need to traverse in order to get out of the maze.

2) Let’s try moving up first. Ah but then we hit a wall at the top.

3) No bother: move left

No no hold on this won’t do. This is all far too vague for a computer. At every step, it’s going to need very clear instructions to allow it to figure out what direction to go in.

SIGH… fine

Steps for the computer:

1) Go up if you can, and you haven’t come from that direction

2) Otherwise go right if you can, and you haven’t come from that direction

3) Otherwise go left if you can, and you haven’t come from that direction

4) Otherwise go down if you can, and you haven’t come from that direction

There! Happy!?!

Oh much better yes. How does it know how to stop though?

Ok shit. Before you do anything, check if you are at the entrance to the maze

🙂

This looks reasonably hopeful now. I’m pretty sure we’ve missed a few edge cases, but this looks like something we can work with.

(see below for my actual real notes I wrote while trying to figure out this strategy)

Bring on the Recursion

This process has the smell of something could be implemented using recursion.

We have a base case (‘am i at the entrance’), and some logic for deciding how to call the next iteration of the solution.

Oh blah blah blah recursion so what. Tell them about the Glarpols!

Oh fine… This is a Glarpol:

Don’t be put off by its cute and fuzzy appearance. It has a statistically tough challenge ahead of it.

Glarpols exist across infinite different parallel universes, with each universe looking suspiciously similar to our scrappily drawn mazes above.

Much like the Salmon has to struggle and swim upstream in order to spawn, and ultimately survive as a species, so too do the Glarpols.

In each universe, a solitary Glarpol is spawned at the exit to a randomly generated grid shaped maze. The exit is always on the bottom right of the grid, and the entrance is always on the top left of the grid.

If the Glarpol and its offspring manage to find a route to the entrance to the maze, they will survive as a species in this universe. If they do not, there will be no Glarpols in this particular universe.

In order to maintain their population, Glarpols require sufficient oxygen. Every time a Glarpol is created, they use a bit more oxygen.

If too many Glarpols are alive at the same time, then they will not have enough oxygen, and they will all die.

A Glarpol can move once, and breed once, and in contrast to many species, will stay alive until all of its children die, at which point it will also die.

Glarpols don’t know about the grid, but each Glarpol is born with the following information available to them:

1) Whether the maze has been solved by another Glarpol

2) Their ancestors’ journey up until this point

3) What the entrance to the maze looks like

4) Whether they are in a hedge

5) Whether they are in a wall

With this information, each solitary and freshly born Glarpol must decide what to do with their life. The choices are somewhat bleak…

• Has someone else found a path? If so kill myself, I can’t help my species and I’m wasting oxygen.

• Am I at the Entrance? If so tell the rest of my species that we are saved, and tell my parent how to get to the entrance. The effort of transmitting this message causes the me to die.

• Am I in a Wall? If so kill myself, I can’t help my species and I’m wasting oxygen.

• Am I in a Hedge? If so kill myself, I can’t help my species and I’m wasting oxygen.

If a Glarpol has managed to live long enough to get this point, they will give birth to three children, and immediately afterwards will send them out into the world, in all directions (left, right, up, down) other than the one which their parent (who they will never meet) came from. They will also give each of these children a copy of their ancestors’ journey up until this point, along with their current position.

The Glarpol will then patiently wait alone to hear back from their offspring about their fate.

If they hear back that one of their descendants has found the entrance to the maze, they happily forward on the message to their parent. As before, the effort required to do this causes them to die.

Otherwise, if their children die, they also die.

OK… weird story. Do you have some code I can see. This is recursion right?

That’s right. In this tenuous and painful analogy/metaphor, each spawned Glarpol is a recursive function call, oxygen is memory, and the path to the entrance of the maze is the solution to the maze.

If your program runs out of memory by calling too many recursive functions, it will crash. If it finds a path through the maze it terminates successfully.

If you want to see and/or play around with the Glarpols’ universe here is the code I developed when messing around with this idea:

https://github.com/robt1019/algorithms-etc.-/blob/master/glarpols.ts

Something which is said often in software teams (especially in good software teams) is don’t reinvent the wheel.

Generally, this is great advice.

Software is increasingly complex, and if you can save yourself some time and effort, and make your final product more robust by using something somebody else has written, that is a good thing. Especially in complex applications which matter.

A notable example of this is time/date manipulation in JavaScript.

If you ever find yourself doing ANYTHING complicated with dates in a production JavaScript application, stop, just stop, and go and install this library.

‘If I have seen further it is by standing on ye sholders of giants’ – Isaac Newton

‘I don’t know what I would do without NPM’ – Also probably Isaac Newton

Basically, using other peoples’ stuff for problems that have already been solved frees your team up to focus on solving the more difficult and interesting problems that your specific app needs to solve.

Also no though

If you take this to the extreme, you can end up with a very shallow understanding of things.

When you are learning a new concept, or deciding whether to use a trendy framework or library, you should probably first have a go at reinventing the wheel. Or, to put it another way, you should try and expose yourself to the raw problem that is being solved by the shiny new thing first. If you understand the problem it is trying to solve, you will have a much better ability to use and learn the tool, and will be able to properly assess whether it is something you actually need.

As a stupid example, imagine explaining wheels to a newly discovered group of humanoids that have developed the ability to fly.

Without understanding that wheels make it easier to transport heavy things over distance, ON THE GROUND, they would have no intuitive understanding of the benefits of wheels.

How would you explain wheels to flying creatures?

Flying creature – ‘Why do we need wheels?’

Non flying creature – ‘Carrying heavy things. Friction is easier to overcome than gravity. We have been using them for ages. Can definitely recommend.’

Flying creature – ‘Oooooh I get it now. Give me a wheel plz.’

Cool cool cool, reinvent all the things, got it. Do you have a better example?

Why yes, yes I do.

I’ve recently been bashing my head against recursion (again) as I struggle (again) to refresh my rusting knowledge of data structures and algorithms.

I did a computer science masters, I have worked in the industry for four years, and I have read about and implemented countless recursive functions.

I still have no f**king intuition whatsoever for recursion though.

Every time I have to solve a problem using recursion (usually in coding interviews…) I diligently code up a solution and run it, and it does NOTHING that I am expecting.

Normally it runs out of memory and I basically tweak variables and return values until it (sort of) behaves.

I have decided that enough is enough. So in order to build up a better mental model of and intuition for recursion, I’m going to (sort of) reinvent it, and then try and explain it back to myself in a way that makes sense.

Hopefully along the way things will start to click, click, click into place.

(What follows is a loosely edited version of hand written notes that I put together over the course of about 6 painful hours. They bounce around a bit. I have deliberately left them pretty much as they were to remind myself how this process looked).

Why recurse at all?

Some problems are a bastard to solve in one go. A better approach is to split the problem up into smaller and smaller sub problems, until you have the smallest and simplest meaningful problem.

Once you have that tiny little nubbin of a problem that is laughably simple, solve it, and then recombine all of the solutions to these teeny tiny easy problems to give you a solution to the big scary problem.

That, I think, is the essence of what makes recursion useful in programming.

Recursion, a life in quotes

Recursive – “periodically recurring”

“Pertaining to or using a rule or procedure that can be applied repeatedly”

“Recursion occurs when a thing is defined in terms of itself or its type”

It is kind of like backwards induction then?

Induction… WTF is that?

Mathematical induction is a method for proving that statements are true.

An example of a use for mathematical induction is proving that you can go as high as you like on an infinite ladder. Here’s how you do it:

1) Prove we can get to the first rung (this is called the ‘base case’)

2) Prove we can move from n rungs, to n+1 rungs

QWOD ERRAT DEMONSTRAAANNTEM (we done proved a thing)

Mathematical induction also turns out to have been around for a long time. Like the Greeks used it. Much longer than recursion in fact.

For now, it is enough to say that induction and recursion seem to be somehow linked.

They both involve boiling a problem or a process down to its simplest form, and then detailing a simple mechanism for moving from one iteration to the next.

Enough yammering. Show me some recursion!!!

Okie dokie:

function recursive() {
  recursive();
}

A recursive function, is nothing more than a function that calls itself as part of its declaration.

If you write a function like the one above, and call it in a program, you will meet some variety of this charming individual:

RangeError: Maximum call stack size exceeded

*’Bastard f**king recursion. Why does this keep happening!?!’*

‘Oh mate you’ve blown up the stack. It’s overflowing all over the place. Tragic’

Stack!?! WTF is a stack, and why would it overflow?

Good point, let’s see. Going back a few steps:

What happens in a program when a function calls itself?

When a function is called at runtime, a stack frame is created for it and is put on the call stack.

Stack frames require memory, so if you call a function that calls itself, it will try and keep doing it forever, and will try and create endless stack frames. These stack frames require memory and that is a finite resource, so eventually the program runs out of memory and crashes.

Sounds half plausible. What is a ‘stack’/’the stack’, or ‘call stack’? Is that what it’s called? I forget

I’m pretty sure it’s just a stack, that is used for keeping track of function calls, and their evaluation/results.

function funcA() {
  return 3;
}

function funcB() {
  return funcA();
}

funcA();

funcB();

When this is run, I believe somewhere, something like this is created:

OK, so because stack frames are dynamically pushed onto the call stack when functions are called, if we call a function inside a function and never have a termination case, the executing program will attempt to put infinite numbers of stack frames onto the call stack, and will run out of space:

That’s probably enough on call stacks for now. I’m absolutely certain some of the stuff above is wrong, but I think it’s enough to understand why my code keeps crashing.

In order to avoid toppling call stacks, our recursive function must have some sort of exit clause, which allows it to stop calling itself.

Because functions are evaluated and run in their own sandboxed execution context, the piece of state which tells a recursive function it is done will probably have to be passed to it I guess.

Let’s make a for loop without variable assignment

function loop(loopCount) {
  console.log("in a loop");
  if(loopCount === 1) {
    return;
  }

  loop(loopCount - 1);
}

loop(5);

I’m relatively certain that as this runs, it will push 5 stack frames onto the call stack (as in shoddy diagram below), and then pop them off once the ‘base case’ is evaluated as true (loopcount === 1).

All of the TypeScript!!!!

At this point I went down a bit of a rabbit hole and implemented a bunch of looping methods in TypeScript for fun.

Here they are:

function loop(loopCount: number) {
  console.log("In a loop");

  if (loopCount === 1) {
    console.log(`loop called with ${loopCount}`);
    return;
  }

  loop(loopCount - 1);

  console.log(`loop called with ${loopCount}`);
}

loop(5);

function customLoop(loopCount: number, callback: (key: number) => void) {
  callback(loopCount);

  if (loopCount === 1) {
    return;
  }

  customLoop(loopCount - 1, callback);
}

customLoop(20, (key: number) => console.log(key));

function iterator(array: any[], callback: (item: any, key: number) => any) {
  function iteratorRecursive(key: number) {
    if (key === array.length) {
      return;
    }

    callback(array[key], key);

    iteratorRecursive(key + 1);
  }

  iteratorRecursive(0);
}

const testArray = ["five", "silly", "frogs", "are", "bathing"];

iterator(testArray, (item, key) =>
  console.log(`'${item}' is found at element ${key} in the array`)
);

console.log("\n");

testArray.forEach((item, key) =>
  console.log(`'${item}' is found at element ${key} in the array`)
);

function baseCaseLess() {
  console.log(new Date().getSeconds());
  if (new Date().getSeconds() % 2 === 0) {
    return;
  }

  baseCaseLess();
}

baseCaseLess();

What have we learnt?

• Recursive functions call themselves

• Recursive functions must be given the means to stop themselves. The information telling them to stop doesn’t necessarily have to be passed to them (see baseCaseLess function above), but probably will be.

• The state that tells a recursive function to end or not has to change, either progressively per function call, or as a function of something else that is changing. E.G. time.

Loops are cool and all, but what is an actual useful example of a recursive function?

Let’s have a go at solving some mazes 🙂

If you’re intrigued, check out this post, where I draw up some dubious metaphors and analogies, and play around with solving mazes using recursive functions.

Why are you doing all this again?

I am trying to develop increasingly useful mental models for programming concepts that I am less fluent with than I’d like to be.

I believe a useful model should allow me to understand a concept well enough to solve problems with it at the level I need to.

If I find things not making sense, or behaving differently to how my current model behaves, I know I probably need to refine my model, and clean up the fuzzy bits (as is/was the case with recursion).

Models can be as deep as you want. Ultimately I see them as just a way to understand a complex thing and work with it.

Without effective mental models I feel like I’m kind of just guessing and stumbling around in the dark.