(define inc (lambda (n) (+ n 1)))
(define dec (lambda (n) (- n 1)))
(define fun (lambda (a b)
(if (= a 0)
(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)
(is-even (- n 2))))
(lambda (a b)
(myst-helper 0 a b)))
(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
-- 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)
-- stacks up work to do: pending computations
-- 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
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
(lambda (a b)
(if (> a b)
(+ a (myst (+ a 1) b)))))
(define (fun a b)
(if (= 0 a)
(fun (dec a) (inc b))))
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