Recursion algorithms
Suggestion for students for this section
- You are able to program with any language, such as Pascal,
C, C++, Java.... and you did learn "function call" method
- You will study with your computer in which a familiar
programming software is installed
Recursion Algorithm
Subject: Introduction to Algorithm • Simplify and delegate
Lecturer: Hoang Do Thanh Tung • Tower of Hanoi puzzle
Credit points 3 ECTS • Recursion Algorithm
Level Undergraduate
Teaching time 2021 • Exercises
Location University of Science and Technology of Hanoi
• Practice
Simplify and delegate
Reduction to simplify a problem
Reduction is the single most common technique used in designing algorithms
Reducing one problem X to another problem Y (or set of problems) means
to write an algorithm for X, using an algorithm for Y as a subroutine or black box.
Recursion to delegate a problem to subs
Recursion is a particularly powerful kind of reduction,
Recursion can be defined loosely as follows:
If the given problem is small or simple enough, just solve it. Otherwise,
Reduce the problem to one or more simpler instances of the same problem and
‘simpler’ and ‘simpler’ subproblems
Correctness of a Recursive algorithm is that it must stop and never recurses
forever
It needs a finiteness condition when simplification is either unnecessary or impossible for
a subproblem
Clean the house
Clean the house
Clean the house
Clean the Clean the house
house and Clean the house
don’t ask
anyone else
If you are confused how it works, ..
Method of thinking:
Imagine that someone else is going to solve the simpler problems
Your only task is to simplify the original problem, and
The Recursion Fairy will magically take care of the simpler subproblems
Clean the house
Clean the house
Clean and Clean the house
don’t ask Clean the house
anyone else
Tower of Hanoi puzzle
Remarkable story
The Tower of Hanoi puzzle was first published by the mathematician François
Éduoard Anatole Lucas in 1883,
• In the great temple, there were fixed three diamond needles.
• On one of these needles, at the creation,
• God placed 64 discs of pure gold,
• the discs is smaller and smaller up to the top one.
• The priests transfer the discs from one needle to another according to laws,
• must not move more than one disc at a time, and
• must place this disc on a needle so that there is no smaller disc below it.
• When the 64 discs are moved to another needle is time the world will vanish
Towers of Hanoi
Task: Move n disks from current post to another post.
Post 1 Post 2 Post 3
Rules:
(1) Can only move one disk at a time.
(2) A larger disk can never be placed on top of a
smaller disk.
(3) May use third post for temporary storage.
Solution for n = 2
1 2 3
How is about n>2 ?
Suppose disks start on Post 1, and target is Post 3.
1. Move top n-1 disks to
Post 2. 1 2 3
2. Move largest disk to
Post 3.
1 2 3
3. Move n-1 disks from
Post 2 to Post 3.
1 2
17-11 3
Task Decomposition (cont.)
Task 1 is really the same problem,
with fewer disks and a different target post.
"Move n-1 disks from Post 1 to Post 2."
And Task 3 is also the same problem,
with fewer disks and different starting and target posts.
"Move n-1 disks from Post 2 to Post 3."
So this is a recursive algorithm.
The terminal case is moving the smallest disk -- can move
directly without using third post.
Number disks from 1 (smallest) to n (largest).
Algorithm for n = 6
1. If n = 1:
1.1. Move a single disk from source to dest.
2. If n > 1:
2.1. Let spare be the remaining pole, other than source and dest.
2.2. Move a tower of (n–1) disks from source to spare.
2.3. Move a single disk from source to dest.
2.4. Move a tower of (n–1) disks from spare to dest.
3. Terminate.
source dest spare 2-13
Towers of Hanoi: Pseudocode
MoveDisk(diskNumber, startPost, endPost, midPost)
{
if (diskNumber > 1) {
/* Move top n-1 disks to mid post */
MoveDisk(diskNumber-1, startPost, midPost, endPost);
printf("Move disk number %d from %d to %d.\n",
diskNumber, startPost, endPost);
/* Move n-1 disks from mid post to end post */
MoveDisk(diskNumber-1, midPost, endPost, startPost);
}
else
Move 1 disk from startPost to endPost;
printf("Move disk number 1 from %d to %d.\n",
startPost, endPost);
}
Analyse the algorithm
Analysis (counting moves):
Let the total no. of moves required to move a tower of n disks be moves(n).
Then:
moves(n) = 1 if n = 1
moves(n) = 1 + 2*moves(n–1) if n > 1
Solution:
moves(n) = 2n – 1
Time complexity is O(2n).
Tree of calls for the Tower of Hanoi Puzzle
n
n-1 n-1
n-2 n-2 n-2 n-2
... ... ...
2 2 2 2
1 1 1 1 1 1 1 1
When will the world vanish?
Moving a tower of 64 disks
requires 264 − 1 = 18,446,744,073,709,551,615 individual moves
Impressive rate of one move per second, the monks will be at work for
approximately 585 billion years
Recursion algorithm
Divide and Conquer
Recursion
a special divide and conquer problem solving technique
Wait for someone else to solve the problem of size n − 1, size n −
2, etc...
When you receive the solution for the problem of size n − 1, size n
− 2, etc..., you will then use these solutions to solve
the original problem.
Recursive problem
Recursive problem = a problem that is defined with one or
more smaller problems of the same kind
Example: the factorial of the number n
Example
Now, suppose that you know (e.g., someone told you) that:
Then, we can solve the original problem (10!) very easily:
The Recursive Property
A problem X(n) has the recursive property if:
The problem X(n) can be solved using the solution of one or
more smaller problems X(n−1), X(n−2), ...
A sufficient number of base (simple) cases of the problem can
be solved readily.
Example
The problem factorial(n) can be solved using the
solution of one smaller problem factorial(n−1)
Because one smaller problem is used to solve factorial(n), we
need one base case
The base (simple) case n = 0 of the factorial problem can
be solved readily:
Design Algorithm for a recursive problem
1. Find out which smaller problems you need to use to solve
the original problem
2. Find out how to use the solutions of the smaller
problems to solve the original problem.
3. Find the solutions for a sufficient number of the base cases.
Computing n!
Which smaller problem do we use to solve factorial(n):
How do we use the solution sol1 to solve factorial(n):
Because we used factorial(n−1), we will need the solution for 1 base case:
Computing n! algorithm
int factorial( int n ) {
if ( n <= 1 ) {
return 1;
} else {
return n * factorial( n – 1 );
}
}
int factorial( int n ) {
return (n <= 1) ? 1 : n * factorial( n – 1 );
}
Analyze the algorithm
Thus, we may analyze the run time of this function as follows:
Θ(1) n 1
T! ( n )
T! ( n 1) Θ(1) n 1
The analysis of the run time of this function yields a recurrence relation:
T!(n) = T!(n – 1) + Q(1) T!(1) = Q(1)
Replace each Landau symbol with a representative function:
T!(n) = T!(n – 1) + 1 T!(1) = 1
Analyze an algorithm
we can examine the first few steps:
T!(n) = T!(n – 1) + 1
= T!(n – 2) + 1 + 1 = T!(n – 2) + 2
= T!(n – 3) + 3
From this, we see a pattern:
T!(n) = T!(n – k) + k
Analyze the algorithm
If k = n – 1 then
T!(n) = T!(n – (n – 1)) + n – 1
= T!(1) + n – 1
=1+n–1=n
Thus, T!(n) = Q(n)
Merge-Sort
Merge-sort on an input Algorithm mergeSort(S, C)
sequence S with n elements Input sequence S with n
consists of three steps: elements, comparator C
Output sequence S sorted
Divide: partition S into two
according to C
sequences S1 and S2 of about
n/2 elements each if S.size() > 1
(S1, S2) partition(S, n/2)
Recur: recursively sort S1 and S2
mergeSort(S1, C)
Conquer: merge S1 and S2 into a mergeSort(S2, C)
unique sorted sequence
S merge(S1, S2)
Merging Two Sorted Sequences
The conquer step of Algorithm merge(A, B)
merge-sort consists of Input sequences A and B with
merging two sorted n/2 elements each
sequences A and B into a Output sorted sequence of A B
sorted sequence S
containing the union of the S empty sequence
elements of A and B while A.isEmpty() B.isEmpty()
Merging two sorted if A.first().element() < B.first().element()
sequences, each with n/2 S.insertLast(A.remove(A.first()))
elements and implemented else
by means of a doubly S.insertLast(B.remove(B.first()))
linked list, takes O(n) time while A.isEmpty()
S.insertLast(A.remove(A.first()))
while B.isEmpty()
S.insertLast(B.remove(B.first()))
return S
Merge-Sort Tree
An execution of merge-sort is depicted by a binary tree
each node represents a recursive call of merge-sort and stores
unsorted sequence before the execution and its partition
sorted sequence at the end of the execution
the root is the initial call
the leaves are calls on subsequences of size 0 or 1
7 2 9 4 2 4 7 9
7 2 2 7 9 4 4 9
77 22 99 44
Execution Example
Partition
7 2 9 43 8 6 1 1 2 3 4 6 7 8 9
7 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6
7 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6
77 22 99 44 33 88 66 11
Execution Example (cont.)
Recursive call, partition
7 2 9 43 8 6 1 1 2 3 4 6 7 8 9
7 29 4 2 4 7 9 3 8 6 1 1 3 8 6
7 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6
77 22 99 44 33 88 66 11
Execution Example (cont.)
Recursive call, partition
7 2 9 43 8 6 1 1 2 3 4 6 7 8 9
7 29 4 2 4 7 9 3 8 6 1 1 3 8 6
722 7 9 4 4 9 3 8 3 8 6 1 1 6
77 22 99 44 33 88 66 11
Execution Example (cont.)
Recursive call, base case
7 2 9 43 8 6 1 1 2 3 4 6 7 8 9
7 29 4 2 4 7 9 3 8 6 1 1 3 8 6
722 7 9 4 4 9 3 8 3 8 6 1 1 6
77 22 99 44 33 88 66 11
Execution Example (cont.)
Recursive call, base case
7 2 9 43 8 6 1 1 2 3 4 6 7 8 9
7 29 4 2 4 7 9 3 8 6 1 1 3 8 6
722 7 9 4 4 9 3 8 3 8 6 1 1 6
77 22 99 44 33 88 66 11
Execution Example (cont.)
Merge
7 2 9 43 8 6 1 1 2 3 4 6 7 8 9
7 29 4 2 4 7 9 3 8 6 1 1 3 8 6
722 7 9 4 4 9 3 8 3 8 6 1 1 6
77 22 99 44 33 88 66 11
Merge Sort 39
Execution Example (cont.)
Recursive call, …, base case, merge
7 2 9 43 8 6 1 1 2 3 4 6 7 8 9
7 29 4 2 4 7 9 3 8 6 1 1 3 8 6
722 7 9 4 4 9 3 8 3 8 6 1 1 6
77 22 99 44 33 88 66 11
Execution Example (cont.)
Merge
7 2 9 43 8 6 1 1 2 3 4 6 7 8 9
7 29 4 2 4 7 9 3 8 6 1 1 3 8 6
722 7 9 4 4 9 3 8 3 8 6 1 1 6
77 22 99 44 33 88 66 11
Execution Example (cont.)
Recursive call, …, merge, merge
7 2 9 43 8 6 1 1 2 3 4 6 7 8 9
7 29 4 2 4 7 9 3 8 6 1 1 3 6 8
722 7 9 4 4 9 3 8 3 8 6 1 1 6
77 22 99 44 33 88 66 11
Execution Example (cont.)
Merge
7 2 9 43 8 6 1 1 2 3 4 6 7 8 9
7 29 4 2 4 7 9 3 8 6 1 1 3 6 8
722 7 9 4 4 9 3 8 3 8 6 1 1 6
77 22 99 44 33 88 66 11
Analysis of Merge-Sort
The height h of the merge-sort tree is O(log n)
at each recursive call we divide in half the sequence,
The overall amount or work done at the nodes of depth i is O(n)
we partition and merge 2i sequences of size n/2i
we make 2i1 recursive calls
Thus, the total running time of merge-sort is O(n log n)
depth #seqs size
0 1 n
1 2 n/2
i 2i n/2i
… … …
Compute Sum of 1…n
n
Problem: Running sum ( i)
1
Recursive solution:
RunningSum(1) = 1
RunningSum(n) = n + RunningSum(n-1)
Recursive algorithm:
int RunningSum(int n) {
declare sum
if (n equal to 1)
return 1;
else
sum = n + RunningSum(n-1)
return sum
}
Executing RunningSum
res = RunningSum(4);
return value = 10 RunningSum(4)
return 4 + RunningSum(3);
return value = 6 RunningSum(3)
return 3 + RunningSum(2);
return value = 3 RunningSum(2)
return 2 + RunningSum(1);
return value = 1 RunningSum(1)
return 1;
Now you analyze the algorithm
Compute power
Recursive definition of bn :
bn = 1 if n = 0
bn = b bn–1 if n > 0
Simple recursive power algorithm:
Easy case: solved directly.
To compute bn:
1. If n = 0:
1.1. Terminate with answer 1.
2. If n > 0:
2.1. Terminate with answer b bn–1.
Hard case: solved by computing bn–
1, which is easier since n–1 is closer
than n to 0.
Design the algoritm
int power (int b, int n) {
if n equal to 0
return 1;
else
return b * power(b, n-1);
}
Now analyze the algorithm
A smart solution
Idea: b1000 = b500 b500, and b1001 = b b500 b500.
Alternative recursive definition of bn:
bn = 1 if n = 0
bn = bn/2 bn/2 if n > 0 and n is even
bn = b bn/2 bn/2 if n > 0 and n is odd
(Recall: n/2 discards the remainder if n is odd.)
Recursive solution
Smart recursive power algorithm:
To compute bn:
Easy case: solved directly.
1. If n = 0:
1.1. Terminate with answer 1.
Hard case: solved by comput-
2. If n > 0:
ing bn/2, which is easier since
2.1. Let p be bn/2.
n/2 is closer than n to 0.
2.2. If n is even:
2.2.1. Terminate with answer p p.
2.3. If n is odd:
2.3.1. Terminate with answer b p p.
Design an algorithm
int power (int b, int n) {
if (n equal to 0)
return 1;
else {
Set p to power(b, n/2);
if (n mod 2 equal to 0)
return p * p;
else
return b * p * p;
}
}
Now analyze the algorithm
Analysis
Analysis (counting multiplications):
Each recursive power algorithm performs the same number of multiplications
as the corresponding non-recursive algorithm. So their time complexities are
the same:
non-recursive recursive
Simple power algorithm O(n) O(n)
Smart power algorithm O(log n) O(log n)
Recursive Squaring
We can derive a more efficient linearly
recursive algorithm by using repeated
squaring:
1 if x 0
p ( x, n) x p ( x, ( n 1) / 2) 2 if x 0 is odd
p ( x, n / 2) 2 if x 0 is even
For example,
24 = 2(4/2)2 = (24/2)2 = (22)2 = 42 = 16
25 = 21+(4/2)2 = 2(24/2)2 = 2(22)2 = 2(42) = 32
26 = 2(6/ 2)2 = (26/2)2 = (23)2 = 82 = 64
27 = 21+(6/2)2 = 2(26/2)2 = 2(23)2 = 2(82) = 128.
56
A Recursive Squaring Method
Algorithm Power(x, n):
Input: A number x and integer n = 0
Output: The value xn
if n = 0 then
return 1
if n is odd then
y = Power(x, (n - 1)/ 2)
return x · y ·y
else
y = Power(x, n/ 2)
return y · y
Analyzing the algorithm
Algorithm Power(x, n):
Input: A number x and integer n
=0
Output: The value xn
if n = 0 then Each time we make a
recursive call we halve the
return 1 value of n; hence, we make
if n is odd then log n recursive calls. That
y = Power(x, (n - 1)/ 2) is, this method runs in
O(log n) time.
return x · y · y
else
It is important that we
y = Power(x, n/ 2) used a variable twice here
return y · y rather than calling the
method twice.
Exercises
Fibonacci sequence problem
The Fibonacci sequence:
{fn } = 0,1,1,2,3,5,8,13,21,34,55
Mathematical Definition:
f ( n ) f ( n 1) f ( n 2)
f (1) 1
f (0 ) 1
In other words, the n-th Fibonacci number is the sum of the previous two
Fibonacci numbers.
Design a recursive algorithm
Write recursive algorithm, and
Analyze the algorithm
Linear search problem
PROBLEM: Start with a collection of names N1, N2, ..., N10000,
and corresponding telephone numbers T1, T2, ..., T10000.
Given a name, Name, find a telephone number for that
name if a match on an Ni occurs; otherwise, print "Not
Found".
Note: In the book, subscripts are used for N1, N2, etc.
Design a recursive algorithm
Write recursive algorithm, and
Analyze the algorithm
FIND LARGEST Problem
PROBLEM: Given n, the size of a list, and a list of n numbers, find
the largest number in the list.
Design a recursive algorithm
Write recursive algorithm, and
Analyze the algorithm
Binary Search problem
Searching a sorted list
How can we exploit the structure that a sorted list
provides?
Start in the middle and determine in which half of the list
our target lives
Repeatthis procedure eliminating half of the remaining list
elements on each iteration
What is the maximum number of comparisons required here?
Design a recursive algorithm
Write recursive algorithm, and
Analyze the algorithm
Computing Prefix Averages Problem
We further illustrate asymptotic analysis with two
algorithms for prefix averages
The i-th prefix average of an array X is average of
the first (i 1) elements of X:
A[i] (X[0] X[1] … X[i])/(i+1)
Design a recursive algorithm
Write recursive algorithm, and
Analyze the algorithm
Examples of Algorithms – Computing the
Greatest Common Divisor of Two Integers
The greatest common divisor of two non-negative, not-both-zero integers
m and n, denoted gcd(m, n), is defined as the largest integer that divides
both m and n evenly, until the remainder is zero
Euclid’s algorithm is based on repeated application of equality until the
second number becomes 0
gcd(m, n) = gcd(n, m mod n)
For example gcd(60, 24) can be computed as follows:
gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12
x, if y 0
gcd( x, y )
gcd( y, x mod y ), otherwise
Design a recursive algorithm
Write recursive algorithm, and
Analyze the algorithm
Selection Sort
n is the size of unsorted list.
if n is 1,
- array is sorted
else
- (1) find the smallest element in the
unsorted array list
- (2) swap the 1st element in the
unsorted array with the smallest
element
- (3) sort the remaining unsorted array
Design a recursive algorithm
Write recursive algorithm, and
Analyze the algorithm
