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