I previously made a post with some shittily drawn diagrams, trying to make sense of how linked list reversal works in JavaScript.

However, some of my diagrams were slightly inaccurate on second look, and also, for me, in order to visualise something like this properly it helps me to see it in motion.

To that end I’ve coded up a new solution, inspired by this video:

Also, if you really want to figure out how this code works, I highly recommend making your own cut outs and moving them around. Beats staring at a screen.

This is one of those algorithms questions that makes my stomach hurt.

If you haven’t seen this before prepare to put your brain through a blender.

How do you reverse a linked list in JavaScript?

Firstly, you have to have a linked list. Luckily I have one I prepared earlier. JavaScript doesn’t have a linked list implementation, so we have to make our own:

When this is run it will print [1,2,3,4,5], which under the hood looks like 1=>2=>3=>4=>5, with a reference to the start (head), and the end (tail) of the chain, or snake, or whatever we decide we want to think of our list as.

We can easily get to the first element, and we can easily get to the last element.

Cooooool. Now reverse it, turn those arrows the other way.

My first attempt at this worked quite nicely, but is wasteful with memory (a sin in computer science). Here it is:

So just stick all the values from the linked list into an array, then pull items off the array and rewrite our linked list from scratch!

I know, I’m a genius.

The runtime is O(n), which is good.

The space complexity is also O(n), which is less good. At this point if you are interviewing, I imagine the interviewer (if they even let you code this basic solution), will be tutting and saying things like ‘but can we do better?’, scratching their chin and gesticulating with whiteboard markers.

And it turns out that yes, there is a better solution. The bad news is that it is utterly brain melting to actually understand. If you get what this is doing straight off the bat, all power to you.

reverse() {
let first = this.head;
this.tail = this.head;
let second = first.next;
while(second) {
const temp = second.next;
second.next = first;
first = second;
second = temp;
}
this.head.next = null;
this.head = first;
}

In my case it just made me want to cry and shout and stomp my feet and yell ‘BUT WHY DO I HAVE TO DO THIS STUPID SHIT. I’M A FRONTEND DEVELOPER, LET ME DO SOME CSS OR SOMETHING. I’LL JUST GOOGLE IT. THIS IS BULLSHIT!!!?!!’.

Obviously, we are onto a good problem. The ones that expand your brain and make you better at problem solving normally start with this sort of reaction. The key to getting gud is to gently soothe and comfort your troubled brain, and trust that given enough sustained concentration on the problem, some youtube videos, and a bit of sleep, this will start to make sense.

Let’s draw some pictures and match them to code (DISCLAIMER: These diagrams are not totally accurate… I’ve left them now though as this is useful as a record for me of how my thinking progressed. For a better illustration of how this algorithm works, see this post) :

We’re going to use a smaller list for this run through, because I can’t be arsed to draw endless diagrams.

We want to turn 1=>2=>3 into 3=>2=>1.

What

a time

to be alive.

let first = this.head;
this.tail = this.head;
let second = first.next;

Just assigning things for now, seems OK. See brain, nothing to be scared about. Right?

‘THIS IS BULLSHIT. WHAT THE FUCK ARE WE EVEN BOTHERING WITH THIS FOR. LET’S PLAY ROCKET LEAGUE’

Our diagram is in this state now:

OK. Next bit.

while(second) {
const temp = second.next;
second.next = first;
first = second;
second = temp;
}

…

…

…

This appears to be a loop. Let’s try one iteration first, and update our diagram.

second is pointing to the element with the value 2 for us currently, so it is truthy. We enter the while loop, filled with trepidation.

const temp = second.next

second.next = first

first = second

second = temp

Oooh wow, this kind of looks like progress, we swapped 2 and 1, and our variables are all pointing at sensible looking things. Apart from second, which is not pointing at the second element, and head which is just floating in the middle of the list. I think this is one of the tricky parts of linked list questions, the variable names end up not making sense mid way through the problem.

Let’s continue.

second is pointing to the element with the value 3, so it is truthy. We enter the while loop again, brimming with new found confidence.

const temp = second.next

temp gets set to second.next, which is now null.

second.next = first

first = second

second = temp

Second is null now, so we avoid the while loop this time round.

this.head.next = null

So we sever that endless loop setting head.next to null

this.head = first

We’ve set up our newly ordered linked list, now we just need to make it official by updating the head reference.

this.head = first;

Anddddd done.

I’m going to need to revisit this, but this scribbling exercise has already helped. I hope it helps you too.

a) You are trying to do search on a randomly rotated sorted array which is enormous

b) You are trying to prepare for technical whiteboard tests

c) You like puzzles

b) is probably the most likely.

In my case it’s a combination of b) and c).

I almost solved this on my own. I didn’t get it quite right, but my thought processes were not totally wrong, which is a nice change.

QUESTION:

Search in Rotated Array: Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order.

If we can use binary search, we can cut the problem in half with each check, giving us a run time of O(log n)

Demon/Gargoyle interviewer: ‘CODE IT!!! MINION’

Hold up there, I haven’t got my tactics in place yet.

For binary search to work we have to be able to work on a sorted array.

Because our array has been rotated, we essentially have two sorted arrays:

[15, 16, 19, 20, 25]

[1, 3, 4, 5, 7, 10, 14]

We can do binary search on each of these individually just fine.

So if we find the ‘rotation point’ or whatever you want to call it, we can split the array and RECURSE LIKE OUR LIFE DEPENDS ON IT.

How we gonna find that rotation point?

Rotation point = ‘point in the array where the previous element is bigger than the next element’. i.e it is not sorted.

Could just loop through the array and check each element, but that erodes all of our good work, as we are just searching for an item in the array again so we go back to O(n).

Demon/Gargoyle interviewer: ‘WHAT ARE YOU THINKING MINION??? YOU MUST VERBALISE YOUR DEEPEST THOUGHTS TO ME’

Fuck this industry.

Maybe we can use recursion again/a version of binary search?

Then we can get back to cutting that problem in half. O(log n) for the win!

I have an idea. Look.

[15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14]

The middle index is 6, with a value of 3 in it.

One half of our array when split by this middle element is not sorted:

[15, 16, 19, 20, 25, 1, 3]

The other half is sorted:

[3, 4, 5, 7, 10, 14]

We can figure out which half is sorted by comparing the middle element (3) with the left and right most elements respectively.

15 is not smaller than 3, so that half is not sorted.

3 is smaller than 14, so that half is sorted.

Now we know that our ‘rotation point’ is in the left half of our array, so forget about the right half, and RECURSE.

[15, 16, 19, 20, 25, 1, 3]

Middle is 20, left half is sorted, right half is not sorted, so rotation point is in right half. RECURSE.

[20, 25, 1, 3]

middle is 1, element before it is 25. IT IS OUT OF ORDER WE HAVE FOUND OUR ROTATION POINT IN LOGARITHMIC TIME DID YOU HEAR THAT YOU IMPASSIVE GARGOYLE FUCK YOU

Suhwheet.

The recipe:

1) Find the rotation point recursively in O(log(n)) time.

2) Do binary search on both halves in O(2 * log(n)) time.

3) Profit/dance with joy at your new O(3 * log(n)) => O(log n) running time.

There are definitely optimisations that can be made here.

But I’m going to move on with my life for now. Behold:

const findRotationPoint = (array: number[], left: number, right: number) => {
const middle = Math.floor((left + right) / 2);
// This element is out of order
if (array[middle - 1] > array[middle]) {
return middle;
}
// If the left half is sorted
if (array[left] <= array[middle]) {
// Check the right half - as left half is OK
return findRotationPoint(array, middle + 1, right);
} else {
// Check the left half because it is not sorted so must contain the rotation point
return findRotationPoint(array, left, middle - 1);
}
};
const searchRecursive = (
array: number[],
left: number,
right: number,
target: number
): number => {
// Target not in array
if (left > right) {
return -1;
}
const middle = Math.floor((left + right) / 2);
if (array[middle] === target) {
// We found the target!
return middle;
}
if (array[middle] < target) {
return searchRecursive(array, middle + 1, right, target);
} else {
return searchRecursive(array, left, middle - 1, target);
}
};
const search = (array: number[], target: number) => {
// Find rotation point
const rotationPoint = findRotationPoint(array, 0, array.length - 1);
// Check to left of rotation point
const leftResult = searchRecursive(array, 0, rotationPoint, target);
if (leftResult !== -1) {
// We found it!
return leftResult;
} else {
// Check to right of rotation point
return searchRecursive(array, rotationPoint, array.length - 1, target);
}
};

This is a problem from Cracking the Coding Interview that I did not manage to solve nicely on my own.

It is an example of a problem that can be solved using the ‘base case and build’ method.

I have implemented it in TypeScript, based on the given solution in CTCI (so I cheated basically).

I’m going to try and explain the solution back to myself in a way I understand so I hopefully can make it stick and solve similar problems in the future.

Power Set: Write a method to return all subsets of a set.

SPOILER: This is how you can do it recursively:

const powerSet = (set: number[], index: number): number[][] => {
let allSubsets: number[][];
if (set.length === index) {
allSubsets = [];
allSubsets.push([]);
return allSubsets;
} else {
allSubsets = powerSet(set, index + 1);
const moreSubsets = [];
for (let i = 0; i < allSubsets.length; i++) {
const newSubset = [];
newSubset.push(...allSubsets[i]);
newSubset.push(set[index]);
moreSubsets.push(newSubset);
}
allSubsets.push(...moreSubsets);
return allSubsets;
}
};

What’s going on here then?

This is an example of using the ‘base case and build’ method of solving problems, where you take the simplest meaningful case of the problem and solve it, then figure out how to move from that simple case to the next iteration, and build a (probably recursive) implementation to take you from n-1 to n.

For simplicity, I’m using arrays to represent sets.

If we need to find all subsets of an empty set ([]), i.e. n=0, we get one subset: []. Our method should return [[]] in this case.

Now n=1. Let’s try with the set [1]. i.e. a set with cardinality of one, with a single element, the integer 1.

This gives us two subsets, the empty set [], and the set [1]. So our method here should return [[], [1]].

Now n=2. We’ll try the set [1,2]. A set with cardinality 2 with two elements, the integers 1 and 2.

This gives us four subsets:

[[], [1], [2], [1,2]]

At this point, believe it or not we have enough information to solve this problem for any n

As our n increases, we just have to clone all subsets from n-1, then append the nth element to each of the new subsets.

In our case:

n=3, let’s use the set [1,2,3].

Clone [[], [1], [2], [1,2]] and put it into the array:

[[], [1], [2], [1,2], [], [1], [2], [1,2]]

Now append the nth element (3) to all of the cloned subsets:

[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Now we have a base case (below is shitty pseudocode btw, not TypeScript):

if (n===0) { subsets.push([]) }

and we can use our newly discovered transformation to construct the remaining subsets recursively.

else {
cloned = subsets.clone();
append set[n] to each subset;
subsets.append(cloned);
}

In terms of time and space complexity, this solution uses O(n * 2^n) space and O(n * 2^n) time, which is the same as the total number of elements across all subsets.

I need to think a bit more about why exactly this is the case, but visually you can see the rate at which it grows by drawing out n from 0 up to 4

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?

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:

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.