Reverse words in a given String using recursion

Reverse words in a given String using recursion

Reverse words in a given String using recursion  

Reverse words in a given String using recursion. We need to reverse words by words in a given line and not the character in a given string. We need to solve this by using backtracking and recursion logic.

Let's see simple Java code for getting the given of words in a reverse order by using recursion.

public class ReverseLineByWords {

 public static void main(String[] args) {
  
  String str = "Hello Java Discover";
  
  String finalStr = new ReverseLineByWords().reverseLine(str);
  
  System.out.println(finalStr);
  
 }
 
 public String reverseLine(String str){
  String word = "";
  int i = 0;
  for(;i<str.length();i++){
   if(str.charAt(i) == ' ') {
    word = word + " ";
    break;
   }else{
    word = word + str.charAt(i);
   }
  }

  if(i < str.length()) 
   return reverseLine(str.substring(i+1)) + word;
  
  return (word + " ");
 }
}

OUTPUT:

Discover Java Hello 

Dynamic Programming - Find nth Fibonacci number

Dynamic Programming - Find nth Fibonacci number

recursion  

Dynamic Programming (DP) is an algorithmic that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again for another subproblems. Just make use of the previously computed result by storing and by this complexity will be reduced. Usually we used to write a recursive call for getting list of Fibonacci series or to get the nth element in Fibonacci series. Here we will see simple recursive method for getting nth Fibonacci number with and without dynamic programming and latter will compare the benefits of using DP.

Find nth Fibonacci number using recursive:

public class Fibonacci {
 
 static int i = 0;
 
 public static void main(String[] args) {
  int n = 10;
  int val = fibo(n);
  System.out.println("No. of recursive calls : "+i);
  System.out.println(n +"th Fibonacci number : "+val);
  
 }
 
 public static int fibo(int n) {
  System.out.println("CALL ::: "+ (++i) + " - n: "+n);
  if(n<=2) {
   return 1;
  }
  else {
   int f = fibo(n-1) + fibo(n-2);
   return f;
  }
 }
}

OUTPUT:

CALL ::: 1 - n: 10
CALL ::: 2 - n: 9
CALL ::: 3 - n: 8
CALL ::: 4 - n: 7
CALL ::: 5 - n: 6
CALL ::: 6 - n: 5
CALL ::: 7 - n: 4
CALL ::: 8 - n: 3
CALL ::: 9 - n: 2
CALL ::: 10 - n: 1
CALL ::: 11 - n: 2
CALL ::: 12 - n: 3
CALL ::: 13 - n: 2
CALL ::: 14 - n: 1
CALL ::: 15 - n: 4
CALL ::: 16 - n: 3
CALL ::: 17 - n: 2
CALL ::: 18 - n: 1
CALL ::: 19 - n: 2
CALL ::: 20 - n: 5
CALL ::: 21 - n: 4
CALL ::: 22 - n: 3
CALL ::: 23 - n: 2
CALL ::: 24 - n: 1
CALL ::: 25 - n: 2
CALL ::: 26 - n: 3
CALL ::: 27 - n: 2
CALL ::: 28 - n: 1
CALL ::: 29 - n: 6
CALL ::: 30 - n: 5
CALL ::: 31 - n: 4
CALL ::: 32 - n: 3
CALL ::: 33 - n: 2
CALL ::: 34 - n: 1
CALL ::: 35 - n: 2
CALL ::: 36 - n: 3
CALL ::: 37 - n: 2
CALL ::: 38 - n: 1
CALL ::: 39 - n: 4
CALL ::: 40 - n: 3
CALL ::: 41 - n: 2
CALL ::: 42 - n: 1
CALL ::: 43 - n: 2
CALL ::: 44 - n: 7
CALL ::: 45 - n: 6
CALL ::: 46 - n: 5
CALL ::: 47 - n: 4
CALL ::: 48 - n: 3
CALL ::: 49 - n: 2
CALL ::: 50 - n: 1
CALL ::: 51 - n: 2
CALL ::: 52 - n: 3
CALL ::: 53 - n: 2
CALL ::: 54 - n: 1
CALL ::: 55 - n: 4
CALL ::: 56 - n: 3
CALL ::: 57 - n: 2
CALL ::: 58 - n: 1
CALL ::: 59 - n: 2
CALL ::: 60 - n: 5
CALL ::: 61 - n: 4
CALL ::: 62 - n: 3
CALL ::: 63 - n: 2
CALL ::: 64 - n: 1
CALL ::: 65 - n: 2
CALL ::: 66 - n: 3
CALL ::: 67 - n: 2
CALL ::: 68 - n: 1
CALL ::: 69 - n: 8
CALL ::: 70 - n: 7
CALL ::: 71 - n: 6
CALL ::: 72 - n: 5
CALL ::: 73 - n: 4
CALL ::: 74 - n: 3
CALL ::: 75 - n: 2
CALL ::: 76 - n: 1
CALL ::: 77 - n: 2
CALL ::: 78 - n: 3
CALL ::: 79 - n: 2
CALL ::: 80 - n: 1
CALL ::: 81 - n: 4
CALL ::: 82 - n: 3
CALL ::: 83 - n: 2
CALL ::: 84 - n: 1
CALL ::: 85 - n: 2
CALL ::: 86 - n: 5
CALL ::: 87 - n: 4
CALL ::: 88 - n: 3
CALL ::: 89 - n: 2
CALL ::: 90 - n: 1
CALL ::: 91 - n: 2
CALL ::: 92 - n: 3
CALL ::: 93 - n: 2
CALL ::: 94 - n: 1
CALL ::: 95 - n: 6
CALL ::: 96 - n: 5
CALL ::: 97 - n: 4
CALL ::: 98 - n: 3
CALL ::: 99 - n: 2
CALL ::: 100 - n: 1
CALL ::: 101 - n: 2
CALL ::: 102 - n: 3
CALL ::: 103 - n: 2
CALL ::: 104 - n: 1
CALL ::: 105 - n: 4
CALL ::: 106 - n: 3
CALL ::: 107 - n: 2
CALL ::: 108 - n: 1
CALL ::: 109 - n: 2
No. of recursive calls : 109
10th Fibonacci number : 55

If we seen above output we can get to know that just for 10th Fibonacci number total 109 recursive calls made. Also in many cases like Fibo(4), Fibo(5), Fino(3) etc., are multiple times computed for same value. So here we need to use the power of Dynamic Programming to store the computed value and need to reuse the result if same value occurs again. By this we can avoid lot of iterations/recursive call's.

Lets see converting above program to Dynamic Programming by storing the computed value and reusing it again when its need. By this lets find out how many recursive calls made for getting 10th Fibonacci number.

Find nth Fibonacci number using Dynamic Programming:

import java.util.HashMap;

public class Fibonacci {
 
 static int i = 0;
 static HashMap<Integer, Integer> map = new HashMap<>();
 
 public static void main(String[] args) {
  int n = 10;
  int val = fibo(n);
  System.out.println("No. of recursive calls : "+i);
  System.out.println(n +"th Fibonacci number : "+val);
  
 }
 
 public static int fibo(int n) {
  
  if(map.containsKey(n)) 
   return map.get(n);
  
  System.out.println("CALL ::: "+ (++i) + " - n: "+n);
  if(n<=2) {
   map.put(n, 1);
   return 1;
  }
  else {
   int f = fibo(n-1) + fibo(n-2);
   map.put(n, f);
   return f;
  }
 }
}

OUTPUT:

CALL ::: 1 - n: 10
CALL ::: 2 - n: 9
CALL ::: 3 - n: 8
CALL ::: 4 - n: 7
CALL ::: 5 - n: 6
CALL ::: 6 - n: 5
CALL ::: 7 - n: 4
CALL ::: 8 - n: 3
CALL ::: 9 - n: 2
CALL ::: 10 - n: 1
No. of recursive calls : 10
10th Fibonacci number : 55

Now we can compare the no. of recursive calls made my 1st program and 2nd program exactly to get the same output of 10th Fibonacci number. If we see 1st program taken 109 recursive calls and 2nd dynamic program taken only 10 recursive calls for same problem and output. 

Multiply 2 numbers using recursion

Multiply 2 numbers using recursion

recursion  

In many interviews, interviewer may asked to write a simple program to multiply 2 integers without using '*' operator. We can solve this program by many ways like using looping, recursion, bitwise operator etc.,

In this tutorial we will see how to multiply 2 integers using recursion. As simple as method takes 1st (n) and 2nd (m) integer as argument and make recursive call m times. Each time summing with n and returning the final sum.

Lets see simple example to multiply 2 integers using recursion.

public class MultiplyNumber {

 public static void main(String[] args) {
  
  int val = new MultiplyNumber().multiply(7, 5);
  System.out.println(val);
 }
 
 public int multiply(int n, int m) {
  if(m>n) {
   int tmp = n;
   n = m;
   m = tmp;
  }
  return multiply(n,m,0);
 }
 
 public int multiply(int n, int m,int val) {
  if(m <= 0) return val;
  return multiply(n,m-1,val+n);
 }
}

OUTPUT:

35