CSC151, Class 42: Tail Recursion Overview: * Two primary kinds of shallow recursion * Example: Sum * Standard design technique for tail recursion * Tail-recursive list generation * Lab (maybe) Notes: * Today's topic continues tomorrow. * What did you think about meeting in Saints' Rest? * Are there questions on the project? ---------------------------------------- If we ignore deep recursion, there are two basic patterns of list recursion First Call procedure recursively Do something with the result. (define sum (lambda (lst) (if (null? lst) 0 (+ (car lst) (sum (cdr lst)))))) Let's watch this in action (sum (list 4 8 7 3)) => (+ 4 (sum (list 8 7 3))) => (+ 4 (+ 8 (sum (list 7 3)))) => (+ 4 (+ 8 (+ 7 (sum (list 3))))) => (+ 4 (+ 8 (+ 7 (+ 3 (sum (list)))))) => (+ 4 (+ 8 (+ 7 (+ 3 0)))) => (+ 4 (+ 8 (+ 7 3))) => (+ 4 (+ 8 10)) => (+ 4 18) => 22 ; Scheme's normal interaction model: ; Read an expression ; Compute its result ; Print the result (define sum (lambda (lst) (letrec ((kernel (lambda (sum-so-far remaining-values) (if (null? remaining-values) sum-so-far (kernel (+ (car remaining-values) sum-so-far) (cdr remaining-values)))))) (kernel 0 lst)))) (sum (list 4 8 7 3)) => (kernel 0 (list 4 8 7 3)) => (kernel 4 (list 8 7 3)) => (kernel 12 (list 7 3)) => (kernel 19 (list 3)) => (kernel 22 (list)) In this second sum, there's a recursive call (to kernel). Once that recursive call finishes, we don't do anything else with it. This second technique is called "tail recursion" It is *usually* more efficient It is also a good candidate for named lets. (define sum (lambda (lst) (let kernel ((sum-so-far 0) (remaining-values lst)) (if (null? remaining-values) sum-so-far (kernel (+ (car remaining-values) sum-so-far) (cdr remaining-values)))))) Observation: Although tail recursion is good and wonderous and much better than violence, there are cases in which it leads to complications. ;;; Procedure: ;;; odds ;;; Parameters: ;;; nums, a list of numbers ;;; Purpose: ;;; Extract all odd numbers in nums and return them ;;; in the same order. ;;; Practica: ;;; > (odds (1 2 3 4 5)) ;;; (1 3 5) (define odds (lambda (lst) (letrec ((kernel (lambda (list-so-far remaining-values) (cond ((null? remaining-values) (reverse list-so-far)) ((odd? (car remaining-values)) (kernel (cons (car remaining-values) list-so-far) (cdr remaining-values))) (else (kernel list-so-far (cdr remaining-values))))))) (kernel null lst)))) ; How do we fix this? ; (1) Reverse at each step; probably won't work. ; (2) Use append at each step. ; (3) Reverse when remaining-values is null.