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
baseCaseLessfunction 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.