recitation 3: substitution model, recursion

-----------------------------------------------------
* do one thing at a time
* take small steps
* sometimes we have a choice of what to evaluate next

(if (= (+ 5 2) 7) (* (+ 2 3) 5) (/ 4 (- 7 5)))
(if (= 7       7) (* (+ 2 3) 5) (/ 4 (- 7 5)))
(if #t            (* (+ 2 3) 5) (/ 4 (- 7 5)))
(if #t            (* 5       5) (/ 4 (- 7 5)))
(if #t            25            (/ 4 (- 7 5)))
25

-----------------------------------------------------
recursive vs iterative

from webster:
  recur: to come up again for consideration
  recursion: something that calls itself
  iterate: repeating, each time getting closer to the desired result

what makes a procedure recursive?  
  * it calls itself (possibly indirectly)

what makes a process recursive? 
  * deferred operations

-----------------------------------------------------
How to design recursive algorithms

* wishful thinking
* decompose the problem
* identify the simple/smallest parts (modular programming)

  (define (odd? x)
    (not (even? x)))

  (define (even? x)
    (not (odd? x)))
 
  (define (even? x)
    (if (= x 0) 1 (odd? (- x 1))))

* assumptions
* test/predicate for base case (termination of recursive unwinding)
* recursive call

  (define (fact n)
     (* n (fact (- n 1))))
 
  (define (fact n)
     (if (= n 1) 
         1
         (* n (fact (- n 1)))))
 
-----------------------------------------------------

what is "recursive recursion"?
  * the width of the expression (substitution model) keeps growing
  * deferred operations

what is "iterative recursion"?
  * constant space
  * no pending/deferred operations

why do we like recursive procedures?
  * many problems are easy to think about as loops

why do some programming guides discourage writing recursive programs?
  * limited stack depth
  * limited memory
  * encourage the use of for loops

-----------------------------------------------------
recipe for making recursive procedures iterative

  * what can we use as our partial answer 
    - can we "accumulate" something?
  * how do we keep track of what's left to do
    - some sort of counter (count up, count down?)
  * how do we update these variables 
    - the partial answer & counter
  * what's the base case?
  * write out a table
    - fixed size (# of variables) becaues there are no pending operations
  * almost always we will write a helper procedure that is
    the recursive part because we have extra variables to
    keep track of!

-----------------------------------------------------
from last time:   We encode an order as multi-digit number where each
digit represents a combo. For example, the order 327 represents a
Triple, Double, and biggie-sized Triple.  (biggie-size = regular+4)

(define order-price
  (lambda (order)
    (if (= order 0)
	0
	(+ (combo-price (remainder order 10))
	   (order-price (quotient order 10))))))

* is this recursive/iterative?  rewrite as the other.

It generates a recursive process.

The iterative version:
(define order-price
  (lambda (order)
    (define helper
      (lambda (subtotal remaining)
	(if (= remaining 0)
	    subtotal
	    (helper (+ subtotal (combo-price (remainder remaining 10)))
		    (quotient remaining 10)))))
    (helper 0 order)))

-----------------------------------------------------
* multiple statements in a define
* scoping
* begin special form (implicit begin inside define, cond, ...)

(define (foo a)
  (begin
    (define b 5)
    (define (foo-helper x) (+ a x))
    (foo-helper b)))

foo => #[procedure]
foo-helper => ERROR, undefined variable
a => ERROR, undefined variable
b => ERROR, undefined variable
(foo 3) => 8
foo-helper => ERROR, undefined variable
a => ERROR, undefined variable
b => ERROR, undefined variable

-----------------------------------------------------
(define (our-display x) (display x) x)
(define (count1 x)
  (if (= x 0) 
      0
      (begin (our-display x)
	     (count1 (- x 1)))))
(define (count2 x)
  (if (= x 0) 
      0
      (begin (count2 (- x 1))
	     (our-display x))))

* evaluated in scheme buffer:

(count1 5) 
54321
;Value: 0

(count2 5)
12345
;Value: 5

* evaluate using the substitution model

(count1 5)
(begin (our-display 5) (count1 4)) <PRINT 5>
(count1 4)
(begin (our-display 4) (count1 3)) <PRINT 4>
(count1 3)
(begin (our-display 3) (count1 2)) <PRINT 3>
(count1 2)
(begin (our-display 2) (count1 1)) <PRINT 2>
(count1 1)
(begin (our-display 1) (count1 0)) <PRINT 1>
(count1 0)
=> 0

(count2 5)
(begin (count2 4) (our-display 5))
(begin (begin (count2 3) (our-display 4)) (our-display 5))
(begin (begin (begin (count2 2) (our-display 3)) (our-display 4)) (our-display 5))
(begin (begin (begin (begin (count2 1) (our-display 2)) (our-display 3)) (our-display 4)) (our-display 5))
(begin (begin (begin (begin (begin (count2 0) (our-display 1)) (our-display 2)) (our-display 3)) (our-display 4)) (our-display 5))
(begin (begin (begin (begin (our-display 1) (our-display 2)) (our-display 3)) (our-display 4)) (our-display 5)) <PRINT 1>
(begin (begin (begin (our-display 2) (our-display 3)) (our-display 4)) (our-display 5)) <PRINT 2>
(begin (begin (our-display 3) (our-display 4)) (our-display 5)) <PRINT 3>
(begin (our-display 4) (our-display 5)) <PRINT 4>
(our-display 5) <PRINT 5>
=> 5