Recursion is often dreaded by programmers as its very difficult for many
programmers to visualize and understand, but it's a useful problem solving
technique which often result in better, simpler and more concise code than
their iterative solutions. That begin said, it's often difficult to come up
when to use
recursion
to solve a
coding problem. In general, you should use recursion if a problem can be broken down into
sub-problems which are exactly the same as original problem. For example,
finding a node in a binary tree.

If you are asked to find a node with give value in a binary tree than you
can solve this with recursion. Why? because you can breakdown the problem
into sub-problems which are exactly the same like finding a node in binary
tree is same as finding the node in left subtree and right subtree.

**This is the ke**y. Once you understand that half of the battle is won, the rest is just how to write the recursive solution, and that's where these practice questions will help you.

In this article, I'll give you some tips to identify when to use recursion
as well as some common recursion based coding problems. Once you have gone
through them, you will be able to use the concepts you learned to solve a
complex real-world problems and also gain the confidence to deal with any
recursion related problem in coding interview.

In the past, I have shared dynamic programming questions, system design questions as well data structure and algorithms questions for programmers, which you can also use for a comprehensive practice.

##
__20+ Recursion based Coding Problems__

Without wasting any more of your time, here are some of the most common
problems which are based upon recursion.

**1. Write a method to check if a node exists in a binary tree or not. If the node exists then return true otherwise return false**.

```
Example
1
/ \
2 3 , findNode(5) ==> true, findNode(10) == false
/ \ / \
4 5 6 7
```

**2. Write a program to find all permutations of a given String?**(solution)

**3. Given a binary tree, write a method checkBST() to determine if it is a Binary Search Tree. The method should return true if the given tree is a valid binary search tree or false otherwise.**

```
Example
20
/ \
15 30
/ \
14 18
output ==> true
20
/ \
30 15
/ \
14 18
output ==> false
```

**4. Write a program to reverse a linked list using recursion in Java or any other programming language?**(solution)

**5. Write a program to find the Nth number in the Fibonacci series (solution)**

Example: Fibonacci series starts with double 1 and where next number is sum
of previous two number, like 1 1 2 3 5 8 13

```
fibonacci(2) = 1
fibonacci(4) = 3
fibonacci(5) = 3
```

**6. Given a binary tree, Write a method findMaxSumLevel to return the level that has the maximum sum. In case the tree is empty return -1. This problem is also known as**

**Find Max Sum Level Problem.**

```
Example
0 1
/ \
1 2 3 ==> 2
/ \ / \
2 4 5 6 7
```

**7. Write a program to find the greatest common divisor or GCD of a given number? (solution)**

8. Write a program to convert a decimal number to a binary number? (solution)

**9. Write a program to print pre-order traversal of binary tree? (solution)**

10. Write a program to print in-order traversal of binary tree using
recursion? (solution)

**11. Write a program to print post-order traversal of binary tree? (solution)**

12. Write a program to check if a given linked list is a palindrome?
(solution)

**13. Write a program to check if a given String is a palindrome()? (solution)**

14. Write a program to remove duplicates from an unsorted linked list? (solution)

**15. Write a program to remove all adjacent duplicates from a string? (solution)**

16. Write a program to calculate the sum of digits in a given String? (solution)

**17. Write a program to find the length of a given linked list? (solution)**

18. Write a program to reverse a given Stack? (solution)

**19. Write a program to implement a quicksort algorithm using recursion? (solution)**

**20. Write a method countLeaves() to find the total number of leaf nodes in a binary tree. If there are no leaf nodes, return 0 (solution)**

```
Example
1
/ \
2 3 ==> # count = 4
/ \ / \
4 5 6 7
```

**21. Write a Program to print number 1 to 100 without using loop in Java?**(solution)

###
__Tips to Solve Coding
Problems with Recursion__

When faced with coding problems, there are few things you can consider to
decide whether you should use recursion or not such as:

1. If a problem can be broken down into smaller sub-problems that can be
solved in the same ways as the original problem

2. If the iterative solution of a problem has an arbitrary number of loops.

3. Problems involving recursive data structures like string, linked list,
and binary trees.

These are not hard-and-fast rules but provides enough hints to decide when
to use recursion. If you are wondering what is a recursive data structure or
why we called a
string,
linked list,
and
binary tree
a recursive data structure then let me tell you that, we call them a
recursive data structure because if you take one element out of them they
are still the same.

For example, if you take one node out of the binary tree, it's still a
binary tree, similarly with string and linked list. Another thing, you can
apply all algorithms into a subset in the same way as you apply to the
original data structure. For example, the
pre-order traversal
will work in a full tree in the same way it works in the left or right
subtree.

##
__Useful Resources to learn Recursion__

As I said, Recursion is often dreaded by developers, but it's an important
problem-solving technique and you just can't afford to ignore that. Luckily
now there are many courses that you can take to level up your Recursion
skill and add this powerful style into your problem-solving skills.

Without wasting any more of your time, here are a couple of useful resources
to learn Recursion in-depth, particularly for coding interviews.

This is an excellent course to master Recursion for coding interviews. In
this course, you will not only learn how to solve coding problems with
recursion but also how and when to use recursion with different data types
and data structures.

You will also be tested with some of the most common recursion interview
questions to build the knowledge and confidence needed to solve complex
real-world problems and unknown problems on real coding interviews.

Just in case if you are not familiar with JavaScript, this course is also
available with Python and Java and you should use it in the language you are
most comfortable with.

Educative as a platform is also a great resource for coding interviews and you can get all of their course access by just $14.9 per month by joining

**Educative subscription**. I highly recommend this to anyone preparing for programming job interviews.

That's all about some of the

**best, most common Recursion interview questions.**You have not only learned how to solve frequently asked recursive problems but also how and when to apply recursion. This is an important skill that will go a long way in your career. I am sure, now you should have more confidence and knowledge to solve the recursion-based problems in real interviews.
Some

Thanks for reading this article so far. If you find these

**Useful Resources**for Coding Interviews:- Top 5 Free Data Structure and Algorithm Courses
- 20+ String Algorithms Interview Questions
- 10 Books to Prepare Technical Programming/Coding Job Interviews
- 10 Courses to Prepare for Programming Job Interviews
- 10 Algorithm Books Every Programmer Should Read
- Top 5 Data Structure and Algorithm Books for Java Developers
- Review these Java Interview Questions for Programmers
- 20+ array-based Problems for interviews
- 10 Algorithms Courses Junior Developer should join in 2021
- 7 Best Courses to learn Data Structure and Algorithms
- 25 Software Design Interview Questions for Programmers
- Top 30 Object-Oriented Programming Questions
- Top 5 Courses to learn Dynamic Programming for Interviews
- 10 Best Courses to learn System Design for Interviews
- 50 SQL and Database Interview Questions with Answers

Thanks for reading this article so far. If you find these

*recursion interview questions*useful 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 more practice, including dozens more problems and solutions for each pattern, check out

**Grokking Dynamic Programming Patterns**for Coding Interviews on Educative. It's an excellent, text-based interactive course to build your Dynamic programming skills.

## No comments :

## Post a Comment