05_Recursion
Lecture 5
Recursion
EECS 281: Data Structures & Algorithms
1
Introduction to Recursion
Data Structures & Algorithms
Recursion Basics
• A recursive function calls itself to
accomplish its task
• At least one base case is required
• At least one recursive case is required
• Each subsequent call has simpler
(smaller) input
• Single recursion can be used on lists
• Multiple recursion can be used on trees
3
Job Interview Question
• Implement this function
// returns x^n
int power(int x, uint32_t n);
• The obvious solution uses n – 1 multiplications
– 28 = 2*2* … *2
• Less obvious: O(log n) multiplications
– Hint: 28 = ((22)2)2
– How does it work for 27 ?
• Write both solutions iteratively and recursively
4
Ideas
• Obvious approach uses a subproblem “one step smaller”
• Less obvious approach splits the problem into two halves
5
𝑥! = #
1
𝑥 ⁄! # ∗ 𝑥 ⁄! #
𝑥 ∗ 𝑥 ⁄! # ∗ 𝑥 ⁄! #
𝑛 == 0
𝑛 > 0, even
𝑛 > 0, odd
𝑥! = / 1
𝑥 ∗ 𝑥!$%
𝑛 == 0
𝑛 > 0
Two Recursive Solutions
Solution #1
1 int power(int x, uint32_t n) {
2 if (n == 0)
3 return 1;
4
5 return x * power(x, n – 1);
6 } // power()
Solution #2
1 int power(int x, uint32_t n) {
2 if (n == 0)
3 return 1;
4
5 int result = power(x, n / 2);
6 result *= result;
7 if (n % 2 != 0) // n is odd
8 result *= x;
9
10 return result;
11 } // power()
Recurrence: T(n) = T(n-1) + c
Complexity: Θ(n)
Recurrence: T(n) = T(n / 2) + c
Complexity: Θ(log n) 6
Introduction to Recursion
Data Structures & Algorithms
Tail Recursion
Data Structures & Algorithms
Tail Recursion
• When a function is called, it gets a stack frame, which
stores the local variables
• A simply recursive function generates a stack frame for
each recursive call
• A function is tail recursive if there is
no pending computation at each
recursive step
– “Reuse” the stack frame rather
than create a new one
• Tail recursion and iteration are
equivalent
http://xkcd.com/1270/ 9
http://xkcd.com/1270/
Shuo
Recursion and the Stack
1 int factorial(int n) {
2 if (n == 0)
3 return 1;
4 return n * factorial(n – 1);
5 } // factorial()
6
7 int main(int, char *[]) {
8 factorial(5);
9 } // main()
10
The Program Stack (1)
• When a function call is made
1a. All local variables are saved in a special storage
called the program stack
2a. Then argument values are
pushed onto the program stack
• When a function call is received
2b. Function arguments are popped off the stack
• When return is issued within a function
3a. The return value is pushed onto the program stack
• When return is received at the call site
3b. The return value is popped off the the program stack
1b. Saved local variables are restored
11
The Program Stack (2)
• Program stack supports nested function calls
– Six nested calls = six sets of local variables
• There is only one program stack (per thread)
– NOT the program heap, (where dynamic memory is allocated)
• Program stack size is limited
– The number of nested function calls is limited
• Example: a bottomless (buggy) recursion function will
exhaust program stack very quickly
12
Recursion vs. Tail Recursion
Recursive
1 int factorial(int n) {
2 if (n == 0)
3 return 1;
4 return n * factorial(n – 1);
5 } // factorial()
Tail recursive*
6 int factorial(int n, int res = 1) {
7 if (n == 0)
8 return res;
9 return factorial(n – 1, res * n);
10 } // factorial()
Θ(n) time complexity
Θ(n) space complexity
(uses n stack frames)
Θ(n) time complexity
Θ(1) space complexity
(reuses 1 stack frame)
*The default argument is used to seed the res parameter. Alternatively, the
“helper function” pattern could be used.
13
Logarithmic Tail Recursive power()
1 int power(int x, uint32_t n, int result = 1) {
2 if (n == 0)
3 return result;
4 else if (n % 2 == 0) // even
5 return power(x * x, n / 2, result);
6 else // odd
7 return power(x * x, n / 2, result * x);
8 } // power()
14
Θ(log n) time complexity
Θ(1) space complexity
Practical Considerations
• Program stack is limited in size
– It’s actually pretty easy to exhaust this!
e.g. Computing the length of a very long vector using a
“linear recursive” function with Θ(n) space complexity
• For a large data set
– ”Simple” recursion is a bad idea
– Use tail recursion or iterative algorithms instead
• This doesn’t mean everything should be tail recursive
– Some problems can’t be solved in Θ(1) space!
15
Tail Recursion
Data Structures & Algorithms
Recurrence Relations
Data Structures & Algorithms
Recurrence Relations
• A recurrence relation describes the way a problem
depends on a subproblem.
– A recurrence can be written for a computation:
– A recurrence can be written for the time taken:
– A recurrence can be written for the amount of memory used*:
*Non-tail recursive
18
𝑇 𝑛 = $
𝑐!
𝑇 𝑛 − 1 + 𝑐”
𝑛 == 0
𝑛 > 0
𝑥# = $ 1
𝑥 ∗ 𝑥#$”
𝑛 == 0
𝑛 > 0
𝑀 𝑛 = $
𝑐!
𝑀 𝑛 − 1 + 𝑐”
𝑛 == 0
𝑛 > 0
A Logarithmic Recurrence Relation
• Fits the logarithmic recursive implementation of
power()
– The power to be calculated is divided into two halves
and combined with a single multiplication
• Also fits Binary Search
– The search space is cut in half each time, and the
function recurses into only one half
à
19
Θ(log 𝑛)𝑇 𝑛 = #
𝑐&
𝑇
𝑛
2
+ 𝑐%
𝑛 == 0
𝑛 > 0
Common Recurrences
Recurrence Example Big-O
Solution
T(n) = T(n / 2) + c Binary Search O(log n)
T(n) = T(n – 1) + c Linear Search O(n)
T(n) = 2T(n / 2) + c Tree Traversal O(n)
T(n) = T(n – 1) + c1 * n + c2 Selection/etc. Sorts O(n2)
T(n) = 2T(n / 2) + c1 * n + c2 Merge/Quick Sorts O(n log n)
20
Solving Recurrences
• Substitution method
1. Write out T(n), T(n – 1), T(n – 2)
2. Substitute T(n – 1), T(n – 2) into T(n)
3. Look for a pattern
4. Use a summation formula
• Another way to solve recurrence equations
is the Master Method (AKA Master
Theorem)
• Recursion tree method
21
Shuo
Recurrence Thought Exercises
• What if a recurrence cuts a problem into two
subproblems, and both subproblems were
recursively processed?
• What if a recurrence cuts a problem into three
subproblems and…
– Processes one piece
– Processes two pieces
– Processes three pieces
• What if there was additional, non-constant work
after the recursion?
22
Recurrence Relations
Data Structures & Algorithms
The Master Theorem
Data Structures & Algorithms
Master Theorem
25
Let T(n) be a monotonically increasing function
that satisfies:
where a ≥ 1, b > 1. If 𝑓 𝑛 ∈ Θ 𝑛% , then:
𝑇 𝑛 = 𝑎𝑇
𝑛
𝑏
+ 𝑓(𝑛)
𝑇 1 = 𝑐& 𝑜𝑟 𝑇 0 = 𝑐&
𝑇 𝑛 ∈ 1
Θ 𝑛&'(‘ ) 𝑖𝑓 𝑎 > 𝑏%
Θ 𝑛% log 𝑛 𝑖𝑓 𝑎 = 𝑏%
Θ 𝑛% 𝑖𝑓 𝑎 < 𝑏%
Exercise 1
𝑇 𝑛 = 3𝑇
𝑛
2
+
3
4
𝑛 + 1
What are the parameters?
a =
b =
c =
Which condition?
26
𝑇 𝑛 = 𝑎𝑇
𝑛
𝑏
+ 𝑓(𝑛)
𝑓 𝑛 ∈ Θ 𝑛(
𝑇 𝑛 ∈ =
Θ 𝑛)*+! , 𝑖𝑓 𝑎 > 𝑏(
Θ 𝑛( log 𝑛 𝑖𝑓 𝑎 = 𝑏(
Θ 𝑛( 𝑖𝑓 𝑎 < 𝑏( 3 2 1 Exercise 2 𝑇 𝑛 = 2𝑇 𝑛 4 + 𝑛 + 7 What are the parameters? a = b = c = Which condition? 28 2 4 1/2 𝑇 𝑛 = 𝑎𝑇 𝑛 𝑏 + 𝑓(𝑛) 𝑓 𝑛 ∈ Θ 𝑛( 𝑇 𝑛 ∈ = Θ 𝑛)*+! , 𝑖𝑓 𝑎 > 𝑏(
Θ 𝑛( log 𝑛 𝑖𝑓 𝑎 = 𝑏(
Θ 𝑛( 𝑖𝑓 𝑎 < 𝑏( Exercise 3 𝑇 𝑛 = 𝑇 𝑛 2 + 1 2 𝑛! + 𝑛 What are the parameters? a = b = c = Which condition? 30 1 2 2 𝑇 𝑛 = 𝑎𝑇 𝑛 𝑏 + 𝑓(𝑛) 𝑓 𝑛 ∈ Θ 𝑛( 𝑇 𝑛 ∈ = Θ 𝑛)*+! , 𝑖𝑓 𝑎 > 𝑏(
Θ 𝑛( log 𝑛 𝑖𝑓 𝑎 = 𝑏(
Θ 𝑛( 𝑖𝑓 𝑎 < 𝑏( When Not to Use • You cannot use the Master Theorem if: – T(n) is not monotonic, such as T(n) = sin(n) – f(n) is not a polynomial, i.e. f(n) = 2n – b cannot be expressed as a constant. i.e. • There is also a special fourth condition if f(n) is not a polynomial; see later in slides 32 𝑇 𝑛 = 𝑇 sin 𝑛 When Not to Use The recursion does not involve division: 𝑇 𝑛 = 𝑇 𝑛 − 1 + 𝑛 Master Theorem not applicable 𝑇 𝑛 ≠ 𝑎𝑇 𝑛 𝑏 + 𝑓(𝑛) 33 Fourth Condition • There is a 4th condition that allows polylogarithmic functions • This condition is fairly limited, • No need to memorize/write down 34 )log()(Then ,0 somefor )log()( If 1log log nnnT knnnf ka ka b b +QÎ ³QÎ Fourth Condition Example • Given the following recurrence: 𝑇 𝑛 = 2𝑇 𝑛 2 + 𝑛 log 𝑛 • Clearly a=2, b=2, but f(n) is not polynomial • However: 𝑓 𝑛 ∈ Θ 𝑛 log 𝑛 and 𝑘 = 1 𝑇 𝑛 = Θ 𝑛 logB 𝑛 If 𝑓(𝑛) ∈ Θ 𝑛)*+! ,log-𝑛 for some 𝑘 ≥ 0, Then 𝑇(𝑛) ∈ Θ 𝑛)*+! ,log-.%𝑛 35 Bonus: Binary Max? • A friend of yours claims to have discovered a (revolutionary!) new algorithm for finding the maximum element in an unsorted array: 1. Split the array into two halves. 2. Recursively find the maximum in each half. 3. Whichever half-max is bigger is the overall max! • Your friend says this algorithm leverages the power of "binary partitioning" to achieve better than linear time. – This sounds too good to be true. Give an intuitive argument why. – Use the master theorem to formally prove this algorithm is Θ(n). 36 The Master Theorem Data Structures & Algorithms 2D Table Search Data Structures & Algorithms Job Interview Question Write an efficient algorithm that searches for a value in an n x m table (two-dim array). This table is sorted along the rows and columns — that is, table[i][j] ≤ table[i][j + 1], table[i][j] ≤ table[i + 1][j] • Obvious ideas: linear or binary search in every row – nm or n log m … too slow 39 1 4 7 11 15 2 5 8 12 19 3 6 9 16 22 10 13 14 17 24 18 21 23 26 30 1 4 7 11 15 2 5 8 12 19 3 6 9 16 22 10 13 14 17 24 18 21 23 26 30 Potential Solution #1: Quad Partition • Split the region into four quadrants, eliminate one. • Then, recursively process the other 3 quadrants. • Write a recurrence relation for the time complexity in terms of n, the length of one side: 40 T(n) = 3T(n/2) + c Why n/2 and not n/4 if it's a quadrant? Remember, n is the length of one side! n 1 4 7 11 15 2 5 8 12 19 3 6 9 16 22 10 13 14 17 24 18 21 23 26 30 Potential Solution #2: Binary Partition • Split the region into four quadrants. • Scan down the middle column, until you find "where the value should be" if it were in that column.1 • This allows you to eliminate two quadrants. (Why? Which ones?) • Recursively process the other two. • Write a recurrence relation, again in terms of the side length n: 41 1 Of course, you might get lucky and find the value here! n T(n) = 2T(n/2) + cn How can we improve this? Use binary search! Potential Solution #3: Improved Binary Partition • Split the region into four quadrants. • Scan down the middle column, until you find "where the value should be" if it were in that column.1 • This allows you to eliminate two quadrants. (Why? Which ones?) • Recursively process the other two. • Write a recurrence relation, again in terms of the side length n: 42 1 Of course, you might get lucky and find the value here! T(n) = 2T(n/2) + c log n 1 4 7 11 15 2 5 8 12 19 3 6 9 16 22 10 13 14 17 24 18 21 23 26 30 n Exercise: Use the Master Theorem • Use the master theorem to find the complexity of each approach: • Quad Partition: • Binary Partition: • Improved Binary Partition: 43 T(n) = 2T(n/2) + cn T(n) = Q(n log n) T(n) = 3T(n/2) + c T(n) = Q(nlog23) ≈ Q(n1.58) T(n) = 2T(n/2) + c log n T(n) = Q(n) 1 bool stepWise(int mat[][n], int m, int target, int &row, int &col) { 2 if (target < mat[0][0] || target > mat[m – 1][n – 1])
3 return false;
4 row = 0; col = n – 1;
5 while (row <= m - 1 && col >= 0) {
6 if (mat[row][col] < target) 7 ++row; 8 else if (mat[row][col] > target)
9 –col;
10 else
11 return true;
12 } // while
13 return false;
14 } // stepWise()
Another Solution!
Stepwise Linear Search
44
1 4 7 11 15
2 5 8 12 19
3 6 9 16 22
10 13 14 17 24
18 21 23 26 30
n
m
Runtime Comparisons
• Source code and data (M = N = 100) available at
http://www.leetcode.com/2010/10/searching-2d-sorted-matrix.html
http://www.leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html
http://www.leetcode.com/2010/10/searching-2d-sorted-matrix-part-iii.html
• Runtime for 1,000,000 searches
Algorithm Runtime
Binary search 31.62s
Diagonal Binary Search 32.46s
Step-wise Linear Search 10.71s
Quad Partition 17.33s
Binary Partition 10.93s
Improved Binary Partition 6.56s
45
http://www.leetcode.com/2010/10/searching-2d-sorted-matrix-part-iii.html
http://www.leetcode.com/2010/10/searching-2d-sorted-matrix-part-iii.html
http://www.leetcode.com/2010/10/searching-2d-sorted-matrix-part-iii.html
2D Table Search
Data Structures & Algorithms
Questions for Self-Study
• Consider a recursive function that only calls itself.
Explain how one can replace recursion
by a loop and an additional stack.
• Go over the Master Theorem in the CLRS textbook
• Which cases of the Master Theorem were exercised for
different solutions in the 2D-sorted-matrix problem?
• Solve the same recurrences by
substitution w/o the Master Theorem
• Write (and test) programs for each
solution idea, time them on your data
47