Recursion -- move cheeses using four (4) stools

The first assignment enhances our understanding of recursion and we start to realize its strong power.

The first assignment (A1) of this course is related to "The tour of Anne Hoy" -- move cheeses from one stool to another. In lecture, the instructor teaches us how to move n cheeses using three(3) stools, and the strategy is : (1) move n-1 cheeses from source stool to intermediate stool; (2) move 1 (the biggest one) cheese from source to destination stool; (3) move n-1 cheeses from intermediate to destination. The total moves is 2^n-1. To reduce moves, Anne decides to invest one more stool. Our task is to find the strategy to using four(4) stools to move cheeses from one stool to another and significantly reduce the moves used by 3 stools.

Because we have 4 stools now, so we do not have to move n-1 cheeses to intermediate stool and move 1 to destination stool. Instead we can (1) move n-i cheeses from source stool to one intermediate stool; (2) move i cheeses from source stool to destination stool; (3) move n-i cheeses from intermediate stool to destination stool. In step (2), Anne can use her old strategy to move the i cheeses using three(3) stools because the n-i smallest cheeses occupies one intermediate stool and she can not use it. But in step (1) and (3), Anne needs a better strategy to move the n-i cheeses because she can uses 4 stools and she can divides the n-i cheeses into two(2) parts (just like we divided the n cheeses into n-i and i two(2) parts), using the same strategy to move the n-i cheeses from source to one intermediate stool -- she will (1) move (n-i)-k cheeses from source to intermediate-1; (2) move k cheeses from source to intermediate-2; (3) move (n-i)-k cheeses from intermediate-1 to intermediate-2. Now you can easily find here is a repeat process -- recursion appear. After getting the idea, then code. At each step of the recursion, we code another function for choosing i value.

I used the console to trace each move and found all the moves were legal. Once again, I saw the power of recursion and its efficiency.