Recursion is shit.

Unless you want your programs to segfault, then it's okay.

>>10

I don't think you understand what I'm talking about, so here is an example:


MERGE_SORT(array A)
  if (A is empty)
    return the empty array.
  else
    return MERGE(MERGE_SORT(left half of A), MERGE_SORT(right half of A))

Where MERGE(A,B) has been proven to generate a sorted array if A and B are both sorted. With this, you prove that MERGE_SORT is correct, by induction on the length of A.

Base case: Suppose that the length of A is zero.
Then the empty array is returned which is sorted. If the length of A is one, then an array of its only elements is returned, and any array of length one is sorted.

Let n > 1 and suppose that MERGE_SORT returns a sorted array, for all input arrays that have length less than n, and let A be an array of length n. The left and right half of A must both have length strictly less than n. So MERGE_SORT applied to each half will yield two sorted arrays. MERGE is then applied to two sorted arrays, and will yield a sorted array, which is then returned from MERGE_SORT(A). By induction, we are done.

Do you see how this method can be applied in general? You prove the correctness of a function be first proving all of the calls it makes yield correct results, and then you rely on that correctness to establish the correctness of the function itself.