CS 455 Lecture Notes

Week Twelve, Thursday: Recursive Thinking (continued)

Divide and Conquer: Sorting Example

We can attack the sorting problem by recursively dividing an array into smaller arrays. When each array has only one element, the subproblem is solved (one element arrays are sorted). The sorting problem reduces to a merging problem.

Reasoning About Recursion

We must assure that infinte recursion cannot occur. This can be done by identifying a variant expression that associates a numeric quantity with each recursive call.

To prove there is no infinite recursion we must show that the variant expression decreases by a fixed amount with every recursive call. Example: the pow(double x, int n) function.

To prove the correctness of a recursive function we must first prove that there is no infinite recursion. Then show that the stop condition produces a correct result, and that a recursive call also meets its specification (precondition/postcondition contract).

This page established November 19, 1999; last updated November 19, 1999.