Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
III. tail recursion (SICP 1.2, The Little Schemer 5-7) A. motivation ------------- FIBONACCI NUMBERS Each pair of rabbits has 2 kids. Mate every month Bear young 2 months after birth # of pairs of rabbits: 1 ; end of month 1 1 ; end of month 2 2 = 1 + 1 ; month 3 3 = 1 + 2 ; month 4 5 = 2 + 3 ; month 5 8 = 3 + 5 ; month 6 13 = 5 + 8 ; month 7 ------------- How many at the end of month 8? ------------------------------------------ FULLY RECURSIVE VERSION (define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))) ------------------------------------------ B. definition ------------------------------------------ FULL vs. TAIL RECURSION def: a procedure is tail recursive if full recursion trace: (list-sum '(3 5 7)) = (+ 3 (list-sum '(5 7))) = (+ 3 (+ 5 (list-sum '(7)))) = (+ 3 (+ 5 (+ 7 (list-sum '())))) = (+ 3 (+ 5 (+ 7 0))) = (+ 3 (+ 5 7)) = (+ 3 12) = 15 tail recursion trace: (list-sum '(3 5 7)) = (list-sum-iter '(3 5 7) 0) = (list-sum-iter '(5 7) 3) = (list-sum-iter '(7) 8) = (list-sum-iter '() 15) = 15 ------------------------------------------ Which of these is more like a while loop? ------------------------------------------ FULL vs. TAIL RECURSION (define list-sum ; fully recursive (lambda (lon) (if (null? lon) 0 (+ (car lon) (list-sum (cdr lon)))))) (define list-sum ; tail recursive (lambda (lon) ------------------------------------------ ------------------------------------------ TAIL RECURSIVE VERSION OF FIB How would we design fib to be tail recursive? ------------------------------------------ ------------------------------------------ FOR YOU TO DO (IN PAIRS) Write a tail-recursive procedure for: (reverse '()) ==> () (reverse '(a b c)) ==> (c b a) (reverse '(x y z h)) ==> (h z y x) ------------------------------------------ do our questions still work? C. When to use tail recursion ------------------------------------------ WHEN TO USE TAIL RECURSION 1. When working with vectors or strings (deftype vector-sum (-> ((vector-of number)) number)) (define vector-sum (lambda (von) (partial-vector-sum von (vector-length von) 0))) (deftype partial-vector-sum (-> ((vector-of number) number number) number))) (define partial-vector-sum (lambda (von n acc) (if (zero? n) (partial-vector-sum von (- n 1) (+ (vector-ref von (- n 1)) acc))))) ------------------------------------------ ------------------------------------------ WHEN TO USE TAIL RECURSION 2. To return directly to caller (since no pending computations) (define list-product (lambda (lon) (prod-iter lon 1))) (define prod-iter (lambda (lon acc) (if (null? lon) acc (if (zero? (car lon)) 0 (prod-iter (cdr lon) (* acc (car lon))))))) ------------------------------------------ D. correspondence to loops What in C/C++ is like a tail recursion? ------------------------------------------ CORRESPONDENCE TO WHILE LOOP struct Cons {int car; Cons *cdr}; // C++ int list_product(Cons *lon) { int acc = 1; while (!(lon == NULL)) { if (lon->car == 0) { return 0; } else { acc = acc * lon->car; lon = lon->cdr; } } return acc; } (define list-product ; Scheme (lambda (lon) (prod-iter lon 1))) (define prod-iter (lambda (lon acc) (if (null? lon) acc (if (zero? (car lon)) 0 (prod-iter (cdr lon) (* acc (car lon))))))) ------------------------------------------ E. when to use an accumulator ------------------------------------------ WHEN YOU NEED AN ACCUMULATOR When working with vectors, strings (define vector-sum (lambda (von) (partial-vector-sum von (vector-length von)))) (define partial-vector-sum (lambda (von n) (if (zero? n) 0 (+ (vector-ref von (- n 1)) (partial-vector-sum von (- n 1)))))) ------------------------------------------ F. summary What are the key ideas for designing tail recursion? When should you use tail recursion? When shouldn't you use tail recursion? How do you design a fully recursive program? What are the questions to ask? ;;;---------------------------------------------------------------------- ;;; vector-product-mod.scm ;;; ;;; Follow the instructions for HW 1, problem 4 to add this module to your ;;; lib342 directory. (module vector-product-mod mzscheme (provide vector-product) ;;; Examples: ;;; (vector-product '#(1 2 3 4)) ==> 24 ;;; (vector-product '#(2 3 2 4)) ==> 48 ;;; (vector-product '#(2 3 2 4 0 888 999)) ==> 0 ;;; (vector-product '#()) ==> 1 (define vector-product (lambda (von) ;; ENSURES: Result is the product of the elements in von (vector-product-iter von (- (vector-length von) 1) 1))) ;;; Design: von n acc ;;; (vector-product-iter '#(1 2 3 4) 3 1) ;;; = (vector-product-iter '#(1 2 3 4) 2 4) ;;; = (vector-product-iter '#(1 2 3 4) 1 12) ;;; = (vector-product-iter '#(1 2 3 4) 0 24) ;;; = (vector-product-iter '#(1 2 3 4) -1 24) ;;; = 24 ;;; ;;; (vector-product-iter '#(1 3 0 4) 3 1) ;;; = (vector-product-iter '#(1 3 0 4) 2 4) ;;; = 0 (define vector-product-iter (lambda (von n acc) ;; REQUIRES: (< n (vector-length n)) ;; ENSURES: Result is the product of acc and the elements in von whose ;; index is less than or equal to n. (if (negative? n) acc (let ((elem (vector-ref von n))) (if (zero? elem) 0 (vector-product-iter von (- n 1) (* elem acc))))))) ) ; end module ;;;---------------------------------------------------------------------- ;;;---------------------------------------------------------------------- ;;; fib-mod.scm ;;; ;;; Follow the instructions for HW 1, problem 4 to add this module to your ;;; lib342 directory. (module fib-mod mzscheme (provide fib fib-iter) (define fib (lambda (n) (if (zero? n) 0 (fib-iter n 0 1)))) (define fib-iter (lambda (n prev last) (if (< n 2) last (fib-iter (- n 1) last (+ prev last))))) ) ) ; end module ;;;---------------------------------------------------------------------- ;;;---------------------------------------------------------------------- ;;; fact-mod.scm ;;; ;;; Follow the instructions for HW 1, problem 4 to add this module to your ;;; lib342 directory. (module fact-mod mzscheme (provide fact) ;;;(fact 5) = 120 ;;;(fact 4) = 24 ;;;(fact 3) = 6 ;;;(fact 0) = 1 (define fact (lambda (n) (if (zero? n) 1 (* n (fact (sub1 n)))))) (define sub1 (lambda (n) (- n 1))) ) ; end module ;;;----------------------------------------------------------------------