(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)

(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

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

(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))))

Which is more like C or Java?

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