Correctness

We started proving the correctness of recursive algorithms this week. I'm starting to realize how powerful induction is. Almost anything can be expressed in an "inductive" way.

Sometimes though it can be a bit tricky to find out how to break it down to that form. Danny showed us this in class when proving the greatest common factor algorithm. Simplifying the two numbers into one by specially relating the two (for all m, for all n > m) helped turn it into a simple one variable induction process. This was a new way of seeing it for me.

Danny mentioned that recursive programs are easier to prove correct than iterative programs. This was at first kind of against my intuition since I have a better picture of what going on in an iterative program (recursive programs that branch off into stacks of trees and whatnot are especially confusing to follow along). However, now it seems this is actually true. For correctness we don't need to follow through with the whole recursion. Instead we just need to worry about the top most layer, which is really simple. For iterative programs, however, I'm guessing the complexity comes from the fact that we actually need to worry about ALL the iterations not just one of them.
Things will get clearer next week.