30 Recursion Interview Questions and Coding Exercises for Programming Interviews
These are the 30 common Recursion based coding problems you can practice for coding and programming interviews
Hello guys, if you struggle to solve Dynamic Programming problems using recursion or have difficulty in understanding the Recursion then you are not alone. Many programmer struggle to understand Recursion and Dynamic Programming and don’t perform well during coding interview
The only way to overcome that is solve as many Recursion coding problems as possible. This will train your brain to understand Recursion, base case, and how recursive algorithm works in general. It’s like swimming, initially you struggle to breath in and out of water and then suddenly you find the rhythm one day.
If you are wondering what is Recursion? then it's nothing but a function calling itself. When a function call itself it can keep calling indefinitely until it doesn’t call itself and that’s the base case. Half of the recursion problem can be solved by finding the base case.
For example, factorial() function is good example of recursion. In order to calculate factorial(3) you can write the functional call as 3 * factorial(2)
and then 3 * 2 * factorial(1)
, for factorial 2 you know that value is always 1 so you don’t need to call a function or use recursion you can just return the answer 1 and recursion will start unrolling and produce the output you need.
If you are preparing for coding interviews or trying to learn recursion but struggling and looking for recursion practice problems, recursive coding problems, or simple recursion exercises for interviews then you have come to the right place.
In the past, I have shared best Recursion courses and Dynamic Programming courses and in this article, I am going to teach you what is Recursion, how to identify if a problem can be solved using recursion, exact steps to create a recursive algorithm for problem you are solving and share 25 to 30 common Recursion interview questions which you can practice.
Recursion is a simple yet difficult topic for many programmers as not everyone can understand recursion easily but it’s also very important and you cannot afford to leave it alone as it’s used to solve many Dynamic Programming problems like knapsack problems, Fibonacci, etc.
Solid knowledge of recursion is key to doing well in the coding interviews and that’s where this article will help you. Earlier, I have shared frequently asked programming interview questions, books, and courses and here, I will share 25 to 30 Recursion practice problems and exercises you can do to learn recursion from scratch.
These are common programming questions and practice problems that can be solved using recursion, these will not only help in learning recursion but also in your coding interview preparation. I personally found the best way to learn Recursion in Java or any programming language is by doing some examples.
Every programmer knows What is a recursive function or Recursion in Java but when it comes to applying Recursion to a problem, many fumbles. As per my experience, Recursion is a tricky programming concept, few people get it very quickly, but for some programmers, it takes ages to understand Recursion and develop the ability to apply it.
If you fall into the second category of programmers for whom Recursion is always tricky, then the best I can suggest is doing lots of Recursion based programming exercises.
I know, for some people recursion is very tough to master, I was one of them but when you keep solving problems like this, from easy to difficult, you will slowly understand how recursive solution works and come up with a recursion solution for any new coding problem.
Recursion will also help you to solve dynamic programming-based coding problems, which is very important from a coding interview perspective. Recursions are also one of the most powerful techniques to solve linked lists and binary tree-based problems because both linked lists and binary trees are recursive data structures.
Since I am a Java programmer, you will Recursion based practice problems which are solved in the Java programming language but you are free to solve any programming language like C or Python or even JavaScript.
By the way, if you struggle to understand recursion patterns and recursion in general, I highly recommend going through this Recursion, Backtracking, and Dynamic Programming in Java to learn how to identify recursive problems and how to break them down to solve using recursion.
What is Recursion Programming Technique?
Just a recap of what we have discussed about Recursion in Java in our earlier article, Recursion means calling himself. A function or method is said to be Recursion if it calls itself. To write a recursion function, the first thing anyone needs is to find the base case.
The base case is a particular case that can be solved without calling a recursive function. The base case is the endpoint for the recursive function, it’s the point from where the stack starts winding up. Without any base case, the recursive function will result in StackOverFlowError.
So whenever you need to write a recursive function, first write a base case. Now let’s see a couple of examples of base cases in a recursive function.
If you are calculating factorial than factorial(1) = 1 is a base case, for Fibonacci numbers its f(1) and f(2), for power(int number) its power(0) which is equal to 1. See, all these base cases are conditions that can be solved without calling recursive functions.
By the way, if you like to learn from interactive courses then you can also join Recursion for Coding Interviews in Java a great interactive course from Educative to learn Recursion better, I really loved it as it also forms the basis for Dynamic Programming which they have explained in their Grokking Dynamic Programming Patterns for Coding Interview course.
How do check if a Coding Problem can be solved using Recursion?
Finding whether a programming problem can be solved using Recursion is a skill, not everybody sees issues in terms of Recursion.
The best thing is to break the problem into a smaller set and see if the smaller problem is the same as the original problem or not like in order to calculate a factorial of 5, does it helps to calculate a factorial of 4? This may be a guide to see if Recursion can be used or not.
Similarly, String questions, Array-based problems, linked list algorithms, binary tree algorithms, and dynamic programming-based coding problems are good candidates for Recursion in Java.
Since a smaller linked list is a linked list, a smaller tree is a tree itself, problems like reversing the linked list, traversing the tree, etc. can be solved using Recursion in Java, and if you want to learn more, you can always join one of these best Recursion courses for beginners where I have shared both beginner and advanced level Recursion courses for coding interviews and learning Recursion from scratch.
2 Steps to solve a Coding problem using Recursion
Once you have identified that a coding problem can be solved using Recursion, You are just two steps away from writing a recursive function.
1. Find the base case
2. Finding how to call the method and what to do with the return value.
As discussed above, finding a base case for any recursive solution is the first step toward writing a recursive function in Java or any other programming language. This is usually the simplest way to solve the problem without using recursion.
For example, when you calculate factorial, the base case is factorial(0) which is 1, you mean you know the answer so you can directly return it and from there onwards recursion will unroll and calculate factorial for the given number.
Once you have done that, you need to find a way to call the recursive method and what to do with the result returned by the method, sometime you may need to add, multiply, and divide those depending upon your problem. This will be more clear when you will solve Recursive Practice Questions in Java.
And, if you want to learn Recursion from scratch then Recursion for Coding Interviews in Java course on Educative is a great resource to start with, I really loved it as it also forms the basis for Dynamic Programming which they have explained in their Grokking Dynamic Programming Patterns for Coding Interview course.
30 Best Recursion-Based Coding Problems and Exercises for Programmers
As I said the best way to learn Recursion in Java is to do examples, here are some of the programming exercises which can be solved using Recursion in Java. These recursion exercises are not too difficult and fun to solve, so try to solve them yourself before looking at answers and solutions.
- How to calculate factorial using recursion in Java. (solution)
- How to Print Fibonacci Series in Java using Recursion. (solution)
- How to reverse String in Java using Recursion. (solution)
- Write a countDown(int number) method in Java using Recursion which prints countdown till zero to console, like count(3) should print 3 2 1 0
- How to reverse Linked List using Recursion. (solution)
- How to print digitsToWords(int number) for example digitToWords(321) should print three or two ones? (solution)
- How to reverse a number using Recursion in Java? (solution)
- How to calculate the sum of arithmetic series from 1 to N? (solution)
- How to calculate the power of a number like power(int number, int power) like power(2, 3) should return 8? (solution)
- How to calculate Greatest Common Division GCD using Euclid’s algorithm (solution)
- How to print nodes of trees in the pre-order traversal using recursion? (solution)
- Write a Java program to convert Decimal to binary using recursion. (solution)
- How to code a post-order traversal algorithm using recursion? (solution)
- How to implement inorder traversal of binary tree using recursion? (solution)
- How to count the number of leaf nodes in a given binary tree? (solution)
- How to implement a binary search algorithm using recursion? (solution)
- How to find all permutations of a given String in Java? (solution)
- How to calculate the sum of digits using recursion in Java? (solution)
- How to solve the Tower of Hanoi problem using recursion? (solution)
- How to implement bubble sort algorithms using recursion? (solution)
- How to implement Quick sort algorithm using recursion? (solution)
- How to implement merge sort algorithm using recursion (solution)
- Solve the Nine Queen problem in chess using Recursion (solution)
- Solve Regular Expression matching problem using recursion where you have given an input string
s
and a patternp
, implement regular expression matching with support for'.'
and'*'
where:
'.'
Matches any single character.'*'
Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
25. How to merge two sorted linked list using Recursion (solution)
26. How to calculate power of three using recursion (solution)
27. How to remove a given element form a linked list using recursion (solution)
These were a few Recursion based coding problems which you can practice to improve you understanding of Recursion and dynamic programming. Though if you are a complete beginner on Recursion and need guidance, you can also check . Recursion course on Udemy, one of the Best Course for Beginners
That’s all on this ultimate Recursion Tutorial for beginners. In this tutorial you have learned what is Recursion, how to identify if a problem can be solved using Recursion and then steps to solve a problem using Recursion programming technique.
We have also seen 20 Recursion Practice Problems and exercises you can do to learn and improve your Recursion skills. Once you are comfortable with these easy recursive exercises you can move on to more complex recursive exercises like the famous Tower of Hanoi problem and several other dynamic programming-based problem which requires recursive solutions.
I highly recommend you to try solving this problem by yourself, without taking help from the internet because that’s the only way to learn recursion, your mind needs to be trained to understand the recursive solutions. Only see the solution if you can’t solve it on your own.
Other Coding and Programing Interview Resources You may like:
- Top 5 Free Data Structure and Algorithm Courses
- 10 Courses to Prepare for Programming Job Interviews
- 20+ String Algorithms Interview Questions
- Review these Java Interview Questions for Programmers
- Top 5 Data Structure and Algorithm Books for Java Developers
- 20+ array-based Problems for interviews
- 25 Software Design Interview Questions for Programmers
- Top 30 Object-Oriented Programming Questions
- 10 Algorithms Courses Junior Developer should join
- 10 Algorithm Books Every Programmer Should Read
- 7 Best Courses to learn Data Structure and Algorithms
- Top 5 Courses to learn Dynamic Programming for Interviews
Thanks a lot for reading this article so far. If you like these recursion-based coding problems and found this article useful in learning Recursion and recursion solutions, then please share them with your friends and colleagues. If you have any questions or feedback, then please drop a note.
P. S. — If you need a resource to understand recursion patterns, I highly recommend going through this Python Object Basics: Function, Recursion, and Objects course on Coursera to learn how to identify recursive problems and how to break them down to solve using recursion.