>> All non-infinite recursive algorithms should have a “base case and a smaller caller”, meaning there needs to be a terminal state and the algorithm should nar

>> All non-infinite recursive algorithms should have a “base case and a smaller caller”, meaning there needs to be a terminal state and the algorithm should narrow its scope on each recursive call. Oh, well, I don't like that, sorry. Recursion is a syntactic property but what you explain here is an algorithmic one. Unbounded recursion, non-terminating recursion and left-recursion are still recursion. My intuition is that you should teach termination and recursion as different concepts and help students understand that they are not the same. So that they learn to avoid non-terminating recursion that is. Btw I think what you describe is called a Knuth-Bendix ordering.