Programs & Examples
Methods and Recursion · Study material
Tower of Hanoi with recursion
Moving n discs = move n − 1 out of the way, move the largest, move n − 1 back on top. The program prints every move for 3 discs and only the count for 10, 2ⁿ − 1.
public class Main {
static int moves = 0;
static boolean verbose = true;
static void hanoi(int n, char from, char to, char via) {
if (n == 0) return;
hanoi(n - 1, from, via, to); // move n-1 discs out of the way
moves++;
if (verbose) System.out.println("move disc " + n + " from " + from + " to " + to);
hanoi(n - 1, via, to, from); // put them back on top
}
public static void main(String[] args) {
hanoi(3, 'A', 'C', 'B');
System.out.println(moves + " moves for 3 discs");
moves = 0;
verbose = false; // 1023 moves: just count them
hanoi(10, 'A', 'C', 'B');
System.out.println(moves + " moves for 10 discs (2^n - 1)");
}
}
move disc 1 from A to C move disc 2 from A to B move disc 1 from C to B move disc 3 from A to C move disc 1 from B to A move disc 2 from B to C move disc 1 from A to C 7 moves for 3 discs 1023 moves for 10 discs (2^n - 1)
Factorial, digit sum, fast power and GCD
The recursion example implements four classic recursive functions, each with a clear base case.
Visualising the call stack
The call-stack example prints "enter" and "leave" with indentation, showing frames being pushed and popped.