Chapter 3
Recursion and Recurrence Relations
CS 130 – Discrete Structures
Recursive Examples
CS 130 – Discrete Structures 2
Recursion
• Recursive definitions: define an entity in terms of itself.
• There are two parts:
– Basic case (basis): the most primitive case(s) of the entity
are defined without reference to the entity.
– Recursive (inductive) case: new cases of the entity are
defined in terms of simpler cases of the entity.
• Recursive sequences
– A sequence is an ordered list of objects, which is
potentially infinite. s(k) denotes the kth object in the
sequence.
– A sequence is defined recursively by explicitly naming the
first value (or the first few values) in the sequence and
then define later values in the sequence in terms of earlier
values.
CS 130 – Discrete Structures 3
Examples of Recursive Sequence
• A recursively defined sequence:
– S(1) = 2 …… basis case
– S(n) = 2 * S(n-1), for n >= 2 …… recursive case
– what does the sequence look like?
– T(1) =1 …… basis case
– T(n) = T(n-1) + 3, for n >= 2 …… recursive case
– what does the sequence look like?
CS 130 – Discrete Structures 4
Fibonacci Sequence
• The Fibonacci Sequence is defined by:
• F(1) = 1, F(2) = 1 …… basis case
• F(n) = F(n-2) + F(n-1), for n > 2 …… recursive case
• the sequence?
• [Link]
CS 130 – Discrete Structures 5
Proofs Related To Recursively Defined
Sequence
• Proofs of properties about recursively defined
entities are typically inductive proofs.
• Prove directly from the definition
• For example:
– prove that in the Fibonacci sequence:
– F(n+4) = 3F(n+2) – F(n), for n >= 1
– F(n+1) + F(n-2) = 2F(n), for n >= 3
CS 130 – Discrete Structures 6
Recursively Defined Operations
• Certain operations performed on objects can
be defined recursively
• Examples:
– A recursive definition of multiplication:
• m*1=m
• m * n = m * (n-1) + m, for n >= 2
– A recursive definition of exponentiation:
• a0 = 1
• an = (an-1)*a, for n > 0
– A recursive definition of factorial operation:
• F(0) = 1
• F(n) = n * F(n-1) for n >= 1
CS 130 – Discrete Structures 7
Examples
• Give a recursive definition of the following sets
of objects:
– 1, 3, 9, 27, 81, …
– 2, 1, ½, ¼, 1/8, …
– 1, 2, 4, 7, 11, 16, 22, …
CS 130 – Discrete Structures 8
Recursively Defined Algorithms
• If a recurrence relation exists for an operation, then the
algorithm for such a relation can be written either
iteratively or recursively
• Example: factorial, multiplication, etc.
• Factorial: S(1) = 2, S(n) = 2S(n-1) for n >= 2
Calculate S(n):
if n = 1 then output 2 and return Calculate S(n):
j=2 if n = 1 then
S=2 return 2
while j <= n else
S = S*2 return 2*S(n-1)
j=j+1 endif
end while
output S
CS 130 – Discrete Structures 9
Solving Recurrence Relations
• Closed-form solution
– S(1) = 2
– S(n) = 2*S(n-1) for n >= 2
– Since S(1) = 2 = 21, S(2) = 4 = 22, S(3) = 8 = 23, …
– We can see S(n) = 2n, and it is called a closed-form
solution to the recurrence relation
– Finding a closed-form solution is called solving
recurrence relation
• General method: expand, guess and verify
• Another method: solution formula (will not be
covered here)
CS 130 – Discrete Structures 10
Example of Expand, Guess, and Verify
• The factorial example:
– S(1) = 2
– S(n) = 2S(n-1) for n >= 2
• Expand:
S(n) = 2S(n-1) = 2[2S(n-2)] = 22S(n-2)
= 22[2S(n-3)] = 23S(n-3)
• Guess: after k such expansions, the equation
has the form: S(n) = 2kS(n-k)
– it stops when n-k = 1, that is when k = n-1, replace
k with (n-1)
– S(n) = 2n-1S(n-(n-1)) = 2n-1S(1) = 2n
• Verify: proof by induction
CS 130 – Discrete Structures 11
Exercise
• Solve the recurrence relation:
– F(1) = 1
– F(n) = n*F(n-1) for n >= 2
• Given the Fib. definition, prove that
– F(n) = 5*F(n-4) + 3*F(n-5) for n >= 6
CS 130 – Discrete Structures 12