We’re reaching the end of the sixth week of the winter quarter, which means that students are taking and/or preparing for midterms. It’s a tough time, and a lot of students are tired. In my lecture on Monday, more than one student literally fell asleep as I talked about merge sort. So today as I was preparing for the continuation of merge sort and the last bits of recursion, I wasn’t expecting anything different. I was very happy to be pleasantly surprised.
One of the last examples of recursion in the course is the Towers of Hanoi problem. It’s a cool problem, especially since there are online tools which allow students to play around and get a good sense of what the problem is about. The recursive solution printing the directions is easy to understand and code. It’s definitely a fun way to finish off a topic that students find abstract and challenging.
But this problem inspired a level of curiosity in my students that I wasn’t expecting. One asked in class if we could count the number of moves, so we changed the program to do that. Unfortunately you have to wait for the instructions to print first, which is time consuming. So another student, on his own and immediately after class, wrote a recursive function that simply counts the number of moves required. He sent it to me, reporting that after 994 disks the function reached the limit of recursion. He seemed a bit embarrassed to be so driven by his curiosity about the problem, but I found it to be an unexpected joy in a difficult week.