Recursion Functions

Recursion can feel difficult to new developers. Perhaps that's because many resources teach it using algorithmic examples (Fibonacci, linked-lists). This piece will hopefully introduce things plainly, using one simple example.

Core Idea

Recursion is when a function calls itself until someone stops it. If no one stops it then it'll recurse (call itself) forever.

Recursive functions let you perform a unit of work multiple times. This is exactly what for/while loops let us accomplish! Sometimes, however, recursive solutions are a more elegant approach to solving a problem.

Countdown Function

Let's create a function that counts down from a given number. We'll use it like this.

countDownFrom(5);
// 5
// 4
// 3
// 2
// 1

And here's our algorithm to solve this problem.

1. Take one parameter called number. This is our starting point.

2. Go from number down to 0, logging each one along the way.

We'll start with a for loop approach and then compare it to a recursive one.

Imperative approach (loops)

function countDownFrom(number) {
	for (let i = number; i > 0; i--) {
		console.log(i);
	}	
}

countDownFrom(5);
// 5
// 4
// 3
// 2
// 1

This one contains both algorithmic steps.

1. ✅ Take one parameter called number.

2. ✅ Log everything from number to 0.

Recursive approach

function countDownFrom(number) {
	if (number === 0) {
		return;
	}

    console.log(number);    
    countDownFrom(number - 1);
}

countDownFrom(5);
// 5
// 4
// 3
// 2
// 1

This one also passes.

1. ✅ Take one parameter called number.

2. ✅ Log everything from number to 0.

So conceptually the two approaches are the same. However, they get the job done in different ways.

Debugging our imperative solution

For a more visual example, let's put a debugger in our loop version and throw it into Chrome Developer Tools.

function countDownFrom(number) {
	for (let i = number; i > 0; i--) {
		console.log(i);
		debugger;
	}	
}

countdownFrom-iterative

See how it uses an extra variable, i, to track the current number? As you iterate i decreases, eventually hitting 0 and terminating.

And in the for loop we specified "stop if i > 0".

Debugging our recursive solution

function countDownFrom(number) {
	if (number === 0) {
		return;
	}

    console.log(number);
	
	debugger;

    countDownFrom(number - 1);
}

countdownFrom-recursive

The recursive version doesn't need extra variables to track its progress. Notice how the pile of functions (call stack) grows as we recurse?

That's because each call to countDownFrom adds to the stack, feeding it number - 1. By doing this we're we're passing along an updated number each time. No extra state needed!

That's main difference between the two approaches.

1. Iterative uses internal state (extra variables for counting, etc).

2. Recursive does not, it simply passes updated parameters between each call.

But how does either version know when to stop?

Infinite Loops

In your travels, you may have been warned about the dreaded infinite loop.

🚨 THIS RUNS FOREVER, BE WARNED 🚨
while (true) { console.log('WHY DID YOU RUN THIS?!' }

🚨 THIS RUNS FOREVER, BE WARNED 🚨
for (i = 0;;) { console.log('WHY DID YOU RUN THIS?!') }

Since they'd theoretically run forever, an infinite loop will halt your program and possibly crash your browser. You can prevent them by always coding a stopping condition.

✅ This does not run forever
x = 0;
while (x < 3) { console.log(x); x++; }

✅ This does not run forever
for (x = 0; x < 3; x++) { console.log(x); }

In both cases we log x, increment it, and stop when it becomes 3. Our countDownFrom function had similar logic.

// Stop at 0
for (let i = number; i > 0; i--)

Again, loops need extra state to determine when they should stop. That's what x and i are for.

Infinite Recursion

Recursion also presents the same danger. It's not hard to write a self-referencing function that'll crash your browser.

🚨THIS RUNS FOREVER, BE WARNED🚨
function run() {
    console.log('running');
    run();
}

run();
// running
// running
// ...

Without a stopping condition, run will forever call itself. You can fix that with an if statement.

✅ This does not run forever

function run(x) {
    if (x === 3) return;
    
    console.log('running');
    run(x + 1);
}

run(0);
// running
// running
// running

// x is 3 now, we're done.

Base case

This is known as the base case–our recursive countDownFrom had one.

if (number === 0) {
    return;
}

It's the same idea as our loop's stopping logic. Whichever approach you pick, always remember that at some point it needs to be stopped.

Summary

• Recursion is when a function calls itself until someone stops it.

• It can be used instead of a loop.

• If no one stops it, it'll recurse forever and crash your program.

• A base case is a condition that stops the recursion. Don't forget to add them!

• Loops use extra state variables for tracking and counting, while recursion only uses the provided parameters.