Master the Concept of Recursion Java

Master the Concept of Recursion Java

9 mins read366 Views Comment
Updated on Dec 27, 2022 16:49 IST

This blog will make you understand the concept of Recursion in Java with the help of several problems.

2022_12_Recursion-Java.jpg

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

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

  1. 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
}
}
Copy code

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);
}
}
}
Copy code

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.
}
}
Copy code

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
}
}
Copy code

Explore- Free Java 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
}
}
Copy code

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;
}
}
Copy code

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
Copy code
Difference between Abstract class and Interface in Java
Difference between Abstract class and Interface in Java
Both abstract class and interface in java helps in achieving abstraction. They are similar in nature yet differ from each other when it comes to their usage. Let’s see what...read more
Sorting Algorithms in Java
Sorting Algorithms in Java
Sorting is the process of putting a list, a sequence of provided items, or data collection into a specific order. In this article, we will discuss different sorting algorithms in...read more
Difference Between C and Java
Difference Between C and Java
C and Java are two widely used programming languages, each with strengths and weaknesses. Both programming languages serve distinct purposes. The main difference between C and Java is that C...read more

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]
Copy code

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;
}
}
Copy code

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;
}
}
Copy code
About the Author

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