Annie LiaoRemember the first time you solved an algorithmic challenge by yourself without looking up the solution, only to be told to solve it again using a recursive function?
As this appears to be a common scenario, especially in a tech interview setting, I am putting together a list of classic algorithm challenges to help flex our recursive brain muscles, as this appears to be a common scenario, especially in a tech interview setting......🙃
Challenges List
- Reversing a String
- Adding the Numbers
- Finding Largest Integer
- Finding Specific Element
- Palindrome
- Permutation
- Fibonacci
1. Reversing a String
/* Instruction:
Given a string, write a recursive function to return the reversed string. */
// Example:
reverseString('covid')
// => 'divoc'
This one seems to be the first challenge every code newbie encounters. If you haven't solved this problem with recursion yet, I encourage you to try it out before reading further.
Here's my solution, which can be refactored via a ternary operator:
function reverseString(str) {
// base case: when there's no string to reverse
if (str === '') {
return ''
} else {
// recursive case:
// (1) grab the last character of current string,
// (2) call the same function
// (3) pass in a substring that does NOT include the last character
// (4) return (1) + (2)
return str[str.length - 1] + reverseString(str.substring(0, str.length - 1))
}
}
2. Adding the Numbers
/* Instruction:
Given an array and an index, write a recursive function to add up the elements of an array. */
// Examples:
addingUpTo([1, 4, 5, 3], 2)
// => 10
// => adding the number all the way up to index 2 (1 + 4 + 5)
addingUpTo([4, 3, 1, 5], 1)
// => 7
// => adding the number all the way up to index 1 (4 + 3)
Because we are returning the sum of multiple numbers, I immediately think of declaring a variable sum.
Also, since we are given an index, I decided to initiate sum as the element at that index and add the numbers backward.
The base case would be when we reach the end of the operation, which in this case is index 0, as we are adding backward.
function addingUpTo(arr, idx) {
// initiate sum at arr[idx]
let sum = arr[idx]
// base case: idx === 0
if (idx === 0) {
return sum
}
// adding backward
return sum + addingUpTo(arr, idx - 1)
}
3. Finding Largest Integer
/* Instruction:
Given an array, write a recursive function to find the largest integer in an array. */
// Examples:
maxOf([1, 4, 5, 3])
// => 5
maxOf([3, 1, 6, 8, 2, 4, 5])
// => 8
This is a comparison problem. So naturally, the base case would be when we cannot make a comparison, i.e. when there's only one element left in the array.
Now, how might we keep comparing and reducing the elements in the array in order to reach the base case?
The splice method in JavaScript came to my rescue.
Thanks to the mutability of splice method, I can compare the first two elements in the array, remove the smaller one, and recursively call the function with an updated array, like so:
function maxOf(arr) {
// base case: only one element left in arr
if (arr.length === 1) {
return arr[0]
}
// compare first two elements and remove smaller one
if (arr[1] > arr[0]) {
arr.splice(0, 1) // remove arr[0]
} else {
arr.splice(1, 1) // remove arr[1]
}
return maxOf(arr)
}
4. Finding Specific Element
/* Instruction:
Given an array and a number, write a recursive function to see if the array includes the given element. */
// Examples:
includesNumber([1, 4, 5, 3], 5)
// => true
includesNumber([3, 1, 6, 8, 2, 4, 5], 9)
// => false
Similar to the maxOf() function, we need to compare the elements in the array against the given number.
We can immediately return true once we found a match; if not, we can call the function recursively and pass in the array minus the element we just compared with until we reach the base case.
The base case I've established here is when there's no element left in the array, in which case we return false, as none of the elements inside the array matches the given number.
function includesNumber(arr, num) {
// base case: no element is left to compare
if (arr.length === 0) {
return false
}
if (arr[0] === num) {
return true
} else {
let newArr = arr.slice(1)
return includesNumber(newArr, num)
}
}
In hindsight, I should've used splice instead of slice method to remove the current element. Using slice will trigger a new copy of the array in each recursive function call, which might slow down the operation if given a larget dataset.
5. Palindrome
/* Instruction:
Given a string, write a recursive function to see if a word is a palindrome. */
// Examples:
isPalindrome('madam')
// => true
isPalindrome('covid')
// => false
A palindrome is a word or phrase that reads the same if you reverse the order of every opposing character.
I approached this problem with a mirror in mind: compare the first and last character of the string in each recursive function until we reach the middle point, which becomes our base case.
In the recursive case, we should immediately return false if the current character does not equate to the opposing character, as this does not satisfy the composition of a palindrome.
function isPalindrome(str) {
// base case: reaching midpoint, or empty str
if (str.length <= 1) {
return true
}
if (str[0] !== str[str.length - 1]) {
return false
} else {
return isPalindrome(str.substring(1, str.length - 1))
}
}
6. Permutation
/* Instruction:
Given a string, write a recursive function to print out an array of all possible permutations of the string. */
// Examples:
permutations('abc')
// => ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
permutations('aabc')
// => ["aabc", "aacb", "abac", "abca", "acab", "acba", "baac", "baca", "bcaa", "caab", "caba", "cbaa"]
A permutation is the rearrangement of a set of items. Now, we need at least 2 elements to accomplish permutation. If the string only has one character or less, there's nothing to rearrange, so that would be our base case.
The recursive case is a tricky one for me. Unlike the previous challenges, this time we need several layers of operations to achieve desired results:
function permutations(str) {
let arr = []
// base case: less than 2 characters in the string
if (str.length < 2) {
arr.push(str)
return arr
}
for (let i = 0; i < str.length; i++) {
let currentChar = str[i]
let remainingStr = str.slice(0, i) + str.slice(i + 1, str.length)
let remainingPermutation = permutations(remainingStr) // save the result of the recursive function
// if we find a repeating character, don't add it to the arr
if (str.indexOf(currentChar) !== i) {
continue
}
// concat currentChar with each substring and push to the arr
remainingPermutation.forEach(subString => arr.push(currentChar + subString))
}
return arr
}
As commented in the code snippet, in the recursive case, not only do we need to factor in the case where there are repeating characters in the given string, we also have to concatenate the current character with each permutation of the result of the recursive function.
If you still find it confusing, I highly recommend this detailed walk-through, which helped me understand the recursive solution for this challenge.
7. Fibonacci
/* Instruction:
Given a number, write a recursive function to
print out the n-th entry in the fibonacci series.
Fibonacci series is a sequence,
where each number is the sum of the preceding two:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34] */
// Example:
fib(3)
// => 2
fib(6)
// => 8
I heard that it is not common to come up with the recursive solution without looking it up, so here's the "textbook" version, which, according to some experienced developers, is a formula worth memorizing:
function fib(n) {
if (n < 2) {
return n
}
return fib(n - 1) + fib(n - 2)
}
The runtime complexity of this recursive approach is exponential (O(2^n)), so it is not as performant as the plain-old iterative approach (O(n)).
You can utilize the memoization technique to optimize the recursion, which is beyond the scope of this article.
Final Thoughts
We all have different approaches to solving a problem using recursion. It took me several practices to develop my own strategy.
As of now, I tend to start by figuring out the base case, as suggested by multiple resources. Then I will venture out to the recursive case, which usually involves creating subtasks and combing results of the subtasks.
What about you? How do you train your brain to think recursively? Let me know in the comments!
