Transcript Document

Induction and Recursion
Lecture 12-13
Ref. Handout p 40 - 46
1
A Question
 Eve was human
 Human mothers produce human children
 Noah was Eve’s great ∗ 8 grandson
 Can you prove the Noah was human?
2
Induction
... and you can get
from any step to
the next step
If you can
reach the
first rung
of the
ladder
You can go
anywhere!
3
Induction
(the picture is from wikipedia.org)
A formal description of mathematical induction can be illustrated by
reference to the sequential effect of falling dominoes
4
Induction has three parts
 Base Case(s)
o Simplest examples
 Inductive Step
o From simpler to more complex
 ‘Exclusivity’
o Only things defined from the base case and
inductive steps are legal
o This part can be omitted in definition as we
assume it must be true
5
Induction – an example
 What is a natural number?
{0,1,2,3,4,...... }
 Use induction to define natural numbers:
1. Base: 0 is a natural number
2. Induction: if x is a natural number so is x+1
3. Exclusivity: only numbers generated using
the above rules are natural numbers
6
Regular Languages defined by
Induction
Base:
 { a } is a regular language for any ‘a’
Inductive steps:
1. If A is a regular language so is A*
2. If A and B are regular languages so is A U B
3. If A and B are regular languages so is A.B
4. ... etc
7
Checking Membership
Is this a regular language?
{ a, b, ab, ba, aab, bba, aaab, bbba, aaaab,... }
top down
A = { a } and B = { b } are regular
so: A* and B* are regular
so: A*.B and B*.A are regular
so: (A*.B U B*.A) is regular
bottom up
8
Induction – more examples
palindromes
 Palindrome = a string which read the same
left to right as right to left.
E.g. Λ, x, aaa, hannah, did, radar,
 Use induction to define palindromes:
1. Base: an empty string, Λ, is a palindrome
2. Base: a single character is a palindrome
3. Induction: if P is a palindrome, then so is
xPx where x is any character
9
Induction – more examples
how to define a path on a graph
b
a
f
e
c
d
g
h
A path is a sequence of connected arcs joining two
node. (this is not an inductive definition)
Use induction to define the path:
There is a path from node A to node B if either
1. there is an arc from A to B, (base) or
2. There is an arc from A to some node C and there is
a path from C to B (induction).
10
Why is Induction Important? - 1
How can we prove
whether this program
stops?
It stops if v is 0 on
the call of
getPosInteger()
If it stops for v = n
it stops for v = n+1
s=0;
v = getPosInteger();
while(v != 0) {
s = s+v;
v = v-1;
}
Assume that getPosInteger() returns a random non-negative integer
11
Why is Induction Important? - 2
n! = n ∗(n-1) ∗(n-2) ∗ ... ∗1
for n >= 1
static int factorial (int n) {
if(n <= 1) // base 1!=1
return 1;
else
// induction: n!=n∗(n-1)!
return n ∗ factotial(n-1);
}
Induction in programming is called recursion
12
Why is Induction Important? - 3
Define an ordered list (i.e. go through the
list from left to right the numbers get bigger)
Base: if the list only has one number,
it is ordered
Induction: let head(L)=the 1st number in L,
tail(L)=rest of L after removing the 1st number.
If tail(L) is ordered and head(L) >=head(tail(L))
then we say L is ordered
13
Why is Induction Important? - 3
‘translate’ the definition to a program:
ordered_list (L) {
if(tail(L)==‘empty’) // base
return true;
else
// induction
return ( head(L)>=head(tail(L))
&& ordered_list(tail(L) );
}
14
Bad Induction
 X gets the same exam mark as herself ( or
himself)
 If n people always all get the same mark then
so do (n+1) people
 But for n=1 this is true so it’s ture for n=2
 But if it’s true for n=2 it is true for n=3
 So everyone gets the same mark
15
Memo for In-class test 12 [
questions
my
answers
correct
answers
/5]
comments
1
2
3
4
5
16
Making a Long String
(by duplicating a given string)
We want to have a program:
public string duplicate (String s, int n)
which returns a string consisting of ‘s’ repeated
‘n’ times.
e.g. duplicate(“abc”, 4)
returns
“abcabcabcabc”
17
Making a Long String - cont
Easy Case 1 – when n=0 or n=1
public string duplicate(String s, int n){
if(n <= 0) return “”;
// “”= Λ
if(n == 1) return s;
18
Making a Long String - cont
Easy Case 2 – when n is even
remainder on
dividing by 2
if(n%2 == 0)
return duplicate(s+s, n/2)
‘+’ here means
appending two
strings into one
19
Making a Long String - cont
Easy Case 3 – when n is odd
if(n%2 == 0) // even
return duplicate(s+s, n/2);
else
// odd
return s + duplicate(s+s, (n-1)/2);
20
Making a Long String - cont
Put them all together
public string duplicate(String s, int n){
if(n <= 0) return “”;
if(n%2 == 0) // even
return duplicate(s+s, n/2);
else
// odd
return s + duplicate(s+s, (n-1)/2);
}
21
Making a Long String - cont
The Short Version
public string duplicate(String s, int n){
if(n <= 0) return “”;
String s2 = duplicate(s+s, n/2);
if(n%2 != 0)// odd, != means not equal
s2 = s2+s;
return s2;
}
22
It Works!
a) It works for n=0
b) If it works for all n up to N say
a) and so it works for all n up to N+1
23
General Recursion
If the problem is very easy – solve it
solve small problems
else break into small problems
24
Recursion and Stacks
Recursion
= using stacks
(but prettier)
fac(5)
fac(int n) {
if(n <= 1) return 1;
else
return (n ∗ fac(n-1));
}
5 ∗ fac(4)
4∗ fac(3)
3 ∗ fac(2)
2∗ fac(1)
fac(1)=1
25
Recursion and Iteration
 A basic component of an algorithm is loop
mechanism
 The loops perform a repeated action of a set
of instances
 The loops can be classified as either iterative
or recursive
 An iterative loop – using explicit loop control
provided by computer languages.
e.g ‘while-loop’, ‘for-loop’
 A recursive loops – a program calls itself
26
Recursion and Iteration – an example
membership checking (x is in the list?)
// using iteration
// using recursion
is_in_list(x, list) {
if(list==[]) return false;
h = Head(list);
t = Tail(list);
while(t != []) {
if(h==x) return true;
else {
t = Tail(list);
h = Head(t);
}
}
return false;
}
is_in_list(x, list) {
if(list==[]) return false
h = Head(list);
t = Tail(list);
if(h==x) return true;
else
return is_in_list(x,t);
}
// note that [] means an
// empty list
27
Memo for In-class test 13 [
questions
my
answers
correct
answers
/5]
comments
1
2
3
4
5
28