>>4
yeah, nevermind, I should have said by induction on the value of a function applied to the arguments (like the length of a list, or height of a tree or something). Trying to do it by induction on the number of recursive calls isn't going to be very successful if there is infinite recursion, although it wouldn't be correct in that case, so you wouldn't be able to prove correctness. But the idea is that every recursive call brings you closer to the solution. So you first prove that the trivial case is correct, and that then given that the next recursive calls will solve their subproblems, you prove that the calling instance is correct.