Master the Concept of Recursion Java
This blog will make you understand the concept of Recursion in Java with the help of several problems.
In computer science, recursion is frequently employed to solve large problems by partitioning them into simpler ones. A function can directly or indirectly invoke itself through the mechanism of recursion. The recursive function is the name given to the related function. Recursive algorithms can be used to solve some complex problems fairly quickly. Here we will understand the Recursion Java.
Must read: What is Java?
Table of Content
- What is the Base Condition in Recursion?
Explore- Java Online Courses & Certifications
What is the Base Condition in Recursion?
In a recursive function, the base case is solved, and the larger problem’s answer is given in terms of smaller problems. The purpose of the base condition is to prevent a recursive function from running indefinitely; when the base condition is satisfied, the function knows when to terminate.
Easy Level
- Create a recursion in Java to determine whether a string is a palindrome or not.
If the string is a palindrome, return 1, else return 0.
Problem Constraints
1 <= |A| <= 50000
String A consists only of lowercase letters.
Input Format
The first and only argument is a string A.
Output Format
Return 1 if the string A is a palindrome; else, return 0.
Example
Input 1:
A = “abcba”
Output 1:
1
Input 2:
A = “abc”
Output 2:
0
Explore- Data Types in Java – Primitive and Non-Primitive Data Types Explained
Implementation:
public class Solution { public int solve(String A) { int n = A.length(); //get the size of string A if(n == 0){ //base condition return 1; } if(isPalindrome(A, 0, n-1)){ //start checking the strings from extreme ends return 1; } return 0; } public boolean isPalindrome(String A, int s, int e){ if(s >= e){ return true; } if(A.charAt(s) != A.charAt(e)){ return false; } return isPalindrome(A, s+1, e-1); //increase and decrease the start and end indexes respectively }}
Must read: Strings in Java Explained
2. The Fibonacci numbers are the numbers in the following integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..
Fn = Fn-1 + Fn-2
Given a number N, find and return the Nth Fibonacci Number.
It is given that F0 = 0 and F1 = 1.
Problem Constraints
0 <= A <= 20
Input Format
The first and only argument is an integer A.
Output Format
Return an integer denoting the Ath term of the sequence.
Example Input
Input 1:
A = 2
Input 2:
A = 9
Example Output
Output 1:
1
Output 2:
34
Explanation
Explanation 1:
f(9) = f(8) + f(7) = 21 + 13 = 34
Explanation 2:
f(9) = f(8) + f(7) = 21 + 13 = 34
Implementation
public class Solution { public int findAthFibonacci(int A) { if(A==0) { return 0; } if(A==1 || A==2){ return 1; } else{ return findAthFibonacci(A-1) + findAthFibonacci(A-2); } }}
3. Given a string A, print the whole string in reverse order.
Problem Constraints
1 <= |s| <= 1000
Input Format
The first line of input contains a string S.
Output Format
Print the character of the string S in reverse order.
Example Input
Input 1:
recursion
Input 2:
naukrilearning
Example Output
Output 1:
noisrucer
Output 2:
gninraelirkuan
Example Explanation
Explanation 1:
Reverse order of string
Implementation
import java.lang.*;import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.next(); //input string int n = str.length(); char[] st = str.toCharArray(); //string to char array if(str == null || n <= 1){ System.out.print(str); } String s = swap(st, 0, n-1); //swap the characters from start and end System.out.print(s); } public static String swap(char[] st, int s, int e){ //method to swap characters if(s >= e){ return new String(st); } else { char tmp = st[s]; st[s] = st[e]; st[e] = tmp; } return swap(st, s+1, e-1); //return the recursive swap method. }}
Read out- Implementing Array in Java
4. Given a number ‘num’, find the sum of the digits in the input number using recursion.
Problem Constraints
1 <= A <= 109
Input Format
The first and only argument is an integer A.
Output Format
Return an integer denoting the sum of digits of the number A.
Example Input
Input 1:
A = 46
Input 2:
A = 11
Example Output
Output 1:
10
Output 2:
2
Example Explanation
Explanation 1:
Sum of digits of 46 = 4 + 6 = 10
Explanation 2:
Sum of digits of 11 = 1 + 1 = 2
public class Solution { public int solve(int A) { int sum = 0; //variable to calc sum if(A == 0){ //base condition return 0; } return (A % 10 + solve(A/10)); //recursion to calculate sum }}
Explore- Free Java Courses
Best-suited Java courses for you
Learn Java with these high-rated online courses
Medium Level
5. Determine whether or not the given number A is a magic number.
If the sum of a number’s digits can be calculated down to a single digit repeatedly by adding the sum after each addition, the number is said to be a magic number. A number is considered to be magical if the solitary digit is 1.
Problem Constraints
1 <= A <= 109
Input Format
The first and only argument is an integer A.
Output Format
Return an 1 if the given number is magic else return 0.
Example Input
Input 1:
A = 83557
Input 2:
A = 1291
Example Output
Output 1:
1
Output 2:
0
Example Explanation
Explanation 1:
Sum of digits of (539559) = 37
Sum of digits of (37) = 10
Sum of digits of (10) = 1.
Single digit is 1, so it’s a magic number. Return 1.
Explanation 2:
Sum of digits of (12883) = 22
Sum of digits of (22) = 4
A single digit is not 1, so it’s not a magic number. Return 0.
Implementation
public class Solution { public int solve(int A) { int t = A; while(t > 9){ t = isMagic(t); //calling magic function if the input number is greater than 9 } if(t == 1){ //Base Condition return 1; } return 0; } public int isMagic(int A){ if(A == 0){ return 0; } return (A % 10 + isMagic(A/10)); //adding the digits of the number by division and modulus }}
6. Implement a power function using recursion. The power function looks like pow(A, B) % C. In other words, given A, B and C, Find (A^B % C).
Note: The remainder of the division cannot be negative i.e. the answer you return is non-negative.
Problem Constraints
-109 <= A <= 109
0 <= B <= 109
1 <= C <= 109
Input Format
Three integers A, B, and C
Output Format
Return an integer.
Example Input
A = 2, B = 4, C = 5
Example Output
1
Example Explanation
2^4 % 5 = 16 % 5 = 1
Implementation
public class Solution { public int pow(int A, int B, int C) { long ans = 0; if(A == 0){ return 0; } if(B == 0){ return 1; } long ha = pow(A, B/2, C); long he = ha * ha; if(B % 2 == 0){ ans = he % C; } else{ ans = ((he % C) * (A % C)) % C; } if(ans < 0){ return (int)((C + ans)%C); } return (int)ans; }}
7. Write a function to return the kth symbol. We enter a 0 in the first row. Now, we refer to the previous row for each additional row and change each instance of 0 to 01 and 1 to 10.
Return the symbol in row X with index Y, given row number X and index Y. (Y values have a 1-indexed range.)
Problem Constraints
1 <= X <= 20
<= Y <= 2X – 1
Input Format
The first argument is an integer X.
The second argument is an integer Y.
Output Format
Return an integer denoting the Yth indexed symbol in row X.
Example Input
Input 1:
X = 2
Y = 1
Input 2:
X = 2
Y = 2
Example Output
Output 1:
0
Output 2:
1
Example Explanation
Explanation 1:
Row 1: 0
Row 2: 01
Explanation 2:
Row 1: 0
Row 2: 01
Implementation
public class Solution { public int solve(int A, int B) { if(A==1) return 0; if(A==2) return B==1 ? 0 : 1; if(B%2==0) return solve(A-1, B/2) == 0 ? 1 : 0; else return solve(A-1, B/2 + 1); }} // Example // 0// 01// 0110// 01101001 // even case:// (A-1)th row, B/2th inverted symbol// odd case:// (A-1)th row, ((B/2)+1)th symbol
Advance Level
8. Two successive values in the gray code differ from each other in binary form by just one bit. Print the series of gray codes given a non-negative integer A that represents the total number of bits in the code.
The first 0 in a grey code sequence is required.
Problem Constraints
1 <= A <= 16
Input Format
The first argument is an integer A.
Output Format
Return an array of integers representing the gray code sequence.
Example Input
Input 1:
A = 2
Input 2:
A = 1
Example Output
output 1:
[0, 1, 3, 2]
output 2:
[0, 1]
Must read- Arraylist in Java
Example Explanation
Explanation 1:
for A = 2 the gray code sequence is:
00 – 0
01 – 1
11 – 3
10 – 2
So, return [0,1,3,2].
Explanation 2:
for A = 1 the gray code sequence is:
00 – 0
01 – 1
So, return [0, 1].
Implementation
public class Solution { public ArrayList<String> grayCode(int A) { if(A==1){ ArrayList<String> res = new ArrayList<>(); res.add("0"); res.add("1"); return res; } ArrayList<String> result = graycode(A-1); //get the gray code of previous A-1 ArrayList<String> temp = new ArrayList<>(); //traverse the string in seq order and add 0 to the numbers for(int i=0;i<result.size();i++){ String tempStr = result.get(i); temp.add("0" + tempStr); } //traverse the string in reverse order and add 1 to the numbers for(int i=result.size();i>=0;i--){ String tempStr = result.get(i); temp.add("1" + tempStr); } return temp; }} //Dry run // For 1 bit you have only two choices// 1 bit ------> [0,1] // For 2 bits, write the numbers of 1 bit (0,1) first from start to end and in second line from end to start// 2 bit ------> [0, 1 (row 1)// 1, 0] (row 2) // Now add 0 to row 1 and 1 to row 2 (add at start)// 2 bit would look like:// [00, 01 // 11, 10] // In decimal it will be 0,1,3,2 // For 3 bits, write the numbers of 2 bits (00, 01, 11, 10), once from start to end and then again in reverse order// 3 bits ------> [00, 01, 11, 10 (row 1)// 10, 11, 01, 00] (row 2) // Now add 0 to row 1 and 1 to row 2 (add at start)// 2 bit would look like:// [000, 001, 011, 010// 110, 111, 101, 100]
Check out- ArrayList vs. LinkedList
9. In the traditional Towers of Hanoi puzzle, you have three towers numbered 1 through 3 from left to right and A discs of various sizes that can slide onto any tower and are numbered 1 through A from top to bottom.
The problem begins with discs arranged from top to bottom in ascending order of size (i.e., each disc sits on top of an even larger one).
The following limitations apply to you:
- Only one disk can be moved at a time.
- On top of one tower, a disc is slid onto the top of another tower.
- It is impossible to stack discs on top of one another.
- You must figure out the answer to the Tower of Hanoi puzzle.
- You must deliver a 2D array with M x 3 dimensions, where M is the bare minimum of moves required to solve the issue.
- There should be three integers (disc, start, and end) in each row, where:
discs being moved: total number of discs
the number of the tower from which the disc is being pushed at the start, and the number of the tower it is being transported to a stop.
Problem Constraints
1 <= A <= 18
Input Format
The first argument is the integer A.
Output Format
Return a 2D array with dimensions M x 3, as mentioned above in the description.
Example Input
Input 1:
A = 2
Input 2:
A = 3
Example Output
Output 1:
[1 1 2 ] [2 1 3 ] [1 2 3 ]
Output 2:
[1 1 3 ] [2 1 2 ] [1 3 2 ] [3 1 3 ] [1 2 1 ] [2 2 3 ] [1 1 3 ]
Example Explanation
Explanation 1:
- We shift the first disk to the middle tower.
- We shift the second disk to the last tower.
- We finally shifted the first disk from the middle tower to the last tower.
Explanation 2:
We can see that this is the only unique path with minimal moves to move all disks from the first to the third tower.
Implementation
public class Solution { int idx = -1; int[][] arr; // outside all functions to access public int[][] towerOfHanoi(int A) { int mSize = (1<<A)-1; // size of the Array will be 2^A - 1 arr = new int[mSize][3]; TOH(A, 1, 2, 3); // calling TOH with no of discs, 1st tower, 2nd, 3rd return arr; } public void TOH(int disc, int start, int temp, int stop) { if (disc==0) return; TOH(disc-1, start, stop, temp); // moving n-1 discs from start to temp using destination arr[++idx][0] = disc; // Storing the output, Ath disc is moving into destination arr[idx][1] = start; arr[idx][2] = stop; TOH(disc-1, temp, start, stop); // moving n-1 discs from temp to destination using start (1st tower) return; }}
10. Given a string expression containing numbers and operators. Return all outcomes from computing all possible combinations of grouping numbers and operators. You can give the response in any sequence.
Problem Constraints
1 <= expression.length <= 20
expression consists of digits and the operator ‘+’, ‘-‘, and ‘*’.
All the integer values in the input expression are in the range [0, 99].
Input Format
A string expression
Output Format
Return an array of integers representing the result of different expressions.
Example Input
Input 1:
expression = “2-1-1”
Input 2:
expression = “2*3-4*5”
Example Output
output 1:
[0,2]
output 2:
[-34,-14,-10,-10,10]
Example Explanation
Explanation 1:
((2-1)-1) = 0
(2-(1-1)) = 2
Explanation 2:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Implementation
class Solution { // function to get the result of the operation int perform(int x, int y, char op) { if(op == '+') return x + y; if(op == '-') return x - y; if(op == '*') return x * y; return 0; } public List<Integer> diffWaysToCompute(String expression) { List<Integer> results = new ArrayList<Integer>(); boolean isNumber = true; for(int i = 0; i < expression.length(); i++) { // check if current character is an operator if(!Character.isDigit(expression.charAt(i))) { // if current character is not a digit then // exp is not purely a number isNumber = false; // list of first operands List<Integer> left = diffWaysToCompute(expression.substring(0, i)); // list of second operands List<Integer> right = diffWaysToCompute(expression.substring(i + 1)); // performing operations for(int x : left) { for(int y : right) { int val = perform(x, y, expression.charAt(i)); results.add(val); } } } } if(isNumber) results.add(Integer.valueOf(expression)); return results; }}
Contributed By: Neetika Khandelwal
Blogs people also read in Java:
Data Type in Java | Features of Java Programming | Jump Statement in Java | OOPS in Java | Java Interview Questions | Python vs Java | Conditional Statement in Java | Data Abstraction in Java | Super Keyword in Java | Method Overloading in Java | Difference between Java and Javascript | Constructors in Java | Method Overriding in Java | Data Structure and Algorithm in Java | Abstract class in Java | Loops in Java
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
