Discrete Mathematics: Logic
Discrete Mathematics:
Lecture 14. Recursive algorithm
recursive algorithms
an = a·a·a·a·a·a···a = a·an-1
power (a, n) = a ·power (a, n-1)
basis step: if n = 0, power(a, 0) = 1, which is correct since a0 = 1
inductive step:
inductive hypothesis: power(a, k) = ak for all a ≠ 0
power(a, k+1) = a·power(a, k) = a·ak = ak+1
recursive algorithms
power (a, n) = a ·power (a, n-1)
procedure power (a: nonzero real number, n: nonnegative integer)
if n = 0 then return 1
else return a·power(a, n-1)
{output is an}
recursive algorithms
an algorithm is recursive if it solves a problem by reducing it to an
instance of the same problem with smaller input
0! = 1
n! = n·(n-1)! n is positive integer
4! = 4·3! = 4·3·2! = 4·3·2·1! = 4·3·2·1·0! = 4·3·2·1
procedure factorial (n: nonnegtive integer)
if n = 0 then return 1
else return n·factorial(n-1)
{output is n!}
recursive algorithms
procedure factorial (n: nonnegtive integer)
if n = 0 then return 1
else return n·factorial(n-1)
{output is n!}
recursive modular exponentiation
bn mod m, where b, n, and m are integers with m ≥ 2, n ≥ 0, and 1≤ b < m
b0 mod m = 1
bn mod m = ( b·bn-1) mod m = (b·(bn-1 mod m)) mod m, n>0
procedure mpower (b, n, m)
if n = 0 then return 1
else return b·mpower(b, n-1, m)mod m
recursive modular exponentiation
bn mod m, where b, n, and m are integers with m ≥ 2, n ≥ 0, and 1≤ b < m
bn mod m = (bn/2 mod m)2 mod m, n is even
= ((b n/2 mod m)2 mod m)·(b mod m) mod m n is odd
procedure mpower (b, n, m)
if n = 0 then
return 1
else if n is even then
return mpower(b, n/2, m) 2 mod m
else
return ((mpower(b, n/2 , m) 2 mod m)·(b mod m) ) mod m
Fibonacci number
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .
Fibonacci number
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .
procedure iterative fibonacci(n: nonnegative integer)
if n=0 then return 0
else
x := 0
y := 1
for i :=1 to n-1
z := x + y
x := y
y := z
return y
{ output is the nth Fibonacci number}
Fibonacci number
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
procedure fibonacci(n: nonnegative integer)
if n=0 then return 0
else if n=1 then return 1
else return fibonacci(n-1) + fibonacci(n-2)
{output is fibonacci(n)}
Fibonacci number
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
procedure fibonacci(n: nonnegative integer)
if n=0 then return 0
else if n=1 then return 1
else return fibonacci(n-1) + fibonacci(n-2)
{output is fibonacci(n)}
Fibonacci number
procedure fastFibonacci(n: nonnegative integer)
if n=0 return 0
return findFib(0,1,1,n)
procedure findFib(a, b, m, n)
if m=n return b
return findFib(b, a+b, m+1, n)
findFib(0, 1, 1, 4)
return findFib(1,1, 2, 4)
return findFib(1,2, 3, 4)
return findFib(2, 3, 4, 4)
return 3
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .
recursive Euclidean algorithm
a = bq + r, a, b, q, r are integer
gcd (a, b) = gcd (b, r) , a > b
gcd(8, 5) ?
gcd(8, 5)
8 = 5 ·1 + 3
= gcd(5, 3)
5 = 3 ·1 + 2
= gcd(3,2)
3 = 2 ·1 + 1
=1
2 = 1 ·2
procedure gcd (a, b: positive integer, a > b)
if b = 0 then
return a
else
return gcd (b, a mod b)
linear search
procedure linear search(x: integer, a1, a2, . . . , an: integers)
i := 1
while (i≤ n and x ≠ ai)
i := i + 1
if i ≤ n then
location := i
else
location := 0
return location {location is the subscript of the term that equals x, or 0 if x is not found}
recursive linear search
search (i, j, x): searches for the first occurrence of x in the sequence ai, ai+1, . . . aj.
procudure search(i, j, x: integers, 1≤ i ≤ j ≤ n)
if ai = x then
return i
else if i = j then
return 0
else
return search(i+1, j, x)
{output is the location of x in a1, a2, . . . an if it appears; otherwise it is 0}
binary search
procedure binary search(x: integer, a1, a2, . . . , an: integers in increasing order)
i := 1 {i is left endpoint of search interval}
j := n {j is right endpoint of search interval}
while (i < j)
m := (i + j)/2
if x > am then
i := m + 1
else
j := m
if x = ai then
location := i
else
location := 0
return location {location is the subscript i of the term ai equal to x, or 0 if x is not found}
recursive binary search
procedure binary search(i, j, x: integers, 1≤ i ≤ j ≤ n)
m := (i+j)/2
if x = am then
return m
else if (x < am and i < m) then
return binary search(i, m-1, x)
else if (x > am and j > m) then
return binary search(m+1, j, x)
else
return 0
{i is the start
output is the location of x in a1, a2, . . . an if it appears; otherwise it is 0}
merge sort
procedure mergesort(L=a1, . . . an)
if n > 1 then
m := n/2
L1 := a1, a2, . . . , am
L2 := am+1, am+2, . . . ,an
L := merge(mergesort(L1), mergesort(L2))
{L is now sorted into elements in nondecreasing order}
procedure merge(L1, L2)
L := empty list
while L1 and L2 are nonempty
remove smaller of first elements of L1 and L2 from its list
put it at the right end of L
if this removal makes one list empty then
remove all elements from the other list and append them to L
return L
merge sort
27 13 26 1 15 2 24 38
27 13 26 1 15 2 24 38
divide
conquer
1 13 26 27 2 15 24 38
1 2 13 15 24 26 27 38
merge sort
27 13 26 1 15 2 24 38
1 11
27 13 26 1 15 2 24 38
divide
2 6
27 13 26 1 15 2 24 38
3 4 7 8
27 13 26 1 15 2 24 38
5 9
13 27 1 26 2 15 24 38
10 conquer
1 13 26 27 2 15 24 38
21
1 2 13 15 24 26 27 38