Some algorithms are naturally recursive. For instance, the algorithm to compute the factorial of a number n is recursive. To compute the factorial of a number, say 5, we multiply 5 times the factorial of that number minus 1:

The factorial of 5 is 5 * the factorial of 4. The factorial of 4 is 4 * the factorial of 3. The factorial of 3 is 3 * the factorial of 2. The factorial of 2 is 2 * the factorial of 1. The factorial of 1 is 1. So the factorial of 5 is 5 * 4 * 3 * 2 * 1, which is 120.

Writing this in pseudocode, you can think of this as recursively designed code:

factorial(5) = 5 * factorial(4)

factorial(4) = 4 * factorial(3)

factorial(3) = 3 * factorial(2)

factorial(2) = 2 * factorial(1)

factorial(1) = 1

We are using the factorial function in the definition of the factorial function. That’s the very definition of “recursive.”

It’s like we are using the question in the answer to the question: what is factorial of 5? It’s 5 times the factorial of 4! Of course, that can be frustrating unless you have an answer to the question that doesn’t involve the question itself.

That’s the reason for the base case. The base case for the factorial algorithm is 1; when n is 1, we don’t call factorial again.

That means you can finally stop asking the question and start getting answers. You can

plug in the value 1 for the answer to “What is the factorial of 1?” then you can then answer the question, “What is the factorial of 2?” and so on until you get to the answer for your original question, “What is the factorial of 5?”.

Every recursive algorithm works this way: you create a pile of function calls, each with solutions that involve calling that function again, until you get to the base case.

Then you can start unravelling the pile until you get back to your original function call. (See if you can implement f act orial() in JavaScriptâ€”it’ll be one of the projects!)

Many algorithms for which you may want to create functions are naturally recursive. These naturally recursive functions tend to be easier to read when they are expressed recursively, rather than when they are expressed iteratively (using loops).

However, there’s a downside to recursion. Each time you call a function, you add that function to the call stack; this takes up memory.

Iteration takes up memory too, but usually not as much as a pile of functions on

a call stack.

To see the call stack created by recursive calls, we can use the Chrome browser tools and add a breakpoint to the code on the line in creat eSquares() where we call creat eSquares() recursively:

Then we reload the page, and execution stops each time we call creat eSquares() recursively.

Execute the breakpoint a few times by clicking the Resume script execut ion button, and you can see the function being added to the call stack each time we call it:

Take a look at the scope variables each time you click the Resume script execut ion button; the value of n decreases by one each time. Eventually, n gets to 0, the recursion stops, and the code completes.

This happens because we’re calling creat eSquares() from inside creat eSquares() before the previous invocation of creat eSquares() is complete. To compare, let’s say you have a function add() (that’s not recursive), and you call that function three times:

function add(num1, num2) { return num1 + num2; } add(1, 2); add(2, 3); add(3, 4);

The add() function goes on to the call stack three times. However, you only have one invocation of add() on the call stack at a time, because each invocation of add() ends before the next one begins, so the call stack never gets bigger than one function.

If you like this post, don’t forget to share đź™‚

## No Comments

Leave a comment Cancel