Tuesday, April 17, 2012

Solve Hannoi problem using recursion or iteration

Problem:
Solve the Tower of Hanoi problem first using recursion and then using iteration.

Analysis:
The Hanoi problem is a favourite example when teaching recursion. The idea is, to move dishes 1..N from source to target, we can first move dishes 1..(N-1) from source to interm, then move the dish N from source to target, and finally we move dishes 1..(N-1) from interm to target. Thus the recursion implementation is very straightforward. To implement using iteration is a little trickier, and can be done using a stack.

Code (recursion):

Code (iteration):

No comments:

Visitors