TL;DR Do not forget to return your recursive functions.

Every now and then, when I am chewing on some CodeWars kata, I discover that a nice little recursive function just might solve it in no time. Half an hour later I find myself debugging exactly three lines of code and wondering where the error is, when there seems to be none. Spoiler: There always is an error. And in my miserable case it is the same one time and time again.

If you find this picture familiar, read on.

Only when I give up on brain-work and start printing every step to the console to see where does my result get lost, it dawns on me…

Like a slinky

Let’s take as an example a silly simple JavaScript function that subtracts 1 from the positive integer input argument until it becomes zero and outputs the number of steps it took. Basically, we should just get back the number, that we pass as an argument. =)

First, I would write it like that (wrong way):

1.  const stepsToZeroWrongWay = (n, acc=0) =>{
2.    console.log(`enter with acc = ${acc}`);
3.    if(n!==0){
4.      stepsToZeroWrongWay(n-1, acc+1);
5.    }
6.    console.log(`exit with acc = ${acc}`);
7.    return acc;
8.  };

On the first sight that seems logical – on the line #4 keep calling the function recursively, increasing the accumulator’s value until you reach the exit condition. But that will not give us the result we hope for. In fact, above code will always return zero. To demonstrate, I’ll write the value of the accumulator acc before and after the recursive call to the console and call this function with argument, let’s say 3.

The output will be as below:

/* Sinking down to the bottom of the recursive function */
enter with acc = 0 
enter with acc = 1 
enter with acc = 2 
enter with acc = 3
/* Bubbling up to the top of the recursive function */ 
exit with acc = 3 
exit with acc = 2 
exit with acc = 1 
exit with acc = 0
function returns: 0

Here you see that at first accumulator increases properly until exit condition is reached, but then starts decreasing all the way back to initial value. Like a slinky.

Indeed, this occurs because after hitting the exit condition of the innermost function, all the outer functions must return as well, so the execution continues retracing own steps back to the top. It stops only when it reaches a return statement of the outermost function call.

But the problem with the above code is: I am not storing the return values of inner functions anywhere and continue with execution. So when inner function returns, returned value of acc just gets discarded. That is exactly what happens, in the “bubbling up” phase.

The Return on the Jedi Function

Easy fix is to return the recursive function call, instead of just calling it out of the void. Simply add the return statement, and see how the tables have turned.

1. const stepsToZero = (n, acc=0) => { 
2.   console.log(`enter with acc = ${acc}`); 
3.   if(n!==0){ 
4.     return stepsToZero(n-1, acc+1); 
5.   } 
6.   console.log(`exit with acc = ${acc}`); 
7.   return acc; 
8. };

Call it, and voilà:

/* Sinking down to the bottom of the recursive function */
enter with acc = 0
enter with acc = 1
enter with acc = 2
enter with acc = 3
/* Bubbling up to the top of the recursive function */ 
exit with acc = 3
function returns: 3

Exactly what we need! Function reaches the bottom and returns on exit condition. Immediately after that it returns from the outer functions all the way to the top.

Actually, our stepsToZero can be easily reduced to the following one-liner:

1. const stepsToZero = (n, acc = 0) => {
2.   return (n !== 0) ? stepsToZero(n - 1, acc + 1) : acc;
3. };

Once again… Now in technicolor

In conclusion, here is a little pseudo-code visualisation of the difference in execution flow with or without the return statement:
Without the return statement

With the return statement

Hope, this helps you to solve yet another issue!
Cheers!

Illustration by Spencer Selover