Recursion is one of those classic computer science topics. It’s an interview favorite and often intimidating to beginner programmers. Recursion can provide elegant solutions to extremely complex problems that follow a pattern (e.g. Towers of Hanoi, Fibonacci Numbers, Collatz Conjecture).
How not to use recursion
If used incorrectly, recursion can be dangerous. Not all problems are meant to be solved recursively. Common pitfalls include infinite loops (if you fail to provide termination conditions), memory errors and stack overflows (if the function is deep and memory intensive). All of these issues are avoidable if you follow one rule: don’t use recursion for the sake of using recursion. In addition to the pitfalls above, irresponsible use of recursion can be much slower and more cryptic than iterative solutions.
When to use recursion
Recursion is helpful to know for technical interviews and answering computer science brainteasers, but it has some practical applications, too. The examples below represent valid opportunities to use recursion. However, there are a few points to take into consideration before implementing recursion.
- Can you implement this more easily with an iterative solution?
- Does the recursive solution perform better than the iterative one?
- Is there any possibility of your break condition never evaluating to true?
- Is there any risk of running out of memory?
If you want to execute a function multiple times after a set period of time, recursion is a great option. Below is an example:
1 2 3 4 5 6 7 8 9 10 11
The function above will print successive items from the
words array once a second until the end is reached. Here’s how it works:
- Declare and define the
wordsarray and n counter.
- Declare the
- Log the nth element of the words array to the console.
- Break out of the function if the
ncounter has reached the end of the
- Otherwise, wait 1000 milliseconds, then call
Many algorithms lend well to recursion. What if you had to work with a JSON object with a large array of alphabetically sorted properties? Iterating over the entire array from start to finish each time you want to search for an element would be terribly inefficient. Instead, you could use the sorted nature of the array to your advantage using a binary search algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
On a simplified level, the Binary Search Algorithm takes the following steps:
- Find the middle element of the given array.
- Break out of the function if the bottom, middle or top element is your target.
- If the target is less than the middle element, call the function recursively passing in the left side of the array.
- If the target is greater than the middle element, call the function recursively passing in the right side of the array.
Recursion is an incredibly powerful solution for both solving puzzles and finding the optimized solution for a puzzle. Let’s say you wanted to make an unbeatable version of a board game like Connect Four or Tic-Tac-Toe. An iterative solution could potentially be very complex, as there are a number of factors to consider before making your next move. However, you could determine which move is best through a recursive algorithm that considers all possible future outcomes of the game based on all possible combinations of valid moves by both players. If your game is too complex for an accurate iterative solution and well-defined enough to prevent infinite loops and memory issues, recursion is a powerful tool.