Lecture 20 Sequences and Summations
Lecture 22 Recursive definitions and Algorithms
Goals and Objectives:
• Understand how to use recursive definition to define a sequence
• Understand how to write a recursive algorithm
Read 3.4, 3.5, p. 256 – 261, 274 - 283
A function sometimes is easily to be defined by itself (i.e. recursively defined) instead of explicitly defined.
Recursively Defined Function
Based on mathematical induction, we can define a function using 2 steps:
1. Basis step: specify f(initial value)
2. Inductive step: find a rule to express f(n) in terms of f(smaller value than n)
Techniques in inductive step:
Try to find the relationship between f(n) and f(n-1) by finding either f(n)- f(n-1) or f(n)/f(n-1)if F(n) is either sum of product of certain numbers.
Example. Given a recursively defined function
f(0)=3
f(n+1)=2*f(n)+3, n=0,1,2,...
Find f(3)
Answer:
f(3)=f(2+1)=2*f(2)+3
f(2)=f(1+1)=2*f(1)+3
f(1)=f(0+1)=2*f(0)+3=2*3+3=9
Hence f(2)=2*9+3=21
f(3)=2*21+3=45
Example. Give a recursive definition of the function f(n)=n!,
n=0,1,2,...
Answer:
(1)Basis step: f(0)=0!=1
(2) Inductive step:
try f(n) - f(n-1) = (1*...*n)- (1*...*(n-1)) = cannot simplify. Then
try f(n)/f(n-1)=(1*...*n)/(1*...*(n-1))= n. Hence,
f(n)=n!=n*(n-1)*...*2*1=n*(n-1)!=n*f(n-1),
n=1,2,...
Example. Give a recursive definition of the function f(n)=1+2+...+n
n=1,2,...
Answer:
(1)Basis step: f(1)=1
(2) Inductive step:
try f(n) - f(n-1) = (1+...+n)- (1+...+(n-1)) = n,
Hence f(n)=n+(n-1)+...+2+1=n+f(n-1),
n=2,3,...
Example. A Fibonacci Number is a sequence as below:
1,1,2,3,5,8,13,21,34,...
Write a recursive definition of the function.
Ans:
(1) Basis step: f(0)=1, f(1)=1
(2) Inductive step:
f(n)=f(n-1)+f(n-2), n=2,3,...
Recursively Defined Set
A set of [positive integers S is recursively define if the elements of S are generated by a redursion, i.e., if S={a1, a2,... }, then there is a recursion which computes an in terms of a1 , a2 ,..., an-1 when n is large.
Example.
Let S={3, 6, 9, ...}
We can define S recursively as
Basis step: 3 [pic] S
Inuctive step: if x [pic] S and y [pic] S, then x+y [pic] S
Recursively Enumerable Set
If there is an algorithm which will determine whether any positive integer a is a member of a set S in finitely many step.
Example.
The set S in the example above is a recursively enumerable set since we can use
a mod 3 == 0 to decide the element I S.
Recursive Algorithm: An algorithm that calls itself to solve the problem by reducing the problem to smaller input problem in inductive step. Eventually the problem will be solved in Basis step.
Ex. Write recursive algorithms for the above problems.
1. f(n)=n!, n=0,1,2,...
Express the function by recursive definition as above
function f(n:nonnegative integer)
begin
if n=0 then f:= 1
else
f:= n*f(n-1)
end;
e.g. f(4)=4*f(4-1)=4*(3*f(3-1))=4*(3*(2*f(2-1)))=4*(3*(2*(1*f(1-1))))
=4*(3*(2*(1*1)))=4*(3*(2*1))=4*(3*2)=4*6=24
2. f(n)=1+2+...+n, n=1,2,...
Express the function by recursive definition:
Basis step: f(1)=1
Inductive step: f(n)-f(n-1)=n
function f(n: positive integer)
begin
if n=1 then f:= 1
else
f:= n+f(n-1)
end;
e.g.
f(4)=4+f(3)=4+(3+f(2))=4+(3+(2+f(1)))=4+(3+(2+(1))) =4+(3+(3))=4+(6)=10
3. A Fibonacci Number is a sequence as below:
1,1,2,3,5,8,13,21,34,...
function f(n: non-negative integer)
begin
if ((n=0) or (n=1)) then f:= 1
else
f:= f(n-1) + f(n-2)
end;
e.g.
f(4)=f(3)+f(2)=(f(2)+f(1))+(f(1)+f(0))=((f(1)+f(0))+f(1)))+(f(1)+f(0))
=((1+1)+1)+(1+1)=(2+1)+(1+1)=3+2=5
Recursive Algorithms: Reduce Problem to smaller problem
Recursive algorithm for linear search:
i=1; // search from a1, …, an
Procedure recur_linear_search (ai, an, key) // search from ai,.., an
If ai=key then
Return i
Else if i==n then // not found
Return 0
Else
recur_linear_search (ai+1, an, key)
Recursive algorithm for binary search:
Procedure recur_bin_search (ai, an, key) // search from ai,.., an
Left=i
Right=n
middle = [pic]
if key==amiddle then
return middle
else if (iamiddle)
recur_bin_search (amiddle+1, an, key)
Recursive algorithm for Euclidean algorithm:
Procedure recur_gcd (a,b where a>b and integers a,b >0)
If b=0 then
Return a
Else
Return recur_gcd(b, a mod b)
Assignment #18
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- lab 20 energy and photosynthesis
- 20 bath and body coupon
- 20 inventors and their inventions
- sequences and series practice problems
- sequences and series test pdf
- arithmetic sequences and series pdf
- october 20 holidays and observances
- unit 1 assignment sequences and series
- arithmetic sequences and series worksheet
- end of chapter 20 questions and answers
- august 20 holidays and observances
- arithmetic sequences and series