8.

Recursive Algorithms

Learning Objectives:
To introduce recursive algorithms
To understand the difference between iterative
and recursive algorithms

Lecture Plan:
- Introduction
- Examples
8.1 Calculating n!
8.2 Recursive binary search
8.3 Euclid’s algorithm
Introduction
There are two approaches to writing repetitive algorithms:
Iteration involves loops Recursion
(while-loops, for-loops) is a repetitive process in which
an algorithm calls itself.
Problem(4)
The size of the problem is
reduced
Problem(3)
The size of the problem is
reduced
Problem(2)
The base case: solving the
trivial problem of small size
Problem(1)
Introduction
▪ Recursion solves a problem by solving a smaller instance of the
same problem
▪ It solves this new problem by solving an even smaller instance of
the same problem.
▪ Eventually the problem will be so small that its solution will be
obvious.

A recursive algorithm should consist of two parts:

▪ base case
▪ recursive part
 8.1 Calculating n!

We start with a popular example, which is often used to introduce

recursive algorithms.
Consider calculation of the factorial function n! defined as

1, if n = 0,
Factorial ( n ) = 
1  2  3  ...  ( n − 1)  n, if n  1

Iterative formula: Recursive formula:

0! = 1, Factorial(0) = 1
n! = 12  …  n for n1 Factorial(n) = Factorial(n-1)  n
Iterative formula: Recursive formula:
0! = 1, Factorial(0) = 1
n! = 12  …  n for n1 Factorial(n) = Factorial(n-1)  n

ALGORITHM itFactorial(n) ALGORITHM Factorial(n)

if n==0 return 1 if n == 0 return 1
product  1 else return Factorial(n-1)*n
for i1 to n do
productproduct*i return 6
return product 3
Factorial(n)
if n == 0 return 1
2 2
else return Factorial(n-1)*n 3
return 2
2
Factorial(n)
Tracing for n=3: if n == 0 return 1
1 1
else return Factorial(n-1)*n 2
i product return 1
1
Factorial(n)
1 if n == 0 return 1
1 0
else return Factorial(n-1)*n 1
1 1×1=1
return 1
2 1×2=2 0
Factorial(n)
if n == 0 return 1
3 2×3=6 else return Factorial(n-1)*n
Iterative formula: Recursive formula:
0! = 1, Factorial(0) = 1
n! = 12  …  n for n1 Factorial(n) = Factorial(n-1)  n

ALGORITHM itFactorial(n) ALGORITHM Factorial(n)

if n==0 return 1 if n == 0 return 1
product  1 else return Factorial(n-1)*n
for i1 to n do
productproduct*i Factorial(3) Factorial(3)
return product return 2×3=6

Factorial(2) Factorial(2)
Tracing for n=3: return 1×2=2

i product
Factorial(1) Factorial(1)
1 return 1×1=1
1 1×1=1
Factorial(0) Factorial(0)
2 1×2=2
return 1
3 2×3=6
Iterative formula: Recursive formula:
0! = 1, Factorial(0) = 1
n! = 12  …  n for n1 Factorial(n) = Factorial(n-1)  n

ALGORITHM itFactorial(n) ALGORITHM Factorial(n)

if n==0 return 1 if n == 0 return 1
product  1 else return Factorial(n-1)*n
for i1 to n do
productproduct*i Factorial(3)
return product return 2×3=6

Factorial(2)
Tracing for n=3: return 1×2=2

i product
Factorial(1)
1 return 1×1=1
1 1×1=1
2 1×2=2 Factorial(0)
3 2×3=6 return 1
Recursive Calls

In a recursive algorithm, when the current module calls a

subroutine, it suspends processing and the called subroutine
takes over control of the program.

When the subroutine completes its processing and returns

to the module that called it, the module wakes up and
continues processing.
ALGORITHM itFactorial(n)
if n==0 return 1 ALGORITHM Factorial(n)
product  1 if n == 0 return 1
for i1 to n do *
else return Factorial(n-1)*n
*
productproduct*i
return product

What is the algorithm’s main operation?

Multiplication Multiplication
How many times is the basic operation executed?

n One multiplication after

each of n recursive calls

What is the class O(?) the algorithm belongs to?

O(n) O(n)
ALGORITHM itFactorial(n)
if n==0 return 1 ALGORITHM Factorial(n)
product  1 if n == 0 return 1
for i1 to n do else return Factorial(n-1)*n
*
*
productproduct*i
return product

A preferred method for analysing recursive algorithms:

1) Determine the algorithm’s main operation

Multiplication
2) Set up a recurrence relation with initial condition
M(n) = M(n-1) + 1 for n>0

multiplications multiplications to multiply

to compute to compute Factorial(n-1)
Factorial(n) Factorial(n-1) by n
M(0) = 0 (no multiplications if n=0)

3) Solve the recurrence or estimate the rate of growth of its solution

Method of backward substitutions (next slide)
Method of backward substitutions for M(x) = M(x-1) + 1 for x>0
M(0) = 0
M(n) = M(n-1) +1 (substitute M(n-1) = M(n-2)+1)
=[M(n-2)+1] + 1
=M(n-2) +2 (substitute M(n-2) = M(n-3)+1)
=[M(n-3)+1] + 2
=M(n-3) +3

After several substitutions we can make a guess:

M(n) = M(n-i) + i for 0 ≤ i ≤ n.

The correctness of this formula can be proved by mathematical induction.

Substituting i=n we obtain:

M(n) = M(n-1) + 1 = … = M(n-i) + i = … = M(n-n) + n = 0+n = n.

Thus recursive algorithm Factorial(n) performs n multiplications, and therefore it is

O(n).
Divide-and-Conquer

1. Divide: a problem’s instance is divided into two

smaller instances.

2. Recur: the smaller instances are solved

recursively.

3. Conquer: if necessary, the solutions obtained for

the smaller instances are combined in order to
get a solution to the original problem.
 8.2 Binary Search (recursive)
ALGORITHM binarySearch(A[l..r],K)
//Input: an array A[l..r] sorted in ascending
//order, defined by its left and right indices
//l and r and a search key K
//Output: an index of the array’s element that
//is equal to K
//or –1 if there is no such element
if there are no
l elements
> r to search return –1
 8.2 Binary Search (recursive)
ALGORITHM binarySearch(A[l..r],K)
//Input: an array A[l..r] sorted in ascending
//order, defined by its left and right indices
//l and r and a search key K
//Output: an index of the array’s element that
//is equal to K
//or –1 if there is no such element
if l > r return –1 //there are no elements to search
else
mid  (l+r)/2
if K == A[mid] return mid
else
if K < A[mid] return binarySearch(A[l..mid-1],K)
else return binarySearch(A[mid+1..r],K)
 8.2 Binary Search (recursive)
if l > r return –1
else
mid  (l+r)/2
if K == A[mid] return mid
else
if K < A[mid] return binarySearch(A[l..mid-1],K)
else return binarySearch(A[mid+1..r],K)

while l  r do
mid  (l+r)/2
if K == A[mid] return mid
else
if K < A[mid] r  mid-1
else l  mid+1
return –1
 8.2 Binary Search (recursive)
if l > r return –1
else
mid  (l+r)/2
if K == A[mid] return mid
else
if K < A[mid] return binarySearch(A[l..mid-1],K)
else return binarySearch(A[mid+1..r],K)
l=0 1 2 3 4 5 6 7 8 9 10 11 r=12 binarySearch(A[0..12], 19)
11 12 13 16 19 20 25 27 30 35 39 41 46 Return 4

l=0 1 2 3 4 r=5 binarySearch(A[0..5], 19)

11 12 13 16 19 20 Return 4

l=3 4 r=5 binarySearch(A[3..5], 19)

16 19 20 Return 4
 Analysis of Recursive Binary Search [A. Levitin]
1) Determine the algorithm’s main operation
Select K==A[mid] as the most frequent operation

2) Set up a recurrence relation with initial condition

The size of the input array is n = r–l+1.
comparisons K==A[mid] performed by
binarySearch(A[l..mid-1],K) or
binarySearch(A[mid+1..r],K)

C(n) = C(n/2) + 1 for n>1

comparisons K==A[mid] performed one comparison K==A[mid]

by binarySearch(A[l..r],K) to select subarray
in the worst case A[l..mid-1]or
C(1) = 1 (one comparison if n=1) A[mid+1..r]
3) Solve the recurrence or estimate the rate of growth of its solution
(next slide)
Method of backward substitutions for C(x) = C(x/2) + 1 for x>1
C(1) = 1
q
Consider n=2 . This implies q=log2n.
C(2q) = C(2q-1) +1 (substitute C(2q-1) = C(2q-2) +1)
= [C(2q-2) +1] + 1
= C(2q-2) +2 (substitute C(2q-2) = C(2q-3) +1)
= [C(2q-3) +1] + 2
= C(2q-3) +3
After several substitutions we can make a guess:
C(2q) = C(2q-i) + i for 0 ≤ i ≤ q.

The correctness of this formula should be proved by mathematical induction.

Substituting i=q we obtain:

C(2q) = C(2q-1)+1 = … = C(2q-i) + i = … = C(2q-q) + q = C(1) + q =1+ log2n.

Recursive implementation of binary search performs at most 1+ log2n

comparisons, the same as the iterative version.
The running time of both versions of the algorithm is O(logn).
 Method of backward substitutions for C(x) = C(x/2) + 1 for x>1
2q-1<n ≤ 2q q=log2n C(1) = 1
q
Consider n=2 . This implies q=log2n.
C(n) ≤ C(2q) = C(2q-1) +1 (substitute C(2q-1) = C(2q-2) +1)
= [C(2q-2) +1] + 1
= C(2q-2) +2 (substitute C(2q-2) = C(2q-3) +1)
= [C(2q-3) +1] + 2
= C(2q-3) +3
After several substitutions we can make a guess:
C(n) ≤ C(2q) = C(2q-i) + i for 0 ≤ i ≤ q.

The correctness of this formula should be proved by mathematical induction.

Substituting i=q we obtain: log2n

C(n)≤C(2q) = C(2q-1)+1 = … = C(2q-i) + i = … = C(2q-q) + q = C(1) + q =1+ log2n.

Recursive implementation of binary search performs at most 1+ log2n

comparisons, the same as the iterative version.
The running time of both versions of the algorithm is O(logn).
 8.3 Find the Highest Common Factor

Problem Given two non-negative integers a and b, find their

highest common factor (h.c.f.), i.e., the largest integer
that divides both a and b (with the remainder zero).

Algorithm 1 Algorithm 2 Algorithm 3 (Euclid)

(brute force)
1. Find all prime 1.While b>0, apply
1. Assign the value of factors of a and b repeatedly the
min{a, b} to h. formula
2. If h is not a divisor 2.Identify all
of a and b, then common primes hcf(a,b)=hcf(b,amodb)
decrease h by 1 and multiply them if b==0 return a
and try again. to get the h.c.f.
3. Return h.
Sieve of Eratosthenes
Example 3: finding h.c.f.

Euclid’s Algorithm
(recursive)
ALGORITHM hcf(a,b)
if b==0 return a
return hcf(b,amodb)

Euclid’s Algorithm
(iterative)
ALGORITHM hcf(a,b)
while b0 do
r  amodb
a  b
b  r
return a
 Example 3: finding h.c.f.
(a) Box-tracing for a=24, b=36
return 12 Euclid’s Algorithm
hcf(24,36)
if 36
b==0 return a (recursive)
return hcf(b,36, amodb)
24 ALGORITHM hcf(a,b)
return 12
hcf(36,24) if b==0 return a
if 24
b==0 return a return hcf(b,amodb)
24, amodb)
return hcf(b, 12
return 12
hcf(24,12) hcf(24,36)=hcf(36,24)=hcf(24,12)=
if 12
b==0 return a =hcf(12,0)=12
12, amodb)
return hcf(b, 0
return 12
hcf(12,0)
if b==0
0 return 12
a
return hcf(b, amodb)

(b) The base case is appropriate since the problem gets smaller, at least
starting from the second recursive call. The base case is always reached.
 Conclusions

As a rule, a recursive algorithm is simpler than its

iterative counterpart.

For some problems, it

If you can easily, is difficult or even
clearly, and efficiently impossible to develop
solve a problem by an an iterative algorithm. If
iterative algorithm you a recursive algorithm
should do so. is straightforward, you
should do so.