COMP 251: Recurrences
Jérôme Waldispühl School of Computer Science
McGill University
Based on slides from Hatami, Bailey, Stepp & Martin, Snoeyink.
Outline
• Introduction: Thinking recursively
• Definition
• Examples:
o Binary search
o Fibonacci numbers o Merge sort
o Quicksort
• Running time
• Substitution method
Course credits
c(x) = total number of credits required to complete course x c(COMP462) = ?
= 3 credits + #credits for prerequisites COMP462 has 2 prerequisites: COMP251 & MATH323
= 3 credits + c(COMP251) + c(MATH323) The function c calls itself twice
c(COMP251) = ? c(MATH323) = ?
c(COMP251) = 3 credits + c(COMP250) COMP250 is a prerequisite
Substitute c(COMP251) into the formula:
c(COMP462) = 3 credits + 3 credits + c(COMP250) + c(MATH323) c(COMP462) = 6 credits + c(COMP250) + c(MATH323)
Course credits
c(COMP462) = 6 credits + c(COMP250) + c(MATH323) c(COMP250) = ? c(MATH323) = ? c(COMP250) = 3 credits # no prerequisite
c(COMP462) = 6 credits + 3 credits + c(MATH323) c(MATH323) = ?
c(MATH323) = 3 credits + c(MATH141)
c(COMP462) = 9 credits + 3 credits + c(MATH141) c(MATH141) = ?
c(MATH141) = 4 credits # no prerequisite
c(COMP462) = 12 credits + 4 credits = 16 credits
Recursive definition
A noun phrase is either
•anoun, or
• an adjective followed by a noun phrase
big black
dog
Definitions
Recursive definition:
A definition that is defined in terms of itself. Recursive method:
A method that calls itself (directly or indirectly).
Recursive programming:
Writing methods that call themselves to solve problems recursively.
Why using recursions?
• “culturalexperience”-Adifferentwayofthinkingof problems
• Cansolvesomekindsofproblemsbetterthan iteration
• Leadstoelegant,simplistic,shortcode(whenused well)
• Manyprogramminglanguages(“functional” languages such as Scheme, ML, and Haskell) use recursion exclusively (no loops)
• Recursionisoftenagoodalternativetoiteration (loops).
Definition
Definition (recurrence):
A recurrence is a function is defined in terms of • oneormorebasecases,and
• itself,withsmallerarguments.
Examples:
1 𝑖𝑓 𝑛 = 1 1
𝑖𝑓 𝑛 = 1
𝑇𝑛 =$𝑇𝑛−1 +1 𝑖𝑓𝑛>1
𝑇𝑛 =+𝑇 𝑛 +𝑇 2.𝑛 +𝑛 𝑖𝑓𝑛>1 33
Many technical issues:
• Floorsandceilings
• Exactvs.asymptoticfunctions
• Boundaryconditions
Note: we usually express both the recurrence and its solution using asymptotic notation.
Iterative algorithms
Definition (iterative algorithm): Algorithm where a problem is solved by iterating (going step-by-step) through a set of commands, often using loops.
Algorithm: power(a,n)
Input: non-negative integers a, n Output: an
product ← 1
for i = 1 to n do
product ← product * a return product
i
0
1
2
3
4
product
1
a
a * a = a2
a2 *a=a3
a3 *a=a4
Recursive algorithms
Definition (Recursive algorithm): algorithm is recursive if in the process of solving the problem, it calls itself one or more times.
Algorithm: power(a,n)
Input: non-negative integers a, n
Output: an
if (n=0) then
return 1 else
return a * power(a,n-1)
Example
power(7,4) calls power(7,3) calls
power(7,2) calls power(7,1) calls
power(7,0) returns 1 returns 7 * 1 = 7
returns 7 * 7 = 49 returns 7 * 49 = 343
returns 7 * 343 = 2041
Algorithm structure Every recursive algorithm involves at least 2 cases:
base case: A simple occurrence that can be answered directly.
recursive case: A more complex occurrence of the problem that cannot be directly answered but can instead be described in terms of smaller occurrences of the same problem.
Some recursive algorithms have more than one base or recursive case, but all have at least one of each.
A crucial part of recursive programming is identifying these cases.
Binary Search
Algorithm binarySearch(array, start, stop, key) Input: – A sorted array
– the region start…stop (inclusively) to be searched
– the key to be found
Output: returns the index at which the key has been found, or returns -1 if the key is not in array[start…stop].
Example: Does the following sorted array A contains the number 6?
A=
Call: binarySearch(A, 0, 7, 6)
1
1
3
5
6
7
9
9
Binary search example
Search [0:7]
5 < 6 Þ look into right half of the array
Search [4:7]
7 > 6 Þ look into left half of the array
1
1
3
5
6
7
9
9
1
1
3
5
6
7
9
9
1
1
3
5
6
7
9
9
Search [4:4]
6 is found. Return 4 (index)
Binary Search Algorithm
int bsearch(int[] A, int i, int j, int x) { if (i<=j) { // the region to search is non-empty
int e = ⎣(i+j)/2⎦; if (A[e] > x) {
return bsearch(A,i,e-1,x);
} else if (A[e] < x) {
return bsearch(A,e+1,j,x);
} else {
return e; }
} else { return -1; } // value not found }
Fibonacci numbers
Fib0 = 0 base case
Fib1 = 1 base case
Fibn = Fibn-1 + Fibn-2 for n > 1 recursive case
i
0
1
2
3
4
5
6
7
Fibi
0
1
1
2
3
5
8
13
Recursive algorithm Compute Fibonacci number n (for n ≥ 0)
public static int Fib(int n) {
if (n <= 1) { Can handle both
}
return n; base cases together }
// {n > 1}
return Fib(n-1) + Fib(n-2); Recursive case
(2 recursive calls)
Note: The algorithm follows almost exactly the definition of Fibonacci numbers.
Recursion is not always efficient!
Note: This is a recursion tree
Fib(4)
Fib(3)
Fib(5)
Fib(2)
Fib(3)
Fib(2) Fib(1)
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(1)
Fib(1) Fib(0)
Fib(0)
Question: When computing Fib(n), how many times are Fib(0) or Fib(1) called?
• •
•
Designing recursive algorithms To write a recursive algorithm:
– Find how the problem can be broken up in one or more smaller problems of the same nature
– Remember the base case!
Naive implementation of recursive algorithms may lead
to prohibitive running time.
– Naive Fibonacci Þ O(𝜙n) operations
– Better Fibonacci Þ O(log n) operations
Usually, better running times are obtained when the size of the sub-problems are approximately equal.
– power(a,n) = a * power(a,n-1) Þ O(n) operations
– power(a,n) = (power(a,n/2))2 Þ O(log n) operations
Sorting problem
Problem: Given a list of n elements from a totally ordered universe, rearrange them in ascending order.
Classical problem in computer science with many different algorithms (bubble sort, merge sort, quick sort, etc.)
Insertion sort
6
3
1
5
2
4
6
3
1
5
2
4
3
6
1
5
2
4
1
3
6
5
2
4
1
3
5
6
2
4
1
2
3
5
6
4
1
2
3
4
5
6
Insertion sort
1
3
5
6
2
4
n elements New element
already sorted
to sort
1
2
3
5
6
4
n+1 elements sorted
Insertion sort
Fori ← 1tolength(A)-1 j←i
while j > 0 and A[j-1] > A[j] swap A[j] and A[j-1] j←j-1
end while
end for
• Iterative method to sort objects.
• Relatively slow, we can do better using a recursive approach!
Merge Sort
Sort using a divide-and-conquer approach:
• Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each.
• Conquer: Sort the two subsequences recursively using merge sort.
• Combine: Merge the two sorted subsequences to produce the sorted answer.
Merge Sort – Example
4
3
2
1
Divide
4
3
2
1
4
3
2
1
3
4
1
2
Merge
1
2
3
4
Merge sort (principle)
• Unsorted array A with n elements
• Split A in half ® 2 arrays L and R with n/2 elements
• SortLandR
• Merge the two sorted arrays L and R
Base case: Stop the recursion when the array is of size 1. Why? Because the array is already sorted!
Recursive case
Merge-Sort (A, p, r)
INPUT: a sequence of n numbers stored in array A OUTPUT: an ordered sequence of n numbers
MergeSort (A, p, r) // sort A[p..r] by divide & conquer
1 2 3 4 5
ifp
} elif (A[e] < x) { return bsearch(A,e+1,j,x); } else { return e; }
} else { return -1; } // value not found }
𝑇𝑛=' 𝑛𝑐 𝑖𝑓𝑛=1 𝑇 2 +𝑐′ 𝑖𝑓𝑛>1
Notes:
• n is the size of the array
• Formally, we should use ≤ rather than =
Example (naïve Fibonacci)
public static int Fib(int n) {
if (n <= 1) { return n; }
return Fib(n-1) + Fib(n-2);
}
𝑇𝑛 =1 𝑐 𝑖𝑓𝑛≤1 𝑇 𝑛−1 +𝑇 𝑛−2 +𝑐′ 𝑖𝑓𝑛>1
What are the value of c and c’ ?
• If 𝑛 ≤ 1 there is only one comparison thus c=1
• If 𝑛 > 1 there is one comparison and one addition thus c’=2
Notes:
• we neglect other constants
• We can approximate c and c’ with an asymptotic notation O(1)
Example (Merge sort)
MergeSort (A, p, r) if (p < r) then
q ¬ ë(p+r)/2û MergeSort (A, p, q) MergeSort (A, q+1, r) Merge (A, p, q, r)
• Base case: constant time c
• Divide: computing the middle takes constant time c’
• Conquer: solving 2 subproblems takes 2・T(n/2)
• Combine: merging n elements takes k · n
𝑐 𝑖𝑓 𝑛 = 1 𝑇 𝑛 ='23𝑇 /0 +𝑘3𝑛+𝑐+𝑐′ 𝑖𝑓𝑛>1
Substitution method
How to solve a recursive equation?
1. Guess the solution.
2. Use induction to find the constants and show that the
solution works.
Example:
𝑇𝑛 =1 1 𝑖𝑓𝑛=0 23𝑇(𝑛−1) 𝑖𝑓𝑛>0
Guess: 𝑇 𝑛 = 2/
Basecase:𝑇 0 =21 =1✓
Inductive case: /
Assume 𝑇 𝑛 = 2 until rank n-1, then show it is true at rank n. 𝑇𝑛 =23𝑇𝑛−1 =232/23=2/✓
Running time of binary search
0 𝑖𝑓 𝑛 = 1 𝑇 𝑛 = ‘ 𝑇 𝑛2 + 1 𝑖 𝑓 𝑛 > 1
Note: set the constant c=0 and c’=1
Guess: 𝑇 𝑛 = log0 𝑛
Basecase:𝑇 1 =log01=0✓ Inductive case:
Assume 𝑇 𝑛⁄2 = log0(𝑛⁄2)
𝑇 𝑛 = 𝑇 𝑛⁄2 + 1 = log0 𝑛⁄2 + 1
=log0 𝑛 −log02+1=log0𝑛✓
Induction hypothesis canbeanything