Ok, you will probably find this problem during your coding interview 😩 Many companies don’t like giving the candidates tricky problems. Instead, they often ask you to write a recursive function to prove that you’re a real engineer, not some random guys applying for the job because it’s well paid 😆 After that, the next question is usually about how to optimize that function with very large datasets and avoid the “Maximum call stack size exceeded” error
Here is how you can prepare yourself for that type of interview question
1. Basic Recursion
Let’s start with this very basic recursion question
Given an array
arr
withN
items, write a recursive function to calculate the sum of all items in the array
If you think about recursion in its simplest form, it’s like a divide and conquer strategy, where you break the problem into smaller ones, solve one of them first and then repeat with the other remaining ones (recursive case) until there is no item left (base case). Now, let’s take a look at the above problem, the solution can be described like this: The sum of an array is the sum of the first element (the head of the list) and all the remaining items (the tail of the array).
If you have worked in any lisp-like language (Emacs Lisp for example 😂), you will immediately see the pattern. They are the
car
andcdr
function in Elisp.
From that, you can easily write a basic recursive function like this (in Javascript)
const sum = (arr) => {
if (arr.length === 0) {
return 0;
}
const [head, ...tail] = arr;
return head + sum(tail);
};