I have some comments on how (not) to teach it. First of all, do not tell students to "start with the base case". The base case will be trivial and gives very l

I have some comments on how (not) to teach it. First of all, do not tell students to "start with the base case". The base case will be trivial and gives very little insight into how to solve the recursion problem. All the time they spend thinking about that is time spent not confronting the actual problem. Beyond that, I think the way to teach recursion is to say "You cannot write the code until you can write a sentence in words describing the recursive solution. Your sentence must make reference to calling the procedure on a smaller sub-problem. Don't bother describing the base case in the sentence; it's boring - just fill it out when you write the code.". So something like "The number of ways the robot can get to the last square is equal to the number of ways it can do it assuming it starts by going right plus the number of ways it can do it assuming it starts by going down".