Recursion and Tail Recursion

10.1 Linear Recursion

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

(define (sum-list lst)
  (if (null? lst)
      0
      (+ (car lst) (sum-list (cdr lst)))))

(define (my-length lst)
  (if (null? lst) 0 (+ 1 (my-length (cdr lst)))))

(define (my-append a b)
  (if (null? a) b (cons (car a) (my-append (cdr a) b))))

10.2 Tail Recursion (Iterative Processes)

Linear recursive (factorial) Builds deferred operations Linear iterative (factorial-iter) State in parameters Tree recursive (fib) O(depth) stack, often exponential time

;; A call is in TAIL POSITION if its value is returned directly (nothing left to do afterwards).
;; Scheme guarantees tail calls run in constant stack space.
(define (factorial-iter n)
  (define (iter i acc)
    (if (> i n)
        acc
        (iter (+ i 1) (* acc i))))    ; tail call
  (iter 1 1))

(define (my-reverse lst)
  (let loop ((l lst) (acc '()))
    (if (null? l) acc (loop (cdr l) (cons (car l) acc)))))

(define (count-down n)
  (unless (= n 0) (count-down (- n 1))))
(count-down 10000000)                 ; fine: constant space

10.3 Tree Recursion and Memoization

(define (fib n)
  (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))      ; exponential time

(define (fib-iter n)
  (let loop ((a 0) (b 1) (k n))
    (if (= k 0) a (loop b (+ a b) (- k 1)))))          ; linear time, constant space
(fib-iter 100)                         ; 354224848179261915075

;; Counting change (SICP 1.2.2): a classic tree recursion
(define (count-change amount) (cc amount 5))
(define (cc amount kinds)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds 0)) 0)
        (else (+ (cc amount (- kinds 1))
                 (cc (- amount (first-denomination kinds)) kinds)))))
(define (first-denomination kinds)
  (case kinds ((1) 1) ((2) 5) ((3) 10) ((4) 25) ((5) 50)))
(count-change 100)                     ; 292

10.4 Recursion on Deep Structures

*The Little Schemer*'s Commandments: always ask null? first; recur on the cdr; when building a list, use cons; make sure at least one argument changes and moves toward termination.

(define (flatten x)
  (cond ((null? x) '())
        ((pair? x) (append (flatten (car x)) (flatten (cdr x))))
        (else (list x))))
(flatten '(1 (2 (3 4)) ((5))))         ; (1 2 3 4 5)

(define (deep-reverse x)
  (if (pair? x)
      (reverse (map deep-reverse x))
      x))
(deep-reverse '(1 (2 3) 4))            ; (4 (3 2) 1)