Merge sort example in core java recursion

Merge Sort:

our final example of recursion is the merge-sort.This is more sorting technique.While the bubble,insertion and selection sort take O(N^2) time.The merge sort is O(N*log N).

Sample Code:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class MergeApp
{
public static void main(String[] args)
{
int[] arrayA={23,47,81,95};
int[] arrayB={7,14,39,55,62,74};
int[] arrayC=new int[10];

merge(arrayA,4,arrayB,6,arrayC);
display(arrayC,10);

}

private static void display(int[] arrayC, int size)
{
for(int j=0;j<size;j++)
System.out.println(arrayC[j] + "  ");
System.out.println(" ");
}

private static void merge(int[] arrayA, int sizeA, int[] arrayB, int sizeB,int[] arrayC)
{
int aDex=0,bDex=0,cDex=0;

while (aDex <sizeA && bDex < sizeB)
if(arrayA[aDex] < arrayA[bDex])
arrayC[cDex++] = arrayA[aDex++];
else
arrayC[cDex++] =arrayB[bDex++];

while(aDex < sizeA)
arrayC[cDex++] =arrayA[aDex++];

while(bDex < sizeB)
arrayC[cDex++] = arrayB[bDex++];
}

}

Divide-and-Conquer Algorithms and Tower of Hanoi Puzzle in core-java

What is Divide-and-Conquer Algorithms?

Divide-and-Conquer Algorithms:

The Divide-and-Conquer approach is commonly used with recursion.The recursive binary search is an example of the divide-and-conquer . actually you divide big problem into small problem and solve them separately.A divide and conquer approach usually involves a method that contains two recursive calls to itself,one for each half of the problem.

The Tower of Hanoi:

The Towers of hanoi is an ancient puzzle consisting of a number of disks placed on three columns.Three disks all have different diameters and holes in the middle so they will fir over the columns.

The Recursive Algorithm to solve this problem:

The solution to the Towers of Hanoi puzzle can be expressed recursively using the notion of sub trees.Suppose you want to move all the disks from a source tower to a destination tower .you have an intermediate tower available .

1. Move the sub tree consisting of the top n-1 disks from S to I.
2. Move the remaining disk from S to D.
3. Move the sub tree from I to D.

Code Sample:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */

public class TowerofHanoiApp
{
   static int nDisks=3;
 
public static void main(String[] args)
{
doTowerofHanoi(nDisks,'A','B','C');
}

private static void doTowerofHanoi(int topN, char from, char inter, char to)
{

if(topN == 1)
System.out.println("Disk 1 from "+from + " to "+to);
else
{
doTowerofHanoi(topN-1, from, to, inter);
System.out.println("Disk" + topN + "from" + from +" to" + to);
doTowerofHanoi(topN-1, inter, from, to);
}
}


}

Recursive Binary Search example in core java

Binary Search:

We can make binary search recursive like below . first we will see simple binary search then will see recursive binary search.

Simple Binary Search:

public int find(long searchKey)
{
int lowerbound=0;
int uperbound=nElems-1;
int curIn;

while(true)
{
curIn =(lowerbound+uperbound)/2;
if(a[curIn] == searchKey)
return curIn;

else if(lowerbound > uperbound)
return nElems;
else
{
if(a[curIn] < searchKey)
lowerbound =curIn +1;
else
uperbound =curIn-1;
}
}
}


Recursive Binary Search:

public int recFind(long searchKey ,int lowerBound,int upperBound)
{
int curIn;
curIn =(lowerbound+uperbound)/2;
if(a[curIn] == searchKey)
return curIn;

else if(lowerbound > uperbound)
return nElems;
else
{
if(a[curIn] < searchKey)
recFind(searchKey, curIn+1, upperBound);
else
return recFind(searchKey, lowerBound, curIn-1);
}
}

Recursion Anagrams example in core-java

Anagrams:
Some times anagrams suits in a situation in which recursion provides a neat solution to a problem.A permutation is an arrangement of things in a definite order.Suppose you want to list all the anagrams of a specified words.

For example: Anagram of Cat:

• cat
• cta
• atc
• act
• tca
• tac

So Algorithm to write a program to anagram a word:

1. Anagram the rightmost n-1 letters .
2. Rotate all n letters.
3. Repeat these steps n times.

Example Code:

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

/**

 * 

 */

/**

 * @author Abhinaw.Tripathi

 *

 */

public class AnagramApp 

{

   static int size;

   static int count;

   static char[] arrChar =new char[100];

   

public static void main(String[] args) throws IOException 

{

System.out.println("Enter a word:  ");

        String input =getString();

        size=input.length();

        count=0;

        for(int j=0;j<size;j++)

        {

        arrChar[j] =input.charAt(j);

        doAnagram(size);

        }

}

private static void doAnagram(int newsize) 

{

      if(newsize == 1)

      {

     return;

      }

      for(int i=0;i<newsize;i++)

      {

     doAnagram(newsize-1);

     if(newsize==2)

     displayWord();

     rotate(newsize);

      }

}

private static void rotate(int size2)

{

int j;

int position =size- size2;

char temp=arrChar[position];

for(j=-position+1;j<size;j++)

  arrChar[j-1]=arrChar[j];

arrChar[j-1]=temp;

 

}

private static void displayWord() 

{

if(count < 99)

System.out.println(" ");

if(count < 9)

System.out.println(" ");

System.out.println(++count + " ");

for(int j=0;j<size;j++)

System.out.println(arrChar[j]);

System.out.println("  ");

System.out.flush();

if(count%6 == 0)

System.out.println(" ");

}

private static String getString() throws IOException 

{

InputStreamReader isr=new InputStreamReader(System.in);

BufferedReader br=new BufferedReader(isr);

String s=br.readLine();

return s;

}

}

Recursion in Java example

What is Recursion?

Recursion is a programming technique in which a method calls itself.This may sound like a strange thing to do or even a catastrophic mistakes.
Recursion is however, one of the most interesting and one of the most surprising effective techniques in programming.we will discuss the strength and weakness of recursion and show how a recursion approach can be transformed into a stack-based approach.

Triangular Numbers:

A band of mathematicians in ancient Greece who worked under Pythagoras and felt a connection with the series of numbers 1,3,6,10,15,21,........
Can you find the next member of this series?

The nth term in the series is obtained by adding n to the previous term.thus second term is found by adding 2 to the first term(which is 1),giving 3.The third term is 3 added to the second term(which is 3) giving 6, and so on.The numbers in the series are called Triangular Numbers.


Finding the nth Term Using a Loop:

int traingle(int n)
{
  int total=0;

while(n>0)
 {
    total=total+n;
    --n;
 }

  return total;
}

The method cycles around the loop n times,adding n to total the first time,n-1 the 2nd time and so on down to 1,quitting  the loop when n becomes 0 .


Finding the nth Term Using Recursion:

1. The first column,which has the value n.
2. The sum of all the remaining columns.

Code implementation:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class TraingleApp
{
   static int theNumber;

public static void main(String[] args) throws IOException
{
System.out.println("Enter a number:");
        theNumber=getInt();    
        int answer=traingle(theNumber);
        System.out.println("Traingle=" +answer);
}

public static int traingle(int n)
{
if(n==1)
return 1;
else
return (n+traingle(n-1));
}

private static int getInt() throws IOException
{
String s=getString();
return Integer.parseInt(s);
}


private static String getString() throws IOException
{
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
String s=br.readLine();
return s;
}

}


Characteristics of Recursive Methods:

• It calls itself.
• When  it calls itself,it does so to solve a smaller problem.
• there is some version of the problem that is simple enough that the routine can solve it and return ,without calling itself.

Is Recursion Efficient:

Calling a method involves certain overhead such as Memory but it can be controlled control must be transferred from the location of the call to the beginning of the method.

In the case of traingle() method its probable that as a result of the overhead, the while loop approach executes  more quickly than the recursive approach.

Recursion is usually used because it simplifies a problem conceptually not because it is inherently more efficient.

Factorial Example in Recursion:

int factorial(int n)
{
  if(n==0)
   {
       return 1;
   }

   else
    {
      return (n * factorial(n-1));

    }
}

How to check if a Binary Tree is BST or not?

What is Binary Search Tree(BST)?

A binary search tree (BST) is a node based binary tree data structure.

Must have these Properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Implementation:

/**

 * 

 */

package com.bst;

/**

 * @author Abhinaw.Tripathi

 *

 */

class Node

{

int data;

Node left,right;

public Node(int item)

{

this.data=item;

left=right=null;

}

}

public class BinaryTree

{

/**

* 

*/

private Node root;

public BinaryTree() 

{

// TODO Auto-generated constructor stub

}

public boolean isBSTUtil(Node node,int min,int max)

{

if(node == null)

return true;

if(node.data < min || node.data> max)

return false;

return (isBSTUtil(node.left, min, node.data-1) && isBSTUtil(node.right, node.data+1, max));

}

public boolean isBST()  

{

        return isBSTUtil(root, Integer.MIN_VALUE,Integer.MAX_VALUE);

    }

 

/**

* @param args

*/

public static void main(String[] args) 

{

// TODO Auto-generated method stub

BinaryTree tree = new BinaryTree();

        tree.root = new Node(4);

        tree.root.left = new Node(2);

        tree.root.right = new Node(5);

        tree.root.left.left = new Node(1);

        tree.root.left.right = new Node(3);

 

        if (tree.isBST())

        {

            System.out.println("IS BST");

        }

        else

        {

            System.out.println("Not a BST");

        }

}

}

Time Complexity: O(n)

Auxiliary Space : O(1) 

If Function Call Stack size is not valid, otherwise O(n)

How to check a Linked-List is a Palindrome.

Solution Approach:

First thing is we should know about palindrome.

What is Palindrome?
The list must be the same backwards and forwards such as

0-> 1 -> 2->1->0 This leads us to our first solution.

This problem can solved in many ways,

1. Reverse and Compare
2. Iterative Approach
3. Recursive Approach

Among three i will first solve this problem using Iterative Approach just see the below 

Implementation:

public boolean isPalindrome(LinkedListNode head)

{

LinkedListNode fast =head;

LinkedListNode slow =head;

Stack<Interger> stack=new Stack<Interger>();

while(fast!=null && fast.next !=null)

{

 stack.push(slow.data);

 slow=slow.next;

 fast=fast.next.next;

 

}

if(fast!=null)

{

  slow =slow.next;

}

while(slow!=null)

{

int top=stack.pop().intValue();

if(top!=slow.data)

                {

   return false;

}

slow=slow.next;

}

return true;

}

Now you can try others too......

Write an algorithm to find the k'th to last element of a singly linked list.

We can approach this problem in two ways one using recursive way and other using non recursive way.if you will use recursive way then its complexity will be o(n) where n=number of elements in the linked-list.

Solution 1: if the linked list size is known then the problem is very easy such as
             
let say the size if the size is known  then kth to last element is the (length - k)th element .

Solution 2:

public static int nthToLast(LinkedListNode head,int k)
{
   if(head == null)
    return 0;

int i=nthToLast(head.next,k)+ 1;
for(i==k)
{
  System.out.println(head.data);
}
return i;
}

Since it is recursive solution then it takes o(n) space due to recursive calls.