Recursion: Closure Trap in While Loops

As developers, Sometime we encounter tricky situations where a simple piece of code does not behave as expected and gives us some headache. I experienced one recently when writing a simple recursion to solve a simple problem.

Naive Implementation

My first thinking was that this problem can be solve using a recursive function that calls itself using n-1 as argument for n > 0:

function fizzBuzz(n) {
	while(n > 0) {
		if(n === 3) {
			console.log("fizz");
		} else if (n === 5) {
			console.log("buzz");
		} else {
			console.log(n);
		}
		fizzBuzz(n - 1);
	}
}

I was confident that my code will succeed at the first execution. I was wrong! This code produces an infinite loop that logs 1 each time.

The Closure Trap in While Loops

When working with recursive functions, one particularly challenging scenario involves the use of while loops, which can lead to unexpected behavior due to closure issues. To understand the issue, let's analyze what happens at the call stack level:

/**
 * The tricky part:
 * The while loop condition is false for n=0, no extra recursive call to execute.
 * The function fizzBuzz(0) returns implicitly undefined 
 * and exits the call stack at this point and the parent call fizzBuzz(1) resumes.
 * Since n=1, the while loop condition (n > 0) is true again. 
 * It calls fizzBuzz(0) again, causing the cycle to repeat.
 */
n=0 => call fizzBuzz(0) 
n=1 => call fizzBuzz(1) 

// Till 2, recursive calls work as expected
n=2 => call fizzBuzz(2) 
n=3 => call fizzBuzz(3) 
n=4 => call fizzBuzz(4) 
n=5 => call fizzBuzz(5) 

How to Fix it

We can fix this in an “ugly” way by adding an explicit return startement after the recursive call. This return statement will stop the loop after the call to function(n-1).

function fizzBuzz(n) {
	while(n > 0) {
		// ...
		fizzBuzz(n - 1);
		return;
	}
}

Or a prettier way by using an if statement instead of a while loop. By using an if statement, each recursive call to fizzBuzz(n) performs a single execution of the block inside the if (n > 0) condition. It does not re-evaluate the if (n > 0) condition after the recursive call returns, because there is no loop structure that would cause re-entry into that logic.

function fizzBuzz(n) {
    if (n > 0) {
        // ...
        fizzBuzz(n - 1);
    }
}

Conclution

Be careful when using while loops in recursive calls. Prefer an if statement to handle the base case.