Generative recursion, Accumulators, Homework hints
Consider the following example function, similar to that from lecture:
(define sum-acc
(lambda (i n acc)
(if (> i n)
acc
(sum-acc (+ 1 i) n (+ acc i))))
(sum-acc 10 50 0) ; = sum of 10,11,...,49,50 = 10+11+...+49+50
(sum-acc 10 10 0) ; = sum of 10 = 10
(sum-acc 10 9 0) ; = sum of = 0
(An aside: why do we use 0 as the initial value of acc?)
As pointed out in class, none of i, n, or acc are getting smaller, unlike the structural recursion we're used to.
But there is something that is getting smaller: the difference between i and n, or more accurately, (n+1)-i. The base case effectively tests if (n+1)-i = 0, assuming that we initially call the function with an i less than or equal to n. We recursively call the function with arguments such that this difference is decreased by one.
What is different than structural recursion is that the difference (n+1)-i is some computed value not explicitly handled by the code.
Here's a version of mergesort similar to those shown in lecture:
(define mergesort
(lambda (data)
(if (has-zero-or-one-elements? data)
data
(merge (mergesort (firsthalf data))
(mergesort (secondhalf data))))))
Clearly the amount of data is decreasing as we recur, and we eventually
get to our base case.
To be more accurate, we have two ways of describing what is decreasing:
Accumulators can be used with either structural or generative recursion. Above, sum-acc uses generative recursion with an accumulator, here, depth-first-search uses structural recursion with an accumulator. Either way, the accumulator represents the current partial solution to the problem.
The following is an example of exhaustive search, looking for a given value in a tree. When the value is in the tree, we return a path from the tree's root to that value. This path is computed using an accumulator.
The following code is also here (Unix path: /home/comp210/public_html/Labs/lab07/example.ss).
(define-structure (tree-empty))
(define-structure (tree-branch value l r))
(define emptytree (make-tree-empty))
(define exampletree
(make-tree-branch
30
(make-tree-branch
20
(make-tree-branch
10
emptytree
emptytree)
emptytree)
(make-tree-branch
15
(make-tree-branch
40
emptytree
(make-tree-branch
14
emptytree
emptytree))
(make-tree-branch
70
(make-tree-branch
8
emptytree
emptytree)
emptytree))))
(define-structure (path-none))
(define-structure (path-empty))
(define-structure (path-some value rest))
(define nopath (make-path-none))
(define emptypath (make-path-empty))
; given: a value, a binary tree, a path so far to get to this tree
; returns: false if the value is not in the tree
; the path to the value if the value is in the tree
(define depth-first-search
(lambda (value tree path)
(cond ((tree-empty? tree)
nopath)
((eq? value (tree-branch-value tree))
(make-path-some (tree-branch-value tree) path))
(else ((lambda (path-l)
(if (path-none? path-l)
(depth-first-search
value
(tree-branch-r tree)
(make-path-some (tree-branch-value tree)
path))
path-l))
(depth-first-search
value
(tree-branch-l tree)
(make-path-some (tree-branch-value tree) path)))))))
(depth-first-search 14 exampletree emptypath)
Step through this example using Donkey, and watch how the path changes. (For convenience, set Donkey's "Stop-At" feature to "Apply".) Try some other examples.
This use of paths is similar to how you'll need to keep track of your solution in the Missionaries & Cannibals homework.
(An aside: Why did we use the expression ...((lambda (path-l) ...) (depth-first-search ...)) ...? We could have written that part of the program as
(if (path-none? (depth-first-search value (tree-branch-l tree) ...))
(depth-first-search value (tree-branch-r tree) ...)
(depth-first-search value (tree-branch-l tree) ...))
instead, but that potentially searches the left branch twice.)
In lab, we will discuss some ideas about what states are for the Missionaries & Cannibals problem. The following are some generalities to consider: