Recursion Woes

You know, I'm ok with recursion. It's a rather straightforward concept. The idea that a solution to a big problem is breaking into a number of smaller problems solved in the same way is usually much more elegant that manually smashing your face against the wall.

Consider the formula given for Assignment 1 for calculating the minimum amount of moves required to solve a 4-Stool Tour of Anne Hoy problem. The recursive part of that formula calls itself, reducing the n in the equation each time. When the n reaches 1, the equation stops recurring, and just kicks a 1 out. So, in the end, what's really happening is at the bottom, a 1 is added to a bunch of other numbers, and that number is then added to a bunch of numbers, and so on.

The issue with this solution for the minimum amount of moves is that, in the given formula, some i value between 1 and n-1 is required, but it is not specified which one would ideally work. The solution is to run a loop to recursively test all i values between 1 and n-1. The problem with this is that the runtime on calculating an ideal amount of moves quickly becomes extremely high, n values past 20 can take several seconds. Not the perfect solution, but since according to Danny we don't need to expect values above 20, it gets the job done accurately.

The solution for a 4 stool TOAH model is very similar to that, too. Basically, it recusively calls itself and a method for solving a 3 stool method, until it finds a single cheese to move at a time. Hard to visualize, but it's interesting to see that something I programmed seems to understand how to solve the problem better than I do.

And that understanding is the biggest problem with recursion, it's straightforward as a concept, but specific applications of it take work with the problem to understand. I wasn't able to really get either of the recursive operations in this assignment until after I had implemented both of them. Not for lack of effort, mind you, it is just hard to wrap my head around.