- f( A, first, last ) — process A[first..last]
- e.g., add up all elements in 1D array A
- Recursion:
- Adding all elements in 1-element array requires returning element
- Adding all elements in n-element array requires first element
+ sum of elements in positions 2 through end
add( A, first, last ) if last = first return A[first] else return A[first] + add( A, first+1, last )
- Recursion:
- Section 4.1
- Divide-and-conquer structure
- Ways to prove correct and analyze
- Recurrences
- Substitution
- Recursion tree
- Master method
- Ignorable (for asymptotic results) technicalities re subproblem sizes
- Examples
- Famous recurrence
- F(0) = 1,
- F(1) = 1,
- F(n) = F(n-1) + F(n-2), n > 1
- Recurrence for execution time of recursive factorial
factorial( n ) if n = 0 return 1 else return n * factorial( n-1 )- T(0) = 1
- T(n) = 1 + T(n-1), n > 0
- Closed form:
- T(n) = 1 + T(n-1) (using substitution method)
- = 1 + 1 + T(n-2)
- = 1 + 1 + 1 + T(n-3)
- …
- = n + 1?
- Proof by induction on n
- Base case: n = 0, T(0) = 1 = n + 1
- Induction: assume T(k) = k+1, k ≥ 0
- Show T(k+1) = k+2
- T(k+1) = 1 + T(k) (definition)
- = 1 + (k+1) (induction)
- = k + 2
- Final result: execution time = Θ(n)
- Sum-of-array-elements algorithm
- n = length of subarray A[first..last] = last - first + 1
- Recurrence:
- T(1) = 1
- T(n) = 1 + T(n-1), n > 1
- T(n) = n?
- Proof (induction on n)
- Base case: n = 1, T(1) = 1 = n
- Assume T(k) = k, k ≥ 1
- T(k+1) = 1 + T(k) = 1 + k
- Recurrence for the maximum number of nodes in a binary tree as
a function of height
- Famous recurrence
- More practice with recurrences (fast multiplication, n logn from book)
- Mini-assignment: verify closed form for N(h) for binary tree