Recursion

My AP Computer Science Class : Read the story of the Tower Hanoi and then solve the Tower in the game below.

The Towers of Hanoi

The Story The puzzle was invented by the French mathematician Edouard Lucas in 1883. There is a legend about an Indian temple which contains a large room with three time-worn posts in it surrounded by 64 golden discs. The priests of Brahma, acting out the command of an ancient prophecy, have been moving these discs, in accordance with the rules of the puzzle. According to the legend, when the last move of the puzzle is completed, the world will end. The puzzle is therefore also known as the Tower of Brahma puzzle. It is not clear whether Lucas invented this legend or was inspired by it.

Definition and example of Recursion

Recursion is when a method calls itself until a particular condition, called the base case, is satisfied. In the first example, the base case is when the counter equals zero.

public class Recursion {

void countDown( int counter)
	{
	if(counter == 0)
	     return;
	else
       {
       System.out.println(""+counter);
       countDown(--counter); //call self again
       return;
       }
	}
	
	
public static void main(String[] args){
		Recursion myRecursor = new Recursion();
		myRecursor.countDown(3); 		
	}
}
	

public int factorialize(int n) {
  // Base case: if n is 1, we can return the answer directly
  if (n==1) return 1;
  
  // Recursion: otherwise make a recursive call with n-1
  // (towards the base case), i.e. call factorialize(n-1).
 return n * factorialize(n-1); //call self again
}

Infinite Recursion and Stack Overflow

If you write a recursive method that does not ever reach the base case you will have infinite recursion which can be considered analogous to the flawed logic of an infinite loop. However, there is a difference. Infinite recursion will not run forever like an infinite loop, instead, you will eventually run out of stack space (memory) and get a run-time error or exception called a stack overflow. This is bad so try to avoid infinite recursion!

Pros and cons of recursion

Pro: Recursion often removes the need for temporary variables.
Con: Recursion requires more calls to the stack and therefore is a more expensive operation.

So the question inevitably arises? When should one employ recursion? Usually, you want to use recursion when you must work backwards from a problem.

The Towers of Hanoi Code and Examples in Java

 

An excellent applet illustrating The Recursive Nature of the Towers of Hanoi (The following solution to the Towers of Hanoi comes from http://www.kernelthread.com/hanoi/html/java.html)

/* The Towers Of Hanoi * Java 
/* Copyright (C) 1999 Amit Singh. All Rights Reserved. 
/* http://hanoi.kernelthread.com * 
/* Tested under Linux jdk-1.1.? */ 


class hanoi { 


public static void main (String args[]) { 
if (args.length != 1) { 
	System.err.println("error: a single integer argument needed");
	 System.exit(1); 
	} 

Integer N = new Integer(args[0]); 
H_dohanoi(N.intValue(), 3, 1, 2); 

System.exit(0); 
} 

static void H_dohanoi(int n, int t, int f, int u) { 
if (n > 0) { 
	H_dohanoi(n-1, u, f, t); //call self again
	H_moveit(f, t); 
	H_dohanoi(n-1, t, u, f); //call self again
	}
 } 

static void H_moveit(int from, int to) { 
System.out.print("move "); 
System.out.print(from); System.out.print(" --> ");
System.out.println(to); 
} 

}