In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.
In simple terms a recursion is technique of creating a function that calls itself until it does not.
All recursive function will have two cases:
- base case - which will not call itself
- recursive case - which calls itself
The best way to understand this is to do an example.
Let's say you have a sorted array of integers and want to check if a target number exists in that array or not. Since there are multiple ways to solve this problem. The most common one is to loop through the entire array to check if it is equal to the target number or not.
But in this article we will solve this using recursion which is more efficient in nature.
function isPresent(nums, target) {
let middleIndex = Math.floor(nums.length / 2);
let middleElement = nums[middleIndex];
// base case
if (middleElement === target) return true;
// recursive case
else if (middleElement < target && nums.length > 1) {
return isPresent(nums.slice(middleIndex, nums.length), target);
}
else if (middleElement > target && nums.length > 1) {
return isPresent(nums.slice(0, middleIndex), target);
}
// in case if the value does not exists
else return false;
}
isPresent([5, 7, 9, 11, 13, 19, 36, 39, 72], 19); // returns true
Here, isPresent() function is a recursive function which accepts two parameters nums - sorted array of integers and target - number that we wish to find.
Inside the function before the base case we will get the middle index of the array to find the middle element of the array.
Our base case will check if the middle element is equal to the target, then we will simply return true.
Now onto the recursive part the function. Here we will check for the two cases
- if the target is greater than the middle element - we will call the function again but with the new array which consists of all the numbers after the middle element.
- if the target is less than the middle element - we will call the function again but with the new array which consists of all the numbers before the middle element.
Understanding the recursive case:
isPresent([5, 7, 9, 11, 13, 19, 36, 39, 72], 19)
// the given array's middle element
let middleIndex = Math.floor(nums.length / 2);
let middleElement = nums[middleIndex];
console.log(middleElement); // 13
Since the current middle element 13 is not equal to the target number 19, our function will move to the recursive part.
return isPresent(nums.slice(middleElement, nums.length), target)
// this action will rerun the function and this time
console.log(middleElement) // will be 36
Now since the middle element 36 is not only not equal to the target number 19 but also less than the target
return isPresent(nums.slice(0, middleIndex), target);
// this action will also reurn the function and this time
console.log(middleElement) // will be 19
Finally our middle element is 19 which is equal to the target and fulfils the base case, the function will return true and the recursion will end.
Conclusion
In this article you learned what a recursion is and how to make use of recursion in JavaScript to check if a number exists in a given sorted array. If you enjoyed reading the article and it helped you learn something please do like and share it with others. :)