# Algorithm and Data Structure Basics - Recursion

|   Source

#### Common Model of Recursion

Obj recursion(Obj o){
if(baseCondition){
/*
You need to return here, so that recursion part can use the basic value which is returned back
*/
return baseConditionResult;
}else{
o = some_expression;
recursion(o);
}
}


If there are other expression before or after recursion call, make sure you run it after each call back, because these expressions are part of method, and you want to call the full method for each recursion. Check "Hanoi" example below for detail.

#### Problem in Recursion

Since system using stack to save return values from each callback, it's really easy to get memory overflow problem.

#### Hanoi

##### Rule
1. Move plate when number of plate is 1 (In code below, we want to printout basic value);

2. If number of plates on a tower is more than 1 (assume n), move first n-1 plate, then move the bottom plate.

##### Code
/**
Result:
Dist 1 from A  to C
Dist 2 from A to B
Dist 1 from C  to B
Dist 3 from A to C
Dist 1 from B  to A
Dist 2 from B to C
Dist 1 from A  to C
*/
public class Hanoi {

static int nDisks = 3;

public static void doTowers(int topN, char from, char inter, char to){
if(topN == 1)
System.out.println("Dist " + topN + " from " + from + " to " + to);
else{
//Move top n-1 from start tower to mid tower
doTowers(topN-1, from, to, inter);
System.out.println("Dist " + topN + " from " + from + " to " + to);
//Move top n-1 from mid tower to end tower
doTowers(topN-1, inter, from, to);
}
}

public static void main(String[] args) {
doTowers(nDisks, 'A', 'B', 'C');
}

}


To make code looks clear, I draw a draft of the sequence of recursion call for the code above. Note the purpose numbers are the sequence of call:

../images/articles/2015/algorithm/hanoi_graph.png

#### Merge Sort

##### Code
/*
Output:
72 90 45 126 54
45 54 72 90 126
*/
public class MergeSort {

private long[] theArray;
private int nElems;

public MergeSort(int max){
theArray = new long[max];
nElems = 0;
}

public void insert(long value){
theArray[nElems] = value;
nElems++;
}

public void display(){
for(int j=0; j<nElems; j++){
System.out.print(theArray[j] + " ");
}
System.out.println("");
}

public void mergeSort(){
long[] workspace = new long[nElems];
recMergeSort(workspace, 0, nElems-1);
}

private void recMergeSort(long[] workspace, int lowerBound, int upperBound){
if(lowerBound == upperBound)
return;
else{
int mid = (lowerBound + upperBound)/2;
recMergeSort(workspace, lowerBound, mid);
recMergeSort(workspace, mid+1, upperBound);
merge(workspace,lowerBound, mid+1, upperBound);
}
}

private void merge(long[] workspace, int lowPtr, int highPtr, int upperBound){
int j=0;
int lowerBound = lowPtr;
int mid = highPtr-1;
int n = upperBound - lowerBound +1; //# of items

while(lowPtr <= mid && highPtr <= upperBound){
if(theArray[lowPtr]<theArray[highPtr]){
workspace[j++] = theArray[lowPtr++];
}else{
workspace[j++] = theArray[highPtr++];
}
}

while(lowPtr <= mid){ //upper side are gone, some lower side left
workspace[j++] = theArray[lowPtr++];
}
while(highPtr<=upperBound){ //lower side are gone, some upperside left
workspace[j++] = theArray[highPtr++];
}

for(j=0; j<n; j++){//copy back
theArray[lowerBound+j] = workspace[j];
}
}

public static void main(String[] args) {
int maxSize = 100;
MergeSort arr = new MergeSort(maxSize);
arr.insert(72);
arr.insert(90);
arr.insert(45);
arr.insert(126);
arr.insert(54);
arr.display();

arr.mergeSort();
arr.display();
}

}

/**
Output:
45 54 72 90 126
Found 54
**/
class BinarySearch {

private long[] a;
private int nElems; //count how many existing elements in array

public BinarySearch(int max){
a = new long[max];
nElems = 0;
}

public int size(){
return nElems;
}

public int find(long searchKey){
return recFind(searchKey, 0, nElems-1);
}

private int recFind(long searchKey, int lowerBound, int upperBound){
int curIn;

curIn = (lowerBound + upperBound)/2;
if(a[curIn] == searchKey){
return curIn;
}
else if(lowerBound > upperBound){
return nElems; //cannot find
}
else{
if(a[curIn]<searchKey)
return recFind(searchKey, curIn+1, upperBound); //check larger half
else
return recFind(searchKey, lowerBound, curIn-1);
}
}

public void insert(long value){
int j;
for(j=0; j<nElems; j++){
if(a[j]>value){
break;
}
}
for(int k=nElems; k>j; k--){
a[k] = a[k-1];
}
a[j] = value;
nElems ++;
}

public void display(){
for(int j=0; j<nElems; j++){
System.out.print(a[j] + " ");
}
System.out.println(" ");
}

public static void main(String[] args) {
int maxSize = 100;
BinarySearch arr = new BinarySearch(maxSize);
arr.insert(72);
arr.insert(90);
arr.insert(45);
arr.insert(126);
arr.insert(54);
arr.display();

int searchKey = 54;
if(arr.find(searchKey) != arr.size())
System.out.println("Found " + searchKey);
else
System.out.println("Can't find " + searchKey);
}

}


#### Word Recursion (Anagram)

##### Idea

Assume a word has n letters:

1. List right-most n-1 letters

2. Rotate all n letters

3. Do two steps above n times

##### Code
/**
If you input 'test', you will get:
1 test
2 tets
3 tste
4 tset
5 ttes
6 ttse
7 estt
8 estt
9 etts
10 etst
11 etst
12 etts
13 stte
14 stet
15 stet
16 stte
17 sett
18 sett
19 ttes
20 ttse
21 test
22 tets
23 tste
24 tset
**/
public class WordRecurtion {

static int size;
static int count;
static char[] arrChar = new char[100];

public static void main(String[] args) throws IOException{
System.out.print("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);
}
public static void doAnagram(int newSize){
if(newSize == 1)
return;
for(int j=0; j<newSize; j++){
doAnagram(newSize-1);
if(newSize==2)
displayWord();
//Starting from every two words, rotate after each recursion
rotate(newSize);
}
}

//Rotate word one position to right
public static void rotate(int newSize){
int j;
int position = size - newSize;
char temp = arrChar[position];
for(j=position+1; j<size; j++){
arrChar[j-1] = arrChar[j];
}
arrChar[j-1] = temp;
}

public static void displayWord(){
if(count<99)
System.out.print(" ");
if(count<9)
System.out.print(" ");
System.out.print(++count + " ");
for(int j=0; j<size; j++)
System.out.print(arrChar[j]);
System.out.println(" ");
}

public static String getString() throws IOException{
return s;
}
}


#### Height of B-Tree

##### Code

This is my code from hankerrank.com:

    /*
class Node
int data;
Node left;
Node right;
*/
int height(Node root)
{
Node current = root;
if(current == null){
return 0;
}
if(height(current.left)>height(current.right))
return 1 + height(current.left);
else
return 1 + height(current.right);
}


#### Decide if B-Tree is Balanced

Following method is taken from this post:

/*
class Node
int data;
Node left;
Node right;
*/
//Return depth of tree if tree is balanced. Otherwise return -1
int isBalenced(Node root)
{
Node current = root;
if(current == null){
return 0; //return 0 for null node
}

int left = isBalenced(current.left);
int right = isBalenced(current.right);

if(left>=0 && right>=0 && left-right<=1 || left-right >= -1){
if(left<right)
return right + 1;
else
return left + 1;
}else{
return -1;
}
}