Guide to understanding recursion
As it’s one of the most frequently asked questions on the forum I’ve decided to answer here, so all of you who have hard times with recursion can easily find it.
Part 1. Precedence
First step to understand recursion requires understanding of operator precedence in JavaScript:
Operator precedence determines how operators are parsed concerning each other. Operators with higher precedence become the operands of operators with lower precedence.
Source: Operator precedence - JavaScript | MDN
What it’s saying is if you have this code:
const a = 42 + someFunction() / 2;
JS parser will have to have certain rules of what to evaluate first. Let’s check precedence table from the link above and parse this statement:
20: Function Call
Call someFunction() and substitute the return value
*(let’s say someFunction() returns 100):
const a = 42 + 100 / 2;
15: Division
as we know from the school division will go before the addition
const a = 42 + 50;
const a = 92;
at this point parser will assign 92 to a constant variable a;
You might ask what does precedence have to do with the recursion? Everything! It is a direct side effect of precedence:
function recurseForever(a) {
return recurseForever(a + 1);
}
Outer function recurseForever will return NOT the inner function, BUT the result of it! There is no special logic or mode in the language that allows recursion, no! It’s simply an order in which things get evaluated by parser.
Part 2. Stack
If you try to run recurseForever function from the example above, of course, it won’t run forever, in fact it would very quickly throw an error:
Uncaught RangeError: Maximum call stack size exceeded
Whenever you see something like this, it means it’s time to debug! And the first step of any debugging is to understand a context of an Error. After reading about RangeError and Call Stack we’re coming to conclusion that we have this internal structure called “Call Stack” with some limited size (Range) and whenever we exceed the size we will get this RangeError, good!
Now when we know the context of a problem (“WHAT”), it’s time to search for a reason (“WHY”). Whenever a JavaScript engine runs a function it pushes it to the Call Stack. Think of Call Stack as an primitive array with just a two methods:
-
push(fn) - pushes function to the stack. Invoked whenever it sees the function call
-
pop() - removes the last function from the stack. Invoked whenever the last statement of the current function is executed. Let’s simulate that with pseudo-function parseLine:
const callStack = [];
parseLine('recurseForever(0);'); // Oh, it's a function call!
callStack.push(recurseForever);
parseLine('return recurseForever(a + 1);');
/**
* Ok, as we already know from Precedence part,
* the first thing we will deal with here is recurseForever(a + 1)
* which is another function call!
*/
callStack.push(recurseForever);
parseLine('return recurseForever(a + 1);');
/**
* And here's the BUG!
* Have you noticed it?
*/
We went back to the exact same argument and without simulating further it must be clearly understandable that we will keep pushing our function to the call stack until it’s size is exceeded.
Now, let’s fix it!
Part 3. Iteration
Before we fix our recursive function though, let’s quickly consider one quick thing first, because when I said this just now:
We went back to the exact same argument
I actually lied! 
In every function call we indeed have new arguments. We started with 0, then inside the function body we called our function with a + 1, so 1, then 2, 3 … and so on. To verify that let’s log an argument:
function recurseForever(a) {
console.log(a);
return recurseForever(a + 1);
}
recurseForever(0);
// Ok, now we know the size of a call stack
And NOW pattern recognition abilities of your brain must start ringing bells: “Wait a minute - this looks just like a loop! We’re simply iterating!”. And you’re right (even if that was just my bells). We can very easily “convert” our function to a loop:
// Don't run this
function recurseReallyForever(a) {
while ("We can") {
a += 1;
}
return a;
}
The only exception here is that our call stack in the case of recurseReallyForever(a) will not be exceeded - it only will have one outer function, because there are no function calls inside. Instead there is a while loop inside that now will truly run forever and crush our browser.
And this is a point of midway takeaways!
Takeaway 1:
Whenever you “attach” parentheses to a function name it’s no longer a function, but a result of the function:
function fortyTwo() {
return 42;
}
typeof fortyTwo; // "function"
typeof fortyTwo(); // "number"
Takeaway 2:
Recursion is nothing else than iteration that doesn’t use iterable data structures (like array), but instead uses an array-like system structure called Call Stack. The natural function of recursion is to repeat itself over some set of changing arguments.
Part 4. Base case
Now finally, with all the knowledge we’ve just read, let’s fix our bug! In order to do that, in some point of the iterations of our initial recurseForever function we need a condition in which we no longer make a function call - an exit contract. We call such a condition “Base case”. Every recursive function has to have one, otherwise it will cause a problem and as general convention we normally put base case as a first thing in the recursive function:
function recurseForever(a) {
// base case
if (a >= 10) return a;
console.log(a);
return recurseForever(a + 1);
}
Congratulations! Base case isn’t exclusively a part of recursive function, it is as well a part of any iteration - exit condition out of iteration and you use it all the time with loops etc.
Part 5. Result
If you run the final version of our function recurseForever(0) you will get what seems like logs from 0 to 10 and the first naive guess that they came from console.log(a) method, right? But why was 10 logged? Number 10 satisfies our base case and therefore console.log(a) with a = 10 never was invoked, instead 10 is a result of our function that was sent to stdout because we haven’t instructed to assign this value to anything and that’s a default behaviour. Compare outputs:
recurseForever(0); // logs 0 ... 10
const result = recurseForever(0); // logs 0 ... 9
console.log(result); // And that's where 10 did go!
And now I need maximum focus! Because it’s the core of all the confusion.
“How the hell result equals 10?!!”
Magic, ha! There are two ways to understand what has just happened:
Logical
I call this a “logical traversal of recursive call”, though it’s not an official or conventional term. The key is to start from the end and iterate backwards. What’s the (successful) end of any recursion? Base case!
// What's the output of the following?
recurseForever(10);
// Easy - 10!
Now iterating backwards:
// What's the output of the following?
recurseForever(9);
// We're skipping base case
// and returning recurseForever(9 + 1);
Now taking into consideration the takeaway 1 from the above, what’s recurseForever(9 + 1)? It’s no longer a function, it’s a value - 10!
Now continue the same process:
// What's the output of the following?
recurseForever(8);
// recurseForever(8 + 1), which we've just calculated
…and let’s stop here actually. We clearly see a recurring pattern here that kinda suggests following:
“If we can get the next recursive iteration after the base case to work, then our recursive function works!”
So coming back to the countdown() function from the thread, our base case would be 1 because it’s 100% clear how to make a countdown from 1, right?
countdown(1);
/* this shall immediately return [1] without recursion */
Now all we need to do is to take the next after the base case input - 2 and produce [2, 1] output in a recursive way and that would guarantee the rest of the cases! Pretty neat! We’ll get back to this!
Technical
To understand how exactly this works under the hood we need to get back to the Call Stack. As we’ve seen any recursion is a process of inflating the stack, until we either hit the limit of the stack or the base case occurs. After the case of the latter we will initiate a backward process of deflating the stack, as our imaginary parseLine function will move to the next line, ending each function and popping it out of stack in reverse order.
Reverse is a key word here and is a result of the nature of the Stack. Imagine a stack of cards: inflating the stack would mean taking cards and stack them on top of each other one by one: push(). Deflating stack would mean taking cards out of the stack from the top until you reach the bottom: pop(). So Last card pushed In would be the First card taken Out (LIFO). The graphical chart where x is time and y is a stack size would look like this:
* <- base case
***
*****
*******
*********
***********
************* <- result
Every row of this graph is a separate instance of our function. We’ve called only one of them - the one at the bottom, the rest were called subsequently in the process of inflation. Each of these functions carries its own result and passes it down until it reaches our main function at the bottom. Here is the same in the form of timeline:
STEP 1: recurseForever(0) pushed to Call Stack
STEP 2: recurseForever(1) pushed to Call Stack
...
STEP 10: recurseForever(9) pushed to Call Stack
STEP 11: recurseForever(10) pushed to Call Stack
STEP 12: recurseForever(10) popped out of Call Stack carrying 10
STEP 13: recurseForever(9) popped out of Call Stack carrying 10
STEP 14: recurseForever(8) popped out of Call Stack carrying 10
...
STEP 21: recurseForever(1) popped out of Call Stack carrying 10
STEP 22: recurseForever(0) popped out of Call Stack carrying 10
STACK EMPTY
As you can see after our function is getting popped out of the call stack it carries value (we also say “it’s evaluated to”) that now can be assigned, returned or simply printed to stdout by JavaScript engine.
Here is another visualisation of similar process kindly made by @ilenia:
Red line on this diagram represent inflation of the call stack and blue line - deflation that carries the output towards the the initial function call.
Part 6. Solution
The best way to understand how the solution works is to solve it 
Step 1 (click to show/hide)
So what’s our input, what do we know? We know that countdown expects number n and has to output an array from n to 1. Right away it’s sufficient for us to write couple lines of code:
function countdown(n) {
// base case
if (n === 1) return [1];
// in some point we need to iterate towards base case
countdown(n - 1);
}
Step 2 (click to show/hide)
Now, what’s the next step after the base case? Number 2. Given input where n = 2 we need to produce the following output: [2, 1]. Any ideas? We know that countdown(n - 1) will return [1]. How do we get from [1] to [2, 1]? Well, that’s not hard!
function countdown(n) {
// base case
if (n === 1) return [1];
const output = [n]; // [2]
return output.concat(countdown(n - 1)); // [2, 1]
}
Ok, one can say “You’ve hardcoded it with n = 2, cheater!”. What do you think, are we hardcoders? 
Let’s test it:
countdown(5); // [5, 4, 3, 2, 1]
countdown(7); // [7, 6, 5, 4, 3, 2, 1]
Works!!! 
Step 3 (click to show/hide)
Now the challenge has additional requirement: if n less than 1 we shall return an empty array. Let’s add this:
function countdown(n) {
// base case
if (n < 1) return [];
if (n === 1) return [1];
const output = [n]; // [2]
return output.concat(countdown(n - 1)); // [2, 1]
}
Then test again:
countdown(0); // []
countdown(-33); // []
Yei!
Now let’s refactor a bit. I think we have couple unnecessary lines:
function countdown(n) {
// base case
if (n < 1) return [];
if (n === 1) return [1]; // Do we really need this line?
/**
* To check it all we need is just to simulate all the above
* for input 0 as base case and 1 as a next
* so the return value for n = 1 would be [1].concat([]);
*/
const output = [n]; // Notice how we assign this to output just to return it on the next line. Waste of line!
return output.concat(countdown(n - 1));
}
Solution (click to show/hide)
And here is the result:
function countdown(n) {
if (n < 1) return [];
return [n].concat(countdown(n - 1));
}
// or using ternary operator
function countdown(n) {
return (n < 1) ? [] : [n].concat(countdown(n - 1));
}
Boom!
Part 7. Couple extra famous examples
Factorial (easy)
function factorial(n) {}
STEP 1: What’s factorial? It’s 1 * 2 * 3 * … * n.
STEP 2: Base case and iteration? Looking at the above, if we have n then we go to 1: (n - 1) until n === 1
STEP 3: Write it:
function factorial(n) {
// considering the fact that 1 * n = n
if (n === 1) return n;
return factorial(n - 1);
}
STEP 4: Produce the next result after base case: factorial(2) -> 2. How to return 2 if we have 1?
STEP 5: Back to code:
function factorial(n) {
if (n === 1) return n;
return n * factorial(n - 1); // 2 * 1 - just what we need
}
STEP 6: Test other numbers
factorial(4); // 24 Correct!
factorial(5); // 120 Correct!
Tree traversal (intermediate)
This example is intentionally different to show you other applications of recursive function. Probably the most famous of which is tree traversal.
/**
* Traverses tree from starting node
* until it finds node with given id
* if not found returns null
*/
function getElementById(node, id) {}
Iteration here is a bit different because every node has child nodes under node.children property, so we need to check all the children and children of those children and so on until either we’ve checked all nodes or found the one we’re looking for. And that would be our base cases:
function getElementById(node, id) {
/* base case # 1 */
if (node.id === id) return node;
/* if not, iterate over each child node repeating the process */
for (const child of node.children) {
/* repeat the same function for child and its children */
const match = getElementById(child, id);
/* if match gave us result - return it immediately */
if (match) return match;
/* if not, continue loop */
/* we cannot return null without checking all children first */
}
/* if loop finishes and we haven't matched node at this point then it's base case #2 */
return null;
}
Part 8. Conclusion
Ok, here are key takeaways:
-
Understanding recursion requires understanding of many programming principles and that’s why it might be overwhelming sometimes. Just look at the length of this guide.
-
Recursion often compared against iteration, but in a nutshell it’s also an iteration (otherwise they would simply be incomparable)
-
Each iteration of recursive function requires new arguments and the change between previous and the next argument has to point towards the base case
Recursion has very solid structure that is divided in two parts: inflation - all the code before internal function call and deflation - all the code that will run “on the way back”. Understanding and seeing this abstract structures gives you more understanding when you read or compose recursive function.
Good luck!
