## Tutorial 12: Working with unknown functions (November 28-30, 2007)Today's tutorial (the last one!) covers accumulative recursion (lecture module 12). We'll be using accumulators to achieve tail recursion, which allows us to write some functions more naturally and more efficiently. You might want to think about what the invariant is for each of the accumulative functions we ask for below, and how you could use it to justify the correctness of the function. - ... And you thought you were done with foldr
- Monotone increasing divergent functions
- Inverse floor function
- Anything bigger
- Inverse floor revisited
The foldr-nat: (num num -> num) num nat -> num (foldr-nat f base n) => (f n (f (- n 1) (f (- n 2) ... (f 1 base)))) So, for example, we could compute the factorial of a number (define (foldr-nat1 f base n) (cond [(= n 1) (f 1 base)] [else (f n (foldr-nat1 f base (sub1 n)))])) Now write a version of These questions deal with functions which are strictly increasing for all If By simply adding 1 to the result of We saw a few weeks ago how to use the binary search algorithm to quickly search for a number in a binary search tree. This same idea can be used to search over a finite interval of the natural numbers. The idea is, given a lower and an upper bound on the result, to test some value in the middle (roughly), and use this to reduce the size of the search interval by one half (roughly). Use this notion of a binary search on the natural numbers, along with your function |

This file generated Monday, December 17th, 2007 using PLT Scheme and WebIt!