Less than vs Greater than

From math, we know that X < Y is the same as Y > X. But in programming, they're not the same.

Oh, I'm not talking about situations where X and Y have side effects that interact badly. Instead, I'm talking about situations where one may be more error prone than the other.

Although the two expressions are mathematically equivalent, they're not linguistically equivalent. One focuses attention on something being smaller, and the other focuses attention on something being bigger. For example, it is a relatively common mistake to go the wrong way when searching a binary search tree. However, almost every time I run into this error, the student has also written the comparisons backward from the direction I think of as “natural”.

Consider the following function for determining whether a given key x appears in a binary search tree t:

  function member(x,t) is
     if t = null then return false
     if t.key = x then return true
     if t.key < x then return member(x,t.left)
     if t.key > x then return member(x,t.right)

The fact that I've written this using recursion instead of iteration is irrelevant. What matters is that the third case goes left when it should go right, and vice versa for the fourth case. But looking more carefully at that third case

     if t.key < x then return member(x,t.left)

I'm not particularly surprised by the error. The comparison t.key < x focuses attention on something being smaller, and the left side of the tree is where the smaller keys go. By asking whether x is smaller than t.key, rather than whether t.key is smaller than x, I think we're much less likely to fall into this trap.

Hey, you got your loop in my recursion!

I've written before about trying to diagnose students' broken or ineffective mental models from the mistakes they make. Here's a mistake that I see frequently from students who are not yet comfortable with recursion.

Say you wanted to write a function to calculate the sum of a list using a loop. Many students could easily write something like

   function sum(list) is
      variable total := 0
      while list /= null do
         total := total + list.item
         list := list.next
      return total

But ask them to write the sum function using recursion, and you might get something like

   function sum(list) is
      variable total := 0
      if list = null then
         return total
      else
         total := total + list.item
         return sum(list.next)

Of course, this code always returns 0. It's pretty clear that the writer had the iterative algorithm in mind, and doesn't understand that each recursive call to sum creates a new instance of the total variable.

When I watch such a student writing code like this, he often declares the variable immediately, before even beginning to think about what the recursive decomposition is going to look like, an almost spinal reflex conditioned by several semesters of writing loops. I can explain recursion until I'm hoarse and draw pictures until my hand cramps up, but I can't compete with the will-o'-the-wisp allure of that variable. Once it's there, it will almost inevitably lead the student to his doom in the bogs of iterative thinking.

One trick to help such a student is to break the cycle where it begins, by getting rid of that variable. Tell him to write the function without using any local or global variables. Or, if he really thinks he needs a variable, to declare it as a constant instead. Of course, there are times when a variable is perfectly appropriate inside a recursive function, but such examples can often be avoided until the student has a better grasp of recursion.