CS116 Chapter 3: Module 3 (Racket/Scheme) - Accumulative Recursion
Document Summary
Understand how to write accumulative recursive functions to build or accumulate a solution. Understand constant, linear, quadratic, and exponential running times. Understand how to analyze basic recursive code to determines its running time. Understand how accumulative recursion may allow for substantial ef ciency gains. Understand how to test accumulative recursive code. Template for code is based on recursive de nition of the data (ex. basic list template) ex. ;; (factorial n) produces the product of the integers from 1 to n. ;; examples: (check-expect (factorial 1) 1) (check-expect (factorial 5) 120) (de ne (factorial n) (cond [(<= n 1) 1] ** all multiplications are done once you reach the end, then it builds back up to the rst element, evaluating along the way. Accumulative recursion ex. (de ne (factorial n) (local [(de ne (running-product n0 prod-so-far) (cond [(<= n0 0) prod-so-far] [else (running-product (sub1 n0) (* prod-so-far n0))]))] (running-product n 1)))
