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.