There is one way of solving problems with functions you have not used on purpose yet, and it is the most disconcerting of all: a function that calls itself. You have already run into it twice —the named function expression in 03-02 existed partly for this, and the RangeError: Maximum call stack size exceeded in 03-05 turned up because of a call that never stopped. In this lesson you will approach it methodically. And it is not an academic exercise: Nómada Tasks has a problem that loops solve badly and recursion solves naturally, because Marta wants a task to be breakable into subtasks, and those subtasks into others, with no depth limit.

1. What a recursive function is
2. The base case and the recursive case
3. The call stack of a recursion
4. Warm-up 1: factorial
5. Warm-up 2: Fibonacci and its hidden cost
6. The real case: nested subtasks
7. Walking the tree: adding up hours
8. Walking the tree: flattening, counting and searching
9. Recursion versus iteration
10. Tail recursion and why JavaScript does not optimize it
11. Memoization applied to Fibonacci
12. When NOT to use recursion
13. Common Mistakes and Tips
14. Exercises
15. Conclusion

A recursive function is one that, inside its body, calls itself with a smaller problem, until it reaches a case simple enough to be solved directly.

The idea behind it is a way of thinking, not a syntax trick:

To solve a big problem, assume you already know how to solve the same problem slightly smaller, and combine that result with whatever you have to do here.

This is called the recursive leap of faith, and it is the hardest part. When you write countdown(n - 1) you do not have to picture all the chained calls: you only have to trust that that call does its job properly.

Every correct recursive function has exactly two parts:

And two conditions that must always be verified:

1. The base case is reachable. It is not enough for it to exist: the argument must get closer to it on every call.
2. The problem really does shrink. Calling yourself with the same argument, or a larger one, is an infinite loop with extra steps.

Here we pick the stack back up from Hoisting and the Execution Context. Each recursive call pushes a new context that is not released until the inner call finishes.

Two essential observations:

• The "way down" phase stacks calls without computing anything definitive: each one waits for the result of the next.
• The "way up" phase is where the calculations actually happen, from the inside out.

That is why a recursion 50,000 levels deep blows the stack, as you saw in the final exercise of 03-05: all 50,000 additions are pending at the same time.

The factorial of n is the product of every integer from 1 to n. Its mathematical definition is already recursive: n! = n × (n-1)!, with 0! = 1.

A trace of factorial(5):

Notice the throw for the negative case: it is the fail-fast approach from Error Handling. Without it, factorial(-1) would head off toward -Infinity stacking contexts and end up in a RangeError, an error that explains nothing.

The Fibonacci sequence starts 0, 1, 1, 2, 3, 5, 8, 13…, where each term is the sum of the two before it.

Elegant and correct. And disastrous in performance, because each call spawns two, and many of them repeat work already done:

fib(3) is computed twice and fib(2) three times, and with larger n the duplication explodes. The number of calls grows exponentially:

From 10 to 35, the calls go from 177 to nearly 30 million. In section 11 you will fix this with memoization, and the improvement will be spectacular. Keep in mind that fibonacci(35) takes several seconds: you will compare it.

Up to now Nómada Tasks has worked with a flat list. But Marta has asked for something reasonable: that a big task can be broken down into subtasks, and that those subtasks can be broken down in turn. Here is task 1 of the backlog broken out:

That structure is a tree, and in JavaScript it is represented with objects containing arrays of objects:

Why is a loop not enough here? Because you do not know how many levels there are. With one for you walk the first level; with two nested, the second; with three, the third. But if tomorrow Iván adds a sub-sub-subtask, the code stops working. Recursion, on the other hand, does not need to know: every level is treated exactly like the one before it.

This is the sign that gives a recursive problem away: the structure of the data contains itself. A task contains tasks, a folder contains folders, a comment contains replies that are comments.

The first calculation Marta needs: how many hours a task adds up to counting all its subtasks, at any depth.

It is worth analyzing why this works:

• The base case is implicit. If subtasks is [], the for makes no passes at all and the function returns only task.estimatedHours. No explicit if is needed, although writing one would be fine too.
• Every node does the same thing: it contributes its own hours and asks its children to contribute theirs.
• The result, 12 h, matches the hours task 1 had in the flat backlog of Module 2 (3 + 2 + 2 + 5 = 12). Breaking it down did not change the total.

And a variant that filters: the subtree's open (unfinished) hours.

Checking by hand: still open are "Visit two suppliers" (2 h) and "Paint and assemble" (5 h). Total, 7 h. "Measure and draw up the floor plan" (3 h) and "Request quotes" (2 h) are done.

The same scheme solves every operation over the tree. Only what happens at each node changes.

Output:

The level = 0 parameter with a default value (03-03) is a common pattern in recursion: whoever calls from outside omits it, and the function itself increments it on the way in.

The if (found !== null) return found; matters: without it, the function would carry on exploring useless branches after having found the result. It is the recursive equivalent of the break from break, continue and Nested Loops.

Anything you can do with recursion you can do with loops, and the other way round. The question is which one suits each case.

Compare the two versions of the same task, flattening the tree. You have already seen the recursive one. The iterative one needs to manage its own stack:

It works, it cannot overflow the engine's stack and it is faster. But look at what it cost: a manual stack, a not-very-obvious reverse loop and a helper object to carry the level. That is the real choice: clarity versus control.

A practical day-to-day rule:

• A nested structure of moderate depth (menu trees, comments, subtasks, JSON) → recursion.
• A flat list, or potentially enormous depth (thousands of levels, large files) → iteration.

A recursion is said to be a tail recursion when the recursive call is the last thing the function does: its result is returned as it stands, with no pending operations.

In theory, a tail recursion does not need to stack contexts: since there is nothing left to do on the way back, the engine could reuse the current frame. That is called tail call optimization (TCO) and it would turn the recursion into a loop, with constant memory.

The problem is that, in practice, JavaScript does not apply it:

Check it for yourself:

The practical conclusion: writing tail recursion in JavaScript does not protect you from overflow. It is a good stylistic habit and it works in other languages, but here, if the depth could get large, the solution is a loop.

Back to the exponential Fibonacci from section 5. The problem was recomputing the same thing over and over, and you already have the tool to fix it: memoization with a closure from Scope and Closures.

The comparison is devastating:

You go from exponential growth to linear growth. The cost is the cache's memory, which here is negligible, and the usual restriction: memoize pure functions only (03-03). fib(n) always gives the same thing for the same n, so it is safe.

Two warnings about the result of fastFibonacci(90): that number exceeds Number.MAX_SAFE_INTEGER and is therefore approximate. For large integers you have to use BigInt, the type you met in Variables and Data Types. And the depth is still linear: fastFibonacci(20000) would overflow the stack even with the cache working.

There are three situations where recursion is the wrong answer:

And a security warning that matters more than it looks: if the nested data comes from outside (an API, a file the user uploads), the depth is controlled by whoever sends the data. A malicious tree 100,000 levels deep would take your recursive function down. In those cases, either you iterate, or you set an explicit limit:

1. Forgetting the base case. It is mistake number one and it always produces RangeError: Maximum call stack size exceeded.

2. An unreachable base case. Use <= instead of === when the argument could skip over it (decimals, subtracting more than one).

3. Not shrinking the problem.

4. Forgetting the return in front of the recursive call.

It is a silent failure: no error, it simply never finds anything.

5. Confusing a for inside a recursion with a nested loop. The for walks this node's children; the recursion goes down a level. They are different axes.

6. Memoizing an impure function. You have known this since 03-04: the cache would hand back stale results.

7. Relying on tail recursion. It is not optimized in most engines.

8. Tip: draw the call tree for three or four levels. Nearly every recursion bug is obvious at a glance in the drawing and invisible when reading the code.

9. Tip: add an indented console.log when debugging.

Seeing the way down and the way up indented makes any recursion comprehensible. In Debugging JavaScript you will see how to do the same thing with breakpoints and the live stack.

Over redesignTask, write three recursive functions:

• countByStatus(task, status): how many tasks in the subtree are in that status.
• titlesForAssignee(task, name): an array with the titles of the tasks assigned to that person, at any depth.
• isComplete(task): true if the task and all its subtasks are in status 'done'.

Write pathTo(task, id) returning an array with the titles running from the root down to the task with that identifier, or null if it does not exist. For example, for id 121 it must return ['Redesign the multipurpose room', 'Choose the furniture', 'Request quotes'].

The maxDepth function from section 8.2 is recursive. Rewrite it iteratively using an explicit stack, check that it gives the same result (3) and explain in which specific case you would prefer each version.

Exercise 1

Comment: all three follow the same scheme —do something with this node, then with each child— and only the operation changes. isComplete also builds in an early exit: as soon as it finds an incomplete subtask it stops looking at the rest, just like myEvery in Higher-Order Functions.

Exercise 2

Comment: the key is the line return [task.title, ...childPath];. The ... is the spread operator, which unfolds the elements of childPath inside the new array; you will study it formally in Object Destructuring, Spread and Rest. Without it, you would have to build the array with a loop. Notice too that the path is assembled on the way up: each level adds its title in front of whatever the level below hands back.

Exercise 3

When to prefer each one:

Notice one subtle difference as well: the recursive version computes the depth on the way up (1 + the maximum of the children), while the iterative one carries it on the way down, storing the level alongside each pending node. It is the same calculation seen from the other side.

With this lesson you close Module 3. You now know that a recursive function calls itself with a smaller problem, that it always needs a reachable base case and a recursive case that genuinely shrinks the problem, and that each call stacks a context that is only released on the way back up: that is why a deep recursion produces the RangeError you met in 03-05. You have practiced with factorial and fibonacci, and you have seen first-hand how the naive Fibonacci goes from 177 calls at n = 10 to nearly thirty million at n = 35, and how the closure-based memoization from 03-04 brings it back down to thirty-four computations.

Above all, you have seen why recursion exists. When Marta asked for a task to be broken down into subtasks, and those into others, loops stopped working: you cannot write a nested for for a depth you do not know. sumTotalHours, flattenTasks, countTasks, maxDepth, findById and pathTo solve that tree with the same six-line scheme, because the structure of the code mirrors the structure of the data. And you know its limits: the recursion-versus-iteration table, the tail recursion JavaScript does not optimize, the depth limit for data coming from outside and the three situations in which a loop is simply the right answer.

Look at what you have gained over these seven lessons. You started with blocks of code copied four times and you finish with priorityWeight(), isOverdue(), describeTask(), createTask(), summarizeWorkload(), createIdGenerator(), createTaskStore(), a configurable reporting engine and a recursive walk over subtasks. You know how to define and call functions, how to write them as values and as arrows, how to design their parameters and their return values, how to control where each variable lives, how to lock state inside a closure, how to understand what the engine prepares before running anything, how to pass functions to other functions and how to make a function call itself. That is, by a long way, the biggest leap of the course so far.

But notice the price you have been paying without complaining. This whole module has worked with loose variables and parallel arrays: titles[i], assignees[i], priorities[i], statuses[i], hours[i], dueDates[i]. You have had to filter indices instead of tasks, pass eight arguments to describeTask, drag six arrays into every function and trust that none of them ever gets out of alignment. And the moment a real structure showed up —the subtask tree— there was no option but to use nested objects, with a note saying that would come later. That "later" is now. In Module 4: Objects and Arrays you will stop simulating the data model and write it properly: each task will be an object with its nine fields, the backlog will be an array of objects, and every function from this module will be rewritten with clean signatures like describeTask(task, today). Start with Introduction to Objects, and the first relief will arrive on the very first page.