The algorithm of solving Hanoi problem is often used to demonstrate the recursive idea in programming. Frankly speaking, recursion often manifests itself as a function calls itself. With that structure, recursive functions should always encompass the termination logic with respect to the base case. Otherwise, they can't stop and will end up throwing out "OOM" (Out Of Memory). The reason why we can make Hanoi problem a recursion is that every step of Hanoi is related to the previous step except for the first step. For example, the problem of size four can be seen as one process moving the top three disks to the auxiliary pillar. Then we execute the process moving the biggest disk to the target pillar. At last, we move the three to the target pillar. The last step is symmetrical to the first because moving the top three to an empty pillar is logically the same as moving to the pillar having the biggest disk. This characteristic determines that Hanoi can be represented by recursion.
Insight: Recursion is a classic programming idea. We use it to solve problems and reduce redundant code. However, when we make mistakes like forgetting the termination or naively force-fitting the idea, it is painful.
Top comments (0)