Mathematical induction and recursion
CHAPTER 6
Mathematical Induction and Recursion
References - (Nothing in Brooks)
Mark Allen Weiss, Data Structures and Algorithm Analysis, The Benjamin/Cummings Publishing Company, Redwood City, CA
Alan Tucker, Applied Combinatorics, John Wiley & Sons, New York
Mathematical Induction -- Two steps
1. Prove theorem is true for some small value (degenerate case), say a.
2. Assume theorem is true for some . (or even all values between a and k). Prove theorem is true for k+1.
· If we can do that, then we know theorem is true for all values .
· That is, we can "get" to any value n by starting at a, and then stepping up 1 until we reach n.
A simple induction proof
A bad induction proof
Another bad induction proof
Proving a property about Fibonacci numbers
Proof that any integer n>1 can be written as a product of primes
A prime number is an integer p>1 that is divisible by no other integer besides 1 and p
Theorem
Any integer n>1 can be written as a product of prime numbers.
Proof (by induction)
The initial step is to prove that 2 can be written as a product of primes. But 2 is itself prime. Thus 2 is trivially the product of primes, i.e. it is itself a prime.
Now assume that the numbers 2, 3,...,n-1 can be written as a product of primes. We will use this assumption to prove that n can also be written as a product of primes.
If n is prime, then it can trivially be written as a product of primes. Suppose n is not prime. Then, there exists an integer m which divides n.
If k=n/m, then n=k m. Since k and m must be less than n and greater than 1, they too can each be written as a product of primes. By multiplying these two prime products for k and m, one obtains the desired representation of n as a product of primes.
Recursion -- introduction
Reference: Brooks, Chapter 5 (5.4)
· Consider the definition of n! (i.e. n factorial)
· One way to look at it:
· Another way to look at it:
· To compute 4! using the second definition, we would proceed as follows:
· We employ the procedure of computing n! recursively until we reach the base case of its definition
Recursion -- introduction (2)
· Our description of n! is an example of a recurrence relation
· A recurrence relation is simply a function which is defined recursively
· For example, the following gives a recurrence relation for n!
· To prove that f(n) = n!, we can use mathematical induction
example Prove that f(n) = n!
Recursion -- introduction (3)
· We can implement a function in C to compute n! using either iteration or recursion
Iterative C implementation
12
3
4
5
6
7
8
9
10
11
12
13
14
15 / long factorial (long n)
{
long i, result = 1;
if (n < 0)
return 0;
if (n == 0)
return 1;
for (i = 1; I <= n; i++)
result *= i;
return result;
}
Recursive C implementation
12
3
4
5
6
7
8
9 / long factorial (long n)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
Recursion -- introduction (4)
· Each block is given its own activation record containing all automatic variables
· Consider calling the recursive factorial(4)
· Let us see what the activation frame looks like at each level
12
3
4
5
6
7
8
9 / long factorial (long n)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
Initial call to factorial(4)
Recursive call to factorial(3)
2
3
4
5
6
7
8
9 / long factorial (long n)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
Recursive call to factorial(2)
2
3
4
5
6
7
8
9 / long factorial (long n)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
Recursive call to factorial(1)
2
3
4
5
6
7
8
9 / long factorial (long n)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
Recursive call to factorial(0)
2
3
4
5
6
7
8
9 / long factorial (long n)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
Returning from the recursive call to factorial(0)
2
3
4
5
6
7
8
9 / long factorial (long n)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
Returning from the recursive call to factorial(1)
2
3
4
5
6
7
8
9 / long factorial (long n)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
Returning from the recursive call to factorial(2)
2
3
4
5
6
7
8
9 / long factorial (long n)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
Returning from the recursive call to factorial(3)
2
3
4
5
6
7
8
9 / long factorial (long n)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
Recursion -- how it works
· Recall that each block is given its own activation record containing all automatic variables
· The recursive implementation of factorial uses the system stack to store intermediate values
· On the other hand, the iterative implementation of factorial uses only one variable to store the intermediate results
· Thus, we observe that the amount of space required by the iterative version is constant
· The recursive version, though, requires a unique activation frame for each function call
· The number of activation frames (at the worst case) is n+1
· Thus, the space requirement of the recursive version is linear in the number of recursive calls!
· To wit: the iterative version (in this case) uses a lot less system resources than the recursive version
· This is because the best algorithm for computing n! requires constant space because we only need to know the previous value
· Recursive implementations are appropriate where the amount of space consumed would have been consumed anyway
· i.e., we would have had to stack the input anyway
Recursion -- concepts and program design
Simple mathematical formulas
Recursive formulas
C implementation
12
3
4
5
6
7 / long f (long x)
{
if (x == 0) /* base case */
return 0;
else
return 2 * f (x - 1) + x * x;
}
· Lines 3 and 4 handle the base case, i.e. the value which is known without resorting to recursion
· Line 6 makes the recursive call
· Without lines 3 and 4, f would go into an infinite loop
· Note that an attempt to evaluate f(-1) will result in calls to f(-2), f(-3), and so on
· Because this never gets to a base case, the program will never terminate with any of those values
Recursion (2)
· The following routine is a bad use of recursion because it never terminates
12
3
4
5
6
7 / long bad (long n)
{
if (n == 0)
return 0;
else
return bad (n / 3 + 1) + n - 1;
}
· Calling bad(1) will call bad(1) at line 6 and go into an infinite loop
· Calling bad(2) will call bad(1) which will once again go into an infinite loop
· In addition, bad(3), bad(4), and bad(5) all call bad(2) which goes into an infinite loop
· The only value of n for which this program works is its special case, i.e. n=0
· These examples illustrate the necessity for the first two fundamental rules of recursion
1. Base cases
· You must always have some base case which can be solved without recursion
2. Making progress
· For the cases that are to be solved recursively, the recursive call must always be to a case that makes progress toward a base case
Recursion (3) -- printing out numbers
· Suppose we wish to write a program in a language to print out a positive integer n but where the only I/O routines available will take a single digit number and print it to the terminal
Given: void print_digit (int digit);
Implement: void print_number (int n);
Solution (recursive)
· To print out the number 67234, we need to first print out 6723 followed by a 4
· We accomplish the second step by calling
print_digit (n % 10);
· We can achieve the first part by calling
print_number (n/10); /* integer division */
12
3
4
5
6
7
8
9
10
11
12 / int print_number (int n) {
if (n < 0) {
/* error -- n is negative */
return –1;
} else if (n < 10) {
print_digit (n);
} else {
print_number (n / 10); /* recursive call */
print_digit (n % 10);
}
return 0;
}
Recursion (4) -- printing out numbers
2
3
4
5
6
7
8
9
10
11
12 / int print_number (int n) {
if (n < 0) {
/* error -- n is negative */
return -1;
} else if (n < 10) {
print_digit (n);
} else {
print_number (n / 10);
print_digit (n % 10);
}
return 0;
}
Recursion (5)
· Notice that the proof is almost identical to the algorithm description.
· This illustrates that when designing a recursive program, all smaller instances of a problem may be assumed to work correctly.
· The recursive program combines solutions to the smaller problems which had to be solved immediately.
· The mathematical justification is proof by induction.
· This is a very profound concept
· Think about the justification behind mathematical induction
· Think about what a computer does when it encounters a recursive call and when the actual work is done
· A lot of bookkeeping is done on the stack...
Four fundamental rules when writing a recursive program
1. Base cases
· You must always have some base case which can be solved without recursion
2. Making progress
· For the cases that are to be solved recursively, the recursive call must always be to a case that makes progress toward a base case
3. Design rule
· Assume that all recursive calls works (like in mathematical induction)
4. Compound interest rule
· Never duplicate work by solving the same instance of a problem in separate recursive calls
Analyzing recursive procedures
· The total time for a recursive procedure is usually a recurrence relation
· In some cases, the recursion is a thinly veiled for loop; in this case, analyze it as if it were a for loop
example
12
3
4
5
6
7 / int factorial (int n)
{
if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
· By inspection, we can see that factorial is O(n)
· However, to prove it, we would need to derive a recurrence relation and then prove an upper bound on that recurrence
· Due to the bookkeeping costs required by recursion, it also uses O(n) space (on the stack)
· A loop version can be written using constant space
· Recursion is appropriate when you implicitly would want to use a stack to store intermediate results
· We will see that tree traversal is one good example
· Recursive descent parsing is another good example
A formal derivation of the time bound for factorial
2
3
4
5
6
7 / int factorial (int n)
{
if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
An example of how not to use recursion
2
3
4
5
6
7 / int fib (int n)
{
if (n <= 1)
return 1; /* 0 or 1 */
else
return fib (n - 1) + fib (n - 2);
}
· To analyze this program, let T(n) = running time for fib(n)
· If n is either 0 or 1, the running time is that of lines 3 and 4 which is constant, i.e. O(1)
· If n > 2, the time is equal to sum of
· the time it takes to execute line 3
· the time it takes to do line 6
· Line 6 consists of two function calls plus an addition
· Thus, line 6 requires T(n-1) + T(n-2) + 1
· Consequently, for adding lines 3 and 6 yields
T(n) = T(n-1) + T(n-2) + 1 + 1
= T(n-1) + T(n-2) + 2
· We can prove by induction that
· We can also prove by induction that
· In addition, we can prove that
· Thus, , which implies that the running time of function fib grows exponentially
· This is very bad
The reason why function fib is so bad
2
3
4
5
6
7 / int fib (int n)
{
if (n <= 1)
return 1; /* 0 or 1 */
else
return fib (n - 1) + fib (n - 2);
}
· There is a huge amount of redundant work being done
· This violates the fourth major rule of recursion
· the compound interest rule
· The first call on line 6, fib(n-1), computes fib(n-2) at some point and then throws it away
· This value is then recomputed by the second call to fib, i.e. fib(n-2)
Basic maxim
DO NOT COMPUTE ANYTHING MORE THAN ONCE
The much faster iterative version of fib