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.

Google Online Preview   Download