What Is Recursion? How Does It Work?

Recursion is a method by which a problem gets solved through iteration.

In other words, a recursive function is a function that repetitively invokes itself infinitely (or until something stops it).

Important stuff to know about recursive function

Keep these two essential pieces of info in mind whenever you choose to use recursive functions.

Info 1: Recursion is not an IIFE

A recursive function is different from an Immediately Invoking function Expression (IIFE).

An IIFE automatically invokes itself once.

However, a recursive function automatically invokes itself repeatedly for an unlimited amount of time or until something stops its re-invocation.

Info 2: A recursive function needs a base case

The code written to discontinue the re-invocation of a recursive function is called a base case.

It is always important to define a base case when creating a recursive function — so that the function will not run endlessly, thereby crashing the browser.

Example of a recursive function

Below is a JavaScript code that returns a concatenation of all the values returned through the countDown() function’s recursive invocation.

// Create a recursive function:
function countDown(num) {
   // Define the base case of this recursive function:
   if (num < 0) {
      return "Recursion Stopped!";
   }

   // Define the recursive case:
   return num + ", " + countDown(num - 1);
}

// Invoke the countDown() recursive function:
countDown(2);

// The invocation above will return:
"2, 1, 0, Recursion Stopped!"

A look at the events behind the scenes

When we invoked the countDown function and passed in the value 2 (that is, countDown(2)), the algorithm started running as follows:

Step 1: Check if 2 is less than 0

The computer checked if the value 2 — that we passed to the num parameter of the countDown function — is less than 0.

Since 2 is not less than 0, the computer didn’t execute the if statement’s code. Instead, it skipped to the next code after the if statement — which is the recursion code.

Step 2: Execute the return statement

After skipping the if statement, the computer executed the return num + " " + countDown(num - 1) code — but substituted the num parameter with the parameter’s value (that is, 2) like so:

return num + ", " + countDown(num - 1);
return 2 + ", " + countDown(2 - 1);
return 2 + ", " + countDown(1);

Step 3: Execute only the recursive statement

In step 2’s code above, notice that the return command can’t return any value because the return statement includes a recursive code (countDown(1)) recalling the countDown function.

Therefore, while retaining the other parts of the return statement (that is, 2 + ", " +), the computer will execute only the recursion code (countDown(1)).

In other words, the countDown(1) code will automatically invoke the countDown function while passing in the value 1. Then, the algorithm will start running again by checking if 1 is less than 0.

Since 1 is not less than 0, the computer skipped to the recursion code like so:

return 2 + ", " + num + ", " + countDown(num - 1);
return 2 + ", " + 1 + ", " + countDown(1 - 1);
return 2 + ", " + 1 + ", " + countDown(0);

Step 4: Invoke only the recursion code

Again, notice that the return command (in step 3) cannot return any value because the return statement includes a recursion code (countDown(0)) that recalls the countDown function.

Therefore, while retaining the other parts of the return statement (that is, 2 + ", " + 1 + ", " +), the computer will execute only the recursion code (countDown(0)). So, the countDown(0) code will automatically invoke the countDown function while passing in the value 0.

Then, the function will start running again by checking if 0 is less than 0.

Since 0 is not less than 0, the computer skipped to the recursion code like so:

return 2 + ", " + 1 + ", " + num + ", " + countDown(num - 1);
return 2 + ", " + 1 + ", " + 0 + ", " + countDown(0 - 1);
return 2 + ", " + 1 + ", " + 0 + ", " + countDown(-1);

Step 5: Execute only the recursion code

Yet again, the return command (in step 4) can’t return any value because the return statement includes a recursion code (countDown(-1)) recalling the countDown function.

Therefore, while retaining the other parts of the return statement (that is, 2 + ", " + 1 + ", " + 0 + ", " +), the computer will execute only the recursion code (countDown(-1)). So, the countDown(-1) code will automatically invoke the countDown function while passing in the value -1.

Then, the function will start running again by checking if -1 is less than 0.

At this point, -1 is less than 0. Therefore, the computer will execute the code of the if statement by returning the value “Recursion Stopped!” like so:

return 2 + ", " + 1 + ", " + 0 + ", " + "Recursion Stopped!";

At last, the return statement now has values it can validly concatenate and return. Therefore, the returned value from countDown will be:

"2, 1, 0, Recursion Stopped!"

Wrapping it up

In this article, we learned that a recursive function is a function that repeatedly recalls itself until something stops the recall.

Thanks for reading!

Credit

Featured Image: Infinity circuit loop by Gerd Altmann