Table of Contents   |   Proof Methods   |   Glossary

Induction and Recursion

Induction and recursion are very closely related and understanding one can help with understanding the other.  This most often arises in proofs of correctness for recursive algorithms.  (e.g. Quicksort)  We start by illustrating this with a simpler recursive algorithm: Factorial.

The Factorial Function: (n!)

As you probably remember from a long ago math class, n! of some integer n can be characterized as:

    n! = 1  for  n = 0;  otherwise

    n! = n (n - 1) (n - 2) ... (1)    

      or in other words

     n! = n (n - 1)!    (since n (n - 1)! = (n [(n - 1) (n - 2)...(1)] )

Now you can devise a recursive algorithm to compute this recurrence.

An Algorithm for n!

Fact (N)

  1. if (N == 0) then

  2.    return 1

  3. else

  4.    return (Fact <= N * Fact (N-1)) 

But what if you had to prove that your recursive algorithm worked?  One way of checking this is to do an example and plug in some numbers.

Here's an example of how Fact(n) works when N = 10 

Algorithm

Fact(10)
    10 * Fact(9)
      |  9 * Fact (8)
      |    |  8 * Fact (7)
      |    |    |    |    ..............
      |    |    |    |    |    |     |    2 * Fact(1) 
      |    |    |    |    |    |     |    |    1 * Fact(0)
      |    |    |    |    |    |    |    |    |    |      1 *  1
      |    |    |    |     |    |    |    |    |    2 * 1 *  1
      |    |    |    |     |    |    |    |      ...............
      |    |    8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1
      |   9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1
  10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1

Why is the recurrence returning the correct answer?  Well we know that the following is true by definition.

     0! = 1

We also know that:

     Fact(1) = 1 * Fact(0) = 1 * (1) = 1!

Then:

     Fact(2) = 2* Fact(1) = 2* (1) = 2= 2! 

and

     Fact(3) = 3 * Fact(2) = 3* (2) = 6 = 3!                    

Because the level preceding 3! was correct, we don't need to check the full multiplication again when we calculate the 4th level, since 4 * Fact(3) = 4 * 3! = 4! and we know the 3rd level correctly calculates 3!.  

 In fact, we know that this repetition will be true all the way up to the 10th level.

Proving Factorial for all inputs

But now you want to establish that this recursion works, not only for numbers 1..10 but for any positive integer n.  This is important because it would be annoying to find out that your algorithm actually breaks at the number 5,730,526.  By showing it true for all n, you can gurantee this won't happen.

A Formal Proof

  1. Prove that Fact(n) returns n!.

  2. Fact(1) works correctly since it will return 1.

  3. Assume the Inductive Hypothesis: Given any input m, if Fact(m ) is true, Fact (m+1) must be true.

  4. Prove Fact(m+1) returns (m+1)!      
This is where our intuition about how a recursive function like Factorial works, comes in handy.  By tracing the function, we have learned how it builds an answer up.  This is very similar to building the row of dominoes needed for the inductive proof.  What the trace allows us to see is that the m + 1th case is just a simple function of the mth case:  

Fact(m+1) = (m+1) Fact(m) (Look at the trace if this isn't clear.)

Substituting the inductive hypothesis gives us

Fact(m+1) = (m+1) m! = (m+1)!

5.  Therefore Fact(n) returns n!.

Top of Page   |   Table of Contents   |   Proof Methods   |   Glossary1