Recitation 4

Lecture Problem #1

(define inc (lambda (n) (+ n 1)))
(define dec (lambda (n) (- n 1)))

(define fun (lambda (a b)
              (if (= a 0)
                  b
                  (inc (fun (dec a) b)))))

Answer: it's addition
To see why, count number of incs: one for each dec of a

This is a recursive procedure that makes a recursive process
-- watch the inc's grow in the stepper
-- the incrementing is pending until the end

What are the elements of a recursive procedure?
-- base case (test and value)
-- recursive call

Think about constructing a recursive solution to a problem by asking
-- what's the solution to a trivial instance of the problem? (base case)
-- if I had a solution, how would I extend it? (recursive case)

Not always easy. What's wrong with this?
(define (is-even n)
  (if (= n 0)
      true
      (is-even (- n 2))))
(is-even 4)
(is-even 3)
 

Lecture Problem #2

(define myst
  (lambda (a b)
    (myst-helper 0 a b)))

(define myst-helper
  (lambda (c a b)
    (if (> a b) c
        (myst-helper (+ c a) (+ a 1) b))))

Answer: it returns sum of ints from a to b inclusive.
To see why, note that it
-- accumulates a, a-1, a-2, etc in c, k times
-- stops when a-k is greater than b

Watch this one in the stepper.
-- nothing growing: no pending computation
 

Today's idea: Iterative vs. Recursive Processes

Recursive procedures
-- procedures that call themselves
-- (or call other procedures that call them back)
-- often a natural way to solve a problem (see lots later with lists and trees)

Recursive process
-- stacks up work to do: pending computations

Iterative process
-- doesn't have pending computations
-- does work as it goes along

Can you spot the difference in structure?
-- recursive call in myst-helper is outermost
-- (well, almost: only contained in an if, which never accumulates work, unlike a combo)
-- iterative procedure has explicit accumulator argument

Iterative procedure expressed in imperative style
c <- 0
while (a <= b)
  c <- c + a
  a <- a + 1
return c

We drew a table to show successive bindings of the arguments a, b, c.

We discussed how Scheme isn't like this
-- variables aren't global or mutated
-- In scheme, no change of variable values
-- In Java or C, value of a, b, c change
-- In Scheme, each execution of myst-helper gets fresh argument variables
-- but helpful anyway?
-- can be useful to start with this, then derive functional code
 

Class Exercise

(define myst
  (lambda (a b)
    (if (> a b)
        0
        (+ a (myst (+ a 1) b)))))

(define (fun a b)
  (if (= 0 a)
      b
      (fun (dec a) (inc b))))

Reflection

Challenge Problem (for another time)
-- Write iter and rec versions of a procedure easy-log that given some power of two, tells you which one it is.
-- Start with rec version, and define problem recursively
-- For iter version, write imperative-style code first