.. title: Algorithm and Data Structure Basics - Recursion
.. date: 2015-09-02
.. category: Algorithm & Data Structure
.. tags: Java, Algorithm, Data Structure, Recursion
.. slug: algorithm-and-data-structure-basics-recursion
.. authors: Pengyin Shan
.. description: I wrote this post to record some basic knowledge about using recursion for future reference. Code is written mainly in Java.
###Reference List
- Understand Recursion (Chinese)
- Recursion (Chinese)
###Common Model of Recursion
:::java
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
:::java
/**
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
:::java
/*
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 upperBound){
return nElems; //cannot find
}
else{
if(a[curIn]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; jheight(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:
:::java
/*
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