Recursion is a powerful concept in computer science that enables functions to call themselves. It provides an elegant and efficient solution to complex problems.
Before we proceed with the explanation, let's start with a quick exercise. Take a moment to think about what you believe will happen when the following foo function is called:
function foo() {
foo();
}
foo();
In this case, the foo function will enter into an infinite recursion loop, repeatedly calling itself without any termination condition. As a result, the program will encounter a well-known error called "stack overflow". In the upcoming assignments, we will delve into a detailed explanation of how function calls work in conjunction with a stack.
Now, let's move on to a practical example. Imagine you are working on a project for a nature conservation organization and need to develop a JavaScript program to estimate the population of a specific species. The program should start from a given number and display the population count from that number down to 0, decrementing by one.
Take a moment to implement this function in JavaScript. Once you're ready, continue reading.
You might have initially written a loop to achieve this task, similar to the following code:
function populationCount(number) {
for (let num = number; num >= 0; num--) {
console.log(num);
}
}
Though this implementation using a loop is valid, let's explore an alternative approach using recursion.
function populationCount(number) {
console.log(number);
populationCount(number - 1);
}
populationCount(5);
Let's break down the steps of this code:
populationCount(5), which initializes the number parameter to 5.
number, which is 5, to the console.
populationCount function completes, it calls populationCount(4) since number - 1 evaluates to 4.
populationCount(4) starts executing, logging the current value of number, which is 4.
populationCount(4) finishes, it calls populationCount(3).
You can observe that each recursive call decreases the value of number. Instead of relying on traditional loop constructs, we leverage recursion in the provided code to accomplish our goal. This is achieved by having the populationCount function call itself, enabling us to count down from 5 and display each number on the console.
Let's continue with the code, but we will remove some steps for brevity.
populationCount(1) finishes, it calls populationCount(0).
0 to the console and call populationCount(-1).
We seem to have a problem. We wanted to stop at 0, but our count down continued running, and it would run infinitely which is definitely not something we want.
So what can we do instead?
We need to ensure that we don't call populationCount after the number becomes 0. To do that, we can simply return from the function if the number is 0.
Let's see how that would look:
function populationCount(number) {
console.log(number);
if (number === 0) {
return;
}
populationCount(number - 1);
}
populationCount(5);
This case, where we stop the recursive function from calling itself any longer, is called a base case. Every recursive function needs to have a base case. The base case acts as the stopping condition for the recursive function, similar to how we stop an iteration when a certain condition is met. When the base case is reached, the recursive function stops calling itself and returns.
In the previous example, the base case is:
if (number === 0) {
return;
}
Here, the base case checks if the number variable is equal to 0. If it is, the function returns, effectively ending the recursion.
Let's add some more terminology that will help us discuss recursive algorithms.
The recursive case refers to the part of the recursive function where it calls itself. It allows the function to solve a larger problem by breaking it down into smaller, similar subproblems. By applying the same function to a smaller input, we move closer to reaching the base case and ultimately solve the problem.
In the previous code snippet, populationCount(number - 1)represents the recursive case. It means that the populationCount function is calling itself with the argument number - 1. This recursive call allows the function to work on a smaller input and make progress towards the base case.
The reduction step is the part of the recursive case where the input is modified to move closer to the base case. It ensures that each recursive call operates on a smaller version of the original problem. The reduction step is crucial for making progress towards the base case and solving the problem recursively.
In the previous code snippet, number - 1 is the reduction step. It subtracts 1 from the number argument before passing it to the recursive call. By reducing the value of number with each recursive call, the function eventually reaches the base case when number becomes 0.
In the next assignment, we will explore the concept of a call stack and its interaction with recursive algorithms. We'll gain a better understanding of what a call stack is and how it functions in the context of recursive functions.