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.