Recursion

CS A262 – Discrete Structures

1
Recursive
Formulas

2
Recursive Definitions (cont.)

▶ One way to define a sequence is to use recursion.

▶ A Recurrence Relation requires:

▶ An initial condition (basis step)
▶ A recursive step

3
Example

▶ Suppose that f is defined recursively by

f (0) = 3
f (n + 1) = 2 f (n) + 3
Find f (1), f (2), f (3), and f (4)

4
Example

▶ Suppose that f is defined recursively by

f (0) = 3
f (n + 1) = 2 f (n) + 3
Find f (1), f (2), f (3), and f (4)

▶ Solution:

f (1)
We know how to find f (n + 1).
If we want to find f (1), then
n+1=1
which means that n = 0 5
Example

▶ Suppose that f is defined recursively by

f (0) = 3
f (n + 1) = 2 f (n) + 3
Find f (1), f (2), f (3), and f (4)
We know how to find f (n + 1).
If we want to find f (1), then
▶ Solution: n+1=1
which means that n = 0
f (1) = 2 f (0) + 3 = 2 * 3 + 3 = 9

6
Example

▶ Suppose that f is defined recursively by

f (0) = 3
f (n + 1) = 2 f (n) + 3
Find f (1), f (2), f (3), and f (4)

▶ Solution:

f (1) = 2 f (0) + 3 = 2 * 3 + 3 = 9
f (2) = 2 f (1) + 3 = 2 * 9 + 3 = 21
f (3) = 2 f (2) + 3 = 2 * 21 + 3 = 45
f (4) = 2 f (3) + 3 = 2 * 45 + 3 = 93

7
Example: Factorial Function

▶ Find a recursive definition for the factorial function

F(n) = n!

▶ Recall
4! = 4 * 3 * 2 * 1
0! = 1

8
Example: Factorial Function
(cont.)
▶ How can we find the recursive function?

▶ We know:

F(n) = 1 if n = 0 (base case)

▶ We don’t know:

F(n) = ? if n > 0 (recursive function)

9
Example: Factorial Function
(cont.)
▶ Reason on a couple of examples:
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!

▶ Look for a pattern:

F(n) = n * F(n – 1)

▶ Final result:
F(n) = 1 if n = 0 (base case)

F(n) = n * F(n – 1) if n > 0 (recursive 10

definition)
Example: Fibonacci Numbers

▶ The Fibonacci series starts with 0 and 1 and has the

property that each subsequent Fibonacci number is the sum
of the previous two Fibonacci numbers.
Fibonacci(0) = 0

Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = 2
Fibonacci(4) = 3
Fibonacci(5) = 5
Fibonacci(6) = 8

11
Example: Fibonacci Numbers (cont.)

▶ Base case for Fibonacci series:

Fibonacci(0) = 0

Fibonacci(1) = 1

▶ Look for a pattern to find the recursive case

Fibonacci(2) = Fibonacci(1) + Fibonacci(0)

Fibonacci(3) = Fibonacci(2) + Fibonacci(1)

Fibonacci(4) = Fibonacci(3) + Fibonacci(2)
Fibonacci(5) = Fibonacci(4) + Fibonacci(3) 12
 Example: Fibonacci Numbers
(cont.)
▶ Base case for Fibonacci series:
Fibonacci(0) = 0

Fibonacci(1) = 1

▶ Look for a pattern to find the recursive case

Fibonacci(2) = Fibonacci(1) + Fibonacci(0)

Fibonacci(3) = Fibonacci(2) + Fibonacci(1)

Fibonacci(4) = Fibonacci(3) + Fibonacci(2)
Fibonacci(5) = Fibonacci(4) + Fibonacci(3)
13

Recursive case → Fibonacci(n) = Fibonacci(n – 1) + Fibonacci(n – 2)

Example: Fibonacci Numbers (cont.)

▶ Base case for Fibonacci series:

Fibonacci(0) = 0

Fibonacci(1) = 1

▶ Recursive expression:
Fibonacci (n) = Fibonacci (n – 1) + Fibonacci (n – 2)

14
 Lecture Problems
▶ Given  f(n) = (0.5)f(n-1), where f(0) = 12

What is f(3)?

a) 12
b) 6
c) 3
d) 1.5

15
 Lecture Problems
▶ Given  f(n) = (0.5)f(n-1), where f(0) = 12

What is f(3)?

d) 1.5

16
 Lecture Problems
▶ Given  g(n) = 3 g(n-1) + g(n-2)
with g(0) = 1 and g(1) = 5

What is g(3)?

a) 6
b) 53
c) 16
d) 45

17
 Lecture Problems
▶ Given  g(n) = 3 g(n-1) + g(n-2)
with g(0) = 1 and g(1) = 5

What is g(3)?

b) 53

18
Recursive Sets
Recursive Sets

▶ Defined by
▶ Base case
▶ Defines specific elements to build on to
create other elements
▶ Recursive rule(s)
▶ Defines how to create all elements of the
set starting with the base case elements
▶ Exclusion statement
▶ Implied for almost every recursive set
▶ States the only elements of the set are the
base case elements and those that can be 20
constructed using the rules
Example: Set of Boolean Expressions

▶ Legal expressions involve the following symbols

▶ ∧ ∨ ∼ ( )
▶ Lowercase letters

▶ Examples:
▶ p ∧ (q ∨ ∼r )
▶ p
▶ q ∨ ∼r

21
Recursive Definition

▶ Base case
▶ Every lowercase letter is a Boolean Expression
▶ Recursive rules
▶ If P and Q are Boolean expressions, then so are
▶ (a) P ∧ Q and (b) P ∨ Q and (c) ∼P and
(d) (P)
▶ Exclusion statement
▶ There are no Boolean expressions over the
alphabet other than those obtained from Base
case and Recursive rules.

22
Elements

Recursive rules
If P and Q are Boolean expressions, then so are
(a) P ∧ Q and (b) P ∨ Q and (c) ∼P and
(d) (P)

▶ Is ∼r ∧ p a Boolean Expression?

23
Elements

Recursive rules
If P and Q are Boolean expressions, then so are
are P ∧ Q and (b) P ∨ Q and (c) ∼P and
(a)
(P)∧ Q) and (b) (P ∨ Q) and (c) ∼P
(a) (P
(d)

▶ Is ∼r ∧ p a Boolean Expression?
▶ The base case says r and p are Boolean
Expressions
▶ By (c), ∼r is a Boolean Expression
▶ By (a), ∼r ∧ p is a Boolean Expression 24
Example 2

▶ Let S be a recursively defined set

▶ Base case
▶ 1∈S
▶ Recursive rules
▶ If s ∈ S, then
▶ (a.) 0s ∈ S (b.) 1s ∈ S
▶ Exclusion statement
▶  Nothing is in S other than objects defined in
Base case or Recursive rules

25
Some Elements

▶ Show 1011 is in S
Recursive rules
If s ∈ S, then
(a.) os ∈ S (b.) 1s ∈ S

26
Some Elements

▶ Show 1011 is in S
Recursive rules
If s ∈ S, then
(a.) os ∈ S (b.) 1s ∈ S
▶ 1 Base
▶ 11 (b)
▶ 011 (a)
▶ 1011 (b)

27
 Lecture Problems
▶ Given some recursive set S as defined by
▶ Base
▶ 1∈S
▶ Recursive rules
▶ If s ∈ S, then
▶ (a.) s0 ∈ S (b.) s1 ∈ S

Is the string 0111 in S?

a) Yes
28

b) No
 Lecture Problems
▶ Given some recursive set S as defined by
▶ Base
▶ 1∈S
▶ Recursive rules
▶ If s ∈ S, then
▶ (a.) s0 ∈ S (b.) s1 ∈ S

Is the string 0111 in S?

29
b) No
 Lecture Problems
▶ Given some recursive set S as defined by
▶ Base
▶ 1∈S
▶ Recursive rules
▶ If s ∈ S, then
▶ (a.) s0 ∈ S (b.) s1 ∈ S

Is the string 11011 in S?

a) Yes
30
b) No
 Lecture Problems
▶ Given some recursive set S as defined by
▶ Base
▶ 1∈S
▶ Recursive rules
▶ If s ∈ S, then
▶ (a.) s0 ∈ S (b.) s1 ∈ S

Is the string 11011 in S?

a) Yes
31
 Recursive
Algorithms
Recursive Algorithm
▶ Defined by

▶ Base Case
▶ When does it stop!?

▶ Recursive Case
▶ Solve a smaller version of the same
problem by calling itself
▶ Should break down the larger problem

▶ Builds a solution by piecing together all the

33
little pieces
Example: Exponents

▶ Behavior: ▶ Phrased another way…

▶ 22 = 4 ▶ 35
▶ 2*2 = 3 * 34

▶ 5
3 = 243 ▶ 34
= 3 * 33
▶ 3*3*3*3*3
▶ 33
= 3 * 32
▶ 32
= 3 * 31
▶ 31
= 3 * 30
34
0
▶ 3 =1
Example: Exponents, Iterative
Solution
int result = 1;
int pow, base;
cin >> pow >> base; // Note: You should prompt the user
for (int i = pow; i > 0; --i) {
result *= base;
}

35
Example: Exponents

▶ To compute rn …..

▶ Base Case?

▶ Recursive Case?

36
Example: Exponents

▶ To compute rn …..

▶ Base Case?
▶ n=0
▶ Recursive Case?

37
Example: Exponents

▶ To compute rn …..

▶ Base Case?
▶ n=0
▶ Recursive Case?
▶ result = r * r(n-1)

38
Example: Exponents

int exponent(int base, int exp){

if(exp == 0)
return 1;
return base * exponent(base, exp -1);
}

39
Example: Balanced Pattern

▶ Create a recursive algorithm that prints out a

pattern made up of n balanced copies of two
characters.

▶ makePattern(“<” , “>”, 4) should return <<<<>>>>

▶ makePattern(“a” , “b”, 1) should return ab

40
Example: Balanced Pattern
Iterative Solution
string thePattern;
for (int i = numReps; i > 0; --i)
{
thePattern += left;
}
for (int i = numReps; i > 0; --i)
{
thePattern += right;
}
41
 Example: Balanced Pattern Iterative
Solution Building Inside Out

string thePattern;
for(int i = numReps; i > 0; --i){
thePattern = left + thePattern + right;
}

42
Example: Balanced Pattern

▶ Create a recursive algorithm that prints out a

pattern made up of n balanced copies of two
characters.

▶ Base Case?
▶ n =0
▶ Recursive case?
▶ char1 + balancedPattern + char2

43
 Example: Balanced Pattern

string makePattern( const string& a, const string& b, int numReps){

if(numReps == 0)
return “”;
return a + makePattern(a, b, numReps - 1) + b;

44
 Lecture Problems
int f (int n){
if( n == 0)
return 0;
return n + f (n-1);
}
What is the base case value?
a) 0
b) 1
c) N
d) Cannot be determined

45
 Lecture Problems
int f (int n){
if( n == 0)
return 0;
return n + f (n-1);
}
What is the base case value?
a) 0

46
 Lecture Problems
int f (int n){
if( n == 0)
return 0;
return n + f (n-1);
}
What is f(3)?
a) 9
b) 3
c) 6
d) 0

47
 Lecture Problems
int f (int n){
if( n == 0)
return 0;
return n + f (n-1);
}
What is f(3)?

c) 6

48
Recursion (END)

49