Transcript
CHAPTER 6 Mathematical Induction and Recursion
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.
\* mergeformat
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
1
2
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
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);
}
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
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);
}
Initial call to factorial(4)
\* mergeformat
Recursive call to factorial(3)
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);
}
\* mergeformat
Recursive call to factorial(2)
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);
}
\* mergeformat
Recursive call to factorial(1)
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);
}
\* mergeformat
Recursive call to factorial(0)
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);
}
\* mergeformat
Returning from the recursive call to factorial(0)
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);
}
\* mergeformat
Returning from the recursive call to factorial(1)
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);
}
\* mergeformat
Returning from the recursive call to factorial(2)
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);
}
\* mergeformat
Returning from the recursive call to factorial(3)
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);
}
\* mergeformat
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
1
2
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
1
2
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 */
1
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); /* recursive call */
print_digit (n % 10);
}
return 0;
}
Recursion (4) -- printing out numbers
1
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
1
2
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
1
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
1
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
1
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long fib (long n)
{
long i, back_1, back_2, result;
back_2 = 1;
back_1 = 1;
if (n <= 1)
return 1; /* 0 or 1 */
for (i = 2; i <= n; i++) {
result = back_1 + back_2;
back_2 = back_1;
back_1 = result;
}
return result;
}
In this example, we observe that we only need to know the last two computed values in order to compute the next value
This follows directly from the recurrence relation
The loop computes each Fibonacci number by starting at 2 and working its way upward
Clearly, the number of iterations is bounded above by n
The amount of space required is constant
A good example of how to use recursion -- binary search
The binary search problem is given as follows.
One solution would be to scan through the input from left to right
This algorithm, though, obviously runs in linear time
It is far better to derive an algorithm which takes advantage of the property that the input is sorted and already in memory
We want our program to search for the object the same way we search for a word in a dictionary
The program will look in the middle of the input
If it finds the element, it will return the index
Otherwise, it will narrow its search to either the lower or upper half of the input
In this sense, it is able to cut its search in half, thus its name binary search
\* mergeformat
The binary search function
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
** To call this function, pass in the array
** a[], the lower bound (0) and the upper
** bound (n-1). This function returns the
** index of the key within a[].
**/
int binsearch (int a[], int low, int high, int key)
{
int mid = (low + high) / 2;
if (low > high) {
/* not in array */
return -1;
}
if (key < a[mid]) /* recursive call */
return binsearch (a, low, mid - 1, key);
else if (key > a[mid]) /* recursive call */
return binsearch (a, mid + 1, high, key);
else /* if (key == a[mid]) */
return mid; /* found it */
}
\* mergeformat
The complexity of this function equals the number of calls to this function
Because this function always divides its input in half before proceeding, the number of calls to this procedure is bounded above by log(n)
Also, the amount of space used on the stack is also bounded by log(n)
It is clearly possible to write an equivalent iterative version which uses O(1) space
the iterative version is marginally better than the recursive version
because log(n) tends to be very small even for large input, the difference in efficiency is marginal indeed
Input string reversal -- an even better example of recursion
Consider the following two routines to reverse a line of input from the terminal
One works and the other doesn't
The one that works uses O(n) space (as it should)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include
void reverse (void)
{
int ch = getchar ();
switch (ch) {
case '\n':
putchar (ch);
case EOF:
break;
default:
reverse ();
putchar (ch);
}
}
void reverse2 (void)
{
static int ch = getchar ();
switch (ch) {
case '\n':
putchar (ch);
case EOF:
break;
default:
reverse2 ();
putchar (ch);
}
}
Beware of “non-reentrant” functions…
Precedence and order of evaluation
Operator
Associativity
Order of Evaluation
() [] -> .
left to right
-
! ~ ++ --
(unary) + -
(indirection) *
& ( type ) sizeof
right to left
-
* / %
left to right
-
+ -
left to right
-
<< >>
left to right
-
<= < > >=
left to right
-
== !=
left to right
-
&
left to right
-
^
left to right
-
|
left to right
-
&&
left to right
left to right
sequence point after first argument
short circuit
||
left to right
left to right
sequence point after first argument
short circuit
?:
right to left
first operand eval
sequence point after first argument
=
+= -=
*= /= %=
&= |=
<<= >>=
right to left
-
,
left to right
left to right
sequence point after first argument
Parse trees
example: x = a + b * c
We wish to draw the parse tree for this string
First, we must fully parenthesize it:
x = (a + (b * c))
Now we can draw the parse tree
\* mergeformat
The higher precedence operand is lower in the tree.
To evaluate the expression, do a preorder (or postorder) traversal of the tree.
preorder: visit root, traverse left subtree, traverse right subtree
inorder: traverse left subtree, visit root, traverse right subtree
postorder: traverse left subtree, traverse right subtree, visit root
example -- continued
\* mergeformat
preorder: visit root, traverse left subtree, traverse right subtree
inorder: traverse left subtree, visit root, traverse right subtree
postorder: traverse left subtree, traverse right subtree, visit root
prefix string: = x + a * b c
infix string: x = a + b * c
postfix string: x a b c * + = (like HP calculator)
Standard exercises
1. Given expression, draw parse tree
2. Given parse tree, derive infix expression with minimal parentheses
3. Given either prefix or postfix expressions, derive infix expression (Hint: draw the parse tree)
example
\* mergeformat
infix string (without parentheses)
a * b - c - d + e * f - g - h - i
C expression with required parentheses
(a * b - (c - d) + e) * (f - g - h - i)
example
Give the parse tree for:
a << b + c * d & e | f & g ? h == i : j
answer
1. Fully parenthesize it
(((a << (b + (c * d))) & e) | (f & g)) ? (h == i) : j
2. Draw the parse tree
\* mergeformat
