All of the recursion we have done to date is called simple recursion.
We will now learn to use a new pattern of recursion, accumulative recursion, and learn to recognize mutual recursion and generative recursion.
Simple Recursion
Every argument in a recursive function is stepping is either unchanged or one step closer to the base case
Measuring efficiency
| Big-O | Example |
|---|---|
| O(1) | No recursive call |
| O(log(n)) | Binary search |
| O(n) | One recursive application for each item; ex. length |
| O(nlog(n)) | Merge sort |
| O(n^2) | Insertion sort |
| O(2^n) | Fibonacci |
Accumulative recursion
Computationally, we can pass down the largest value seen so far as a parameter called an accumulator.
;; (max-list/acc list max) produces the largest of the maximum element of list and max
(define max-list/acc list max)
(cond
[(empty? list) max]
[(> (first list) max)
(max-list/acc (rest list) (first list))]
[else (max-list/acc (rest list) max)]))
(define (max-list-v3 list)
(max-list/acc (rest list) (first list)))
Tracing
(max-list-v3 (list 1 2 3 9 5))
⇒ (max-list/acc(list 2 3 9 5) 1)
⇒ (max-list/acc(list 3 9 5) 2)
⇒ (max-list/acc(list 9 5) 3)
⇒ (max-list/acc(list 5) 9)