```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

```