PHP Program for Tower of Hanoi with Output and Explanation

A PHP program for Tower of Hanoi uses a recursive function like function towerOfHanoi($n, $from, $to, $aux) that moves disks between rods and prints each move with echo.

Examples

Input3 disks

OutputMove disk 1 from rod A to rod C Move disk 2 from rod A to rod B Move disk 1 from rod C to rod B Move disk 3 from rod A to rod C Move disk 1 from rod B to rod A Move disk 2 from rod B to rod C Move disk 1 from rod A to rod C

Input1 disk

OutputMove disk 1 from rod A to rod C

Input0 disks

Output

How to Think About It

To solve Tower of Hanoi, think about moving the top n-1 disks to the auxiliary rod first, then move the largest disk to the target rod, and finally move the n-1 disks from auxiliary to target. Use recursion to repeat this process until no disks remain.

Algorithm

1

If number of disks is 1, move it directly from source to target and return.

2

Recursively move n-1 disks from source to auxiliary rod.

3

Move the nth disk from source to target rod.

4

Recursively move n-1 disks from auxiliary to target rod.

Code

php

<?php
function towerOfHanoi($n, $from, $to, $aux) {
    if ($n == 1) {
        echo "Move disk 1 from rod $from to rod $to\n";
        return;
    }
    towerOfHanoi($n - 1, $from, $aux, $to);
    echo "Move disk $n from rod $from to rod $to\n";
    towerOfHanoi($n - 1, $aux, $to, $from);
}

// Example: Move 3 disks from rod A to rod C using rod B
towerOfHanoi(3, 'A', 'C', 'B');

Output

Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C

Dry Run

Let's trace moving 2 disks from rod A to rod C using rod B.

1

Move top disk from A to B

Call towerOfHanoi(1, 'A', 'B', 'C') prints: Move disk 1 from rod A to rod B

2

Move bottom disk from A to C

Prints: Move disk 2 from rod A to rod C

3

Move disk from B to C

Call towerOfHanoi(1, 'B', 'C', 'A') prints: Move disk 1 from rod B to rod C

Call	Action
towerOfHanoi(1, A, B, C)	Move disk 1 from rod A to rod B
Print move disk 2 from rod A to rod C	Move disk 2 from rod A to rod C
towerOfHanoi(1, B, C, A)	Move disk 1 from rod B to rod C

Why This Works

Step 1: Base Case

When there is only one disk, the function moves it directly from the source rod to the target rod using echo.

Step 2: Recursive Calls

The function calls itself to move n-1 disks to the auxiliary rod, then moves the largest disk, and finally moves the n-1 disks from auxiliary to target.

Step 3: Print Moves

Each move is printed immediately, showing the step-by-step solution to the Tower of Hanoi problem.

Alternative Approaches

Iterative approach using stack

php

<?php
// Iterative Tower of Hanoi is complex and uses stacks to simulate recursion
// This example is simplified and not shown here due to complexity

Iterative solutions avoid recursion but are harder to implement and understand.

Using global array to store moves

php

<?php
$moves = [];
function towerOfHanoiStore($n, $from, $to, $aux) {
    global $moves;
    if ($n == 1) {
        $moves[] = "Move disk 1 from rod $from to rod $to";
        return;
    }
    towerOfHanoiStore($n - 1, $from, $aux, $to);
    $moves[] = "Move disk $n from rod $from to rod $to";
    towerOfHanoiStore($n - 1, $aux, $to, $from);
}

// Call and print all moves
towerOfHanoiStore(3, 'A', 'C', 'B');
foreach ($moves as $move) {
    echo $move . "\n";
}

Stores moves in an array first, useful if you want to process moves later instead of printing immediately.

Complexity: O(2^n) time, O(n) space

Time Complexity

The function makes two recursive calls for n-1 disks plus one move, resulting in 2^n - 1 moves, so time complexity is exponential O(2^n).

Space Complexity

The recursion depth is n, so the space used on the call stack is O(n).

Which Approach is Fastest?

Recursive approach is simplest and clear; iterative methods can be faster but are more complex to implement.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Simplicity and clarity
Iterative	O(2^n)	O(n)	Avoiding recursion but complex code
Storing moves in array	O(2^n)	O(2^n)	Processing moves later instead of immediate output