Recursion: The Important Lesson on Recursive Functions

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).

This article will use an example to illustrate how a recursive function works.

Note:

• 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 reinvocation.
• The code written to discontinue the reinvocation 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 recursion 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 (recursion statement):
   return num + ", " + countDown(num - 1);
}

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

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

Note: In the recursive algorithm above, the countDown(num - 1) code makes the whole function a recursion because it is the code that makes countDown() recall itself repeatedly.

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 recursion code

In step 2’s code above, notice that the return command 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 + ", " +), 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 the countDown recursion function will be:

"2, 1, 0, Recursion Stopped!"

Conclusion

All in all, a recursive function is a function that repeatedly recalls itself until something stops the recall.

Credit

Menger Maze Pool photo by Pete Linforth

Last Updated on January 10, 2021 by Oluwatobi Sofela