Recursive functions in Javascript are functions that call themselves—usually over and over again. If that seems too complicated to wrap your head around, imagine placing five cards in a deck, then drawing those same five cards again. The first card you drew was the last card you placed on the stack. That is what happens when a process is recursive: a sequence is repeated until a specified limit is reached.
Put another way, think of a choose your own adventure story you may have read as a child. When you reached a dead end, you started the book from the last choice you made, and chose a different path until you found a satisfying conclusion.
In order to develop a deeper understanding of recursion, we will cover:
- How recursion works
- Parts of a recursive function
- Recursion vs. Iteration
- Use cases and examples
- Tips
How Recursion Works
Nature is full of recursion. The repetition in a sunflower’s head or a fern’s leaves exemplify this pattern-making process. When a computer executes recursive functions this process happens in the background.
Recursive functions run via a call stack. A compiler keeps track of pending function calls by adding them to this stack. The calls are then placed on top of one another, akin to our card example, and removed the same way until there are no more calls to make.
Anatomy of a Recursive Function
All functions require an input in order to evaluate a desired output. A recursive function is no different. However, these types of functions must have three attributes to operate correctly:
- A base case
- Different inputs
- The function call
The inclusion of a base case ensures that the process will end at a desired point, usually by returning a variable. Not writing one—or writing one incorrectly—often results in a stack overflow and may cause problems for your CPU.
Each time the recursive function runs, it evaluates a different value or input. Imagine counting down from ten to zero. You would run through different values, or inputs, each time until reaching zero. The code below does the same thing.
function countDown(num){
if(num === 0){
console.log("end")
return;
}
}
In this example the numbers passed in decrement to different inputs as the function calls itself. The base case is the return in the if-statement. Once the number reaches zero the function prints end to the console.
Why Not Iteration?
You may be thinking that an iterative process could do the same thing and you’d be right. In fact many problems that can be solved iteratively can also be solved recursively. Some researchers have also argued that recursion is slower.
The following example produces the same output as the previous countdown function. This time, however, the process is iterative. Using a while loop, the process continues to decrement the numbers passed in until it hits zero.
function iterativeCountDown(num){
let i = 0;
while (i < num){
console.log(num)
num--
};
console.log("end")
return;
}
}
These two problems are simple, but when working with problems in the wild, it’s best to go with the most natural method first. Which case seems more natural for a countdown? for a Fibonacci sequence?
Why Use Recursion
Recursive algorithms remain popular in many aspects of programming today. If you’ve ever written an API call to receive JSON from a backend, a recursive function may have fired in the background. Searching algorithms are also popular places to implement recursion, as we’ll see in the examples below.
Imagine performing a search on an array. We start at the index of zero and reach the end when we find our target, or when the dataset we’re looking through ends. Now imagine looking through 10,000 indexes to find a given value. A better way to search through this array would be to divide it into sections and search only through those sections by dividing again and again until reaching our target.
Binary Search I
The following function relies on recursion to search a sorted array of numbers. In this case a value represents our specified target. In order to optimize the search, a middle point is created by dividing the array’s length by two. A check then fires to see if the middle point is the value we’re searching for.
function binary(array, value){
if(!array.length){
return false
}
let mid = Math.floor((array.length-1) / 2)
if(value === array[mid]){
return array[mid]
}
if(value > array[mid]){
return binary(array.slice(mid + 1), value)
}
if(value < array[mid]){
return binary(array.slice(0, mid), value)
}
}
In the case that the first if-statement evaluates to false, the function then checks to see if the value is greater than or less than the midpoint. The new values are then used to create a new subarray so the process can repeat itself until the target is found.
Binary Search II
This binary function performs similarly to the first one. In this case two more arguments—start and end—are passed into the function. Instead of slicing the array, the start and end points allow us to set the limits of our subarrays.
Note that the recursive function is called with its initial arguments, reducing the need to manipulate the midpoint in the argument itself.
function binary(array, value, start, end){
if(!start){
start = 0
}
if(!end){
end = array.length - 1
}
if(!array.length){
return false
}
let mid = Math.floor((end - start) / 2)
if(value === array[mid]){
return array[mid]
}
if(value > array[mid]){
start = mid
return binary(array, value, start, end)
}
if(value < array[mid]){
end = mid
return binary(array, value, start, end)
}
}
Recursion allows programmers to create powerful, readable, and reusable code. It is especially useful when writing search algorithms that would otherwise be bogged down by slower, sequential processes.
Helpful Tips
Be careful when declaring variables in recursive methods, as they are reset each time the call enters the stack. One way of getting around this is by writing the recursive call in an inner function and wrapping variable declarations in an outer function.
Different data structures demand different ways of thinking about recursion. Slice and substring are useful, in-built helper methods for strings. Our Binary Search I example also used slice to mutate an array. Methods like the spread operator or concat are preferred for arrays that shouldn’t be altered. Object.assign and the spread operator can also help when working with objects.
Recursion is really about viewing a problem differently. Next time you solve a problem iteratively, practice solving it recursively as well. You may be surprised to find how you fast-tracked both your understanding of the problem and the recursive process itself.
Top comments (1)
Enjoyed reading your post,
In the next post, would you please share your experience about Ruby on Rails?
Thanks