Top 5 Problems to Test Your Recursion Knowledge for Your Next Coding Interview
Recursion is a useful fundamental theory in computer science and mathematics. In mathematics, it appears in areas such as number sequences and functions. In computer science, it is helpful to solve problems by using the divide-and-conquer approach and dynamic programming. The divide-and-conquer approach decomposes a specific problem into smaller sub-tasks. After that, it solves each decomposed tasks to obtain the final solution. These smaller tasks can be either the same or overlapping. If a particular problem has overlapping sub-tasks, dynamic-programming helps us to reach the optimal solution.
Understanding the recursion theory and solving recursive problems could be difficult sometimes. Also, those problems could be easier for people who improved their analytical thinking skills. Hence, most interviewers frequently ask recursion-related problems during coding interviews to test the candidate’s analytical skills.
The quick DFS
Problem: Assume that there is a binary tree with some nodes. Write a program to print all values of existing nodes with the DFS algorithm. The order doesn’t matter.
Solution: If we try to simplify this problem further by decomposing it to a repetitive tiny problem, we can notice that it’s all about processing a node, traversing the left sub-tree, and traversing the right sub-tree. Let’s write a code for it quickly.
Since there are no cycles in trees, there is no need to mark each node as visited to avoid stack overflow issues.
The magic function
max(int x, int y) function returns the largest integer between
y. If there is a third integer, we can write a one-line statement format like
max(int x, max(int x, int y)). Write a function to output the relevant one-line statement format for
Solution: If we write down answers for a few input values such as 2, 3, and 4 — we can notice that the second parameter is going recursive. In other words, the
int y area is recursively defining the main function. This question requires collecting answers from all subtasks to build the final answer, unlike the previous challenge.
The recursive sum
Problem: Write a recursive function to compute the sum of given
b positive integers without directly using the
+ operator for summation.
Solution: I hope that you are thinking about incrementing one value. Well done, you are very close to the answer. We can increment a value by one until the other value reaches zero. Check out the following code!
Here were are incrementing the value of
a recursively until
b gets zero. When
b gets zero, we stop the recursion as the base case. Finally, we simply return
a as the final answer.
Finding the maximum value
Problem: Write a function to find the maximum value of an array of integers without using an iterative statement.
Solution: This is very similar to the previous question. If there is an array with two integers, it is possible to compare both. If there is only one value in the array, we can directly return it as the final answer. Besides, we can compare the first integer with the highest integer of the right partition for larger arrays.
The recursion approach can easily solve the right partition of the array similarly.
The linked list
Problem: Write a recursive function to print all values of a linked list.
Solution: If you solve previous challenges, this is a piece of cake for you. This question is very similar to the DFS algorithm of a binary tree. The following code shows how easy it is.
When I interview university students for internship programs, I usually ask this question with some theoretical questions about the singly linked list.