Top 5 Problems to Test Your Recursion Knowledge for Your Next Coding Interview

Try to solve these challenges before your next coding interview.

Shalitha Suranga
Jan 16 · 3 min read
Image for post
Image for post
Photo by AltumCode on Unsplash

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 following types of questions are so popular, and there is a higher probability of getting these kinds of challenges in your next coding interview. I wrote solutions for each problem in JavaScript.

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

Problem: max(int x, int y) function returns the largest integer between x and 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 N variables.

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, theint 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 a and 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.

The Startup

Medium's largest active publication, followed by +773K people. Follow to join our community.

Shalitha Suranga

Written by

Software Engineer at 99x | Apache PMC member | Open Source Contributor (Author of Neutralinojs) | Technical Writer

The Startup

Medium's largest active publication, followed by +773K people. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store