Writing recursive functions involves a number of techniques, just as writing loops does. This lecture introduces a number of those techniques. The example are all taken from the exercises in the book.
The first example reinforces the concept of mutually recursive functions and leads us toward accumulator variables and the concepts of tail recursion (in the questions following the example). The second example introduces accumulator variables and tail recursion. The third example covers double recursion. The last example introduces the use of syntax functions for abstracting a data structure (binary trees) and shows us that we might not always recurse on all the possible BNF recursion points in any given execution.
(count-occurrences s slst) counts how many times the symbol s occurs in slst.
The first step is to examine the BNF:
| The BNF for <s-list>, <symbol-expression> |
|---|
|
We expect from the BNF that we'll have two functions, one that counts the symbol in an <s-list> and one that counts the symbol in an <symbol-expression>.
We could do this program using either straight recursion or using tail recursion and an accumulator variable in an auxiliary function. We'll do the former. You might want to try the latter.
We start with the pattern that the BNF for <s-list> suggests:
(define count-occurrences
(lambda (s slst)
(if (null? slst)
... ;; its empty
... ;; its a cons
)
))
Now, we can conclude that a symbol occurs in an empty list 0 times and in non-empty list the number of times it occurs in the car of the list and the number of times it occurs in the cdr of the list:
(define count-occurrences
(lambda (s slst)
(if (null? slst)
0 ;; its empty
(+ (count-occurrences-sym-expr s (car slst)) ;; its a cons
(count-occurrences s (cdr slst)))
)
))
We assume that count-occurrences-sym-expr exists and use it to count the number of occurrences in the car of the list.
Once we define count-occurrences-sym-expr, we're done. The BNF for <symbol-expression> suggests the following pattern:
(define count-occurrences-sym-expr
(lambda (s symexpr)
(if (symbol? symexpr)
... ;; its a symbol
... ;; its an slist
)
))
If the symbol expression is a symbol, then we need to determine whether its the symbol we're counting or not and return the right number (1 or 0). If its an s-list, we already have a procedure defined for counting occurrences:
(define count-occurrences-sym-expr
(lambda (s symexpr)
(if (symbol? symexpr)
(if (eq? s symexpr) 1 0) ;; its a symbol
(count-occurrences s symexpr) ;; its an slist
)
))
Using our procedure:
(count-occurrences 'a '(((a be) a ((si be a) be (a be))) (be g (a si be)))) 5
Rewrite count-occurrences using an accumulator variable
(see the next problem if you don't know what that is). Redo the
substitution model you did in the last problem. What do you notice about
the structure of the recursion?
(flatten slst) returns a list of all the elements in slst in the order of their occurrence. This is the same as the fringe function from Lecture 7. Now, you'll see how to solve the problem without using append.
The BNF for this problem is the same as before. If you try to do this using straight recursion rather than using an accumulator variable in an auxiliary procedure, you'll find this problem to be quite difficult. Using an accumulator variable makes the problem straight forward.
To understand the intuition for the accumulator variable in this problem, think for a moment about how you'd solve this problem in an imperative programming langauge. You'd likely use recursion, since iterating over a structure such as an s-list can be difficult. However, you'd probably find that the easiest way to solve the problem was to build a global list using assignment, adding each member of the s-list as it was encountered.
We'll do the same thing here, except in the spirit of functional programming, we won't use a global variable, we'll use an accumulator in the prameters of the recursive call.
We start defining the auxiliary function using the pattern that the BNF for <s-list> suggests, making sure to add the accumulator variable:
(define flatten-aux
(lambda (slst symbols-so-far)
(if (null? slst)
... ;; its empty
... ;; its a cons
)
))
If the symbol list is empty, we can return the symbols we've found so far. If not, then we recurse, first using flatten-aux to create a list of symbols in the cdr and passing that to the accumulator variable in flatten-sym-expr-aux:
(define flatten-aux
(lambda (slst symbols-so-far)
(if (null? slst)
symbols-so-far ;; its empty
(flatten-sym-expr-aux ;; its a cons
(car slst)
(flatten-aux (cdr slst) symbols-so-far))
)
))
The definition of the function for symbol expressions, follows the, by now,
familiar pattern shown below:
(define flatten-sym-expr-aux
(lambda (sym-expr symbols-so-far)
(if (symbol? sym-expr)
...
...
)
))
If the symbol expression is a symbol, we cons it onto the front of the symbols we have seen so far and return the list. If it is a s-list, we simply call flatten-aux:
(define flatten-sym-expr-aux
(lambda (sym-expr symbols-so-far)
(if (symbol? sym-expr)
(cons sym-expr symbols-so-far)
(flatten-aux sym-expr symbols-so-far)
)
))
The only thing left to do is define the interface function:
(define flatten
(lambda (slst)
(flatten-aux slst '())
))
Of course, we pass the empty list to flatten-aux since when we
just start out we haven't seen any symbols yet.
Why was the list produced by flatten in the correct order? Can you write a version of flatten that returns the fringe of the s-list in reverse order instead? Remember, you want the run time to remain linear and you can't use reverse. Hint: process the car before the cdr.
(merge los1 los2) merges two lists of numbers which are themselves in increasing order. The result is a list in increasing order.
The BNF for a list of numbers is considerably simpler than the s-lists we have been working with:
| The BNF for <list-of-numbers> |
|---|
|
The trick in this problem is to realize that the recursion must take place on both lists simultaneously and therefore, our recursion pattern will be somewhat more complicated than what the BNF would suggest. Still, we can start off, using the BNF to help us define our procedure:
(define merge
(lambda (los1 los2)
(if (null? los1)
...
...
)
))
It doesn't matter, in this problem, which list we test for emptiness first.
Suppose that los1 is null. Then, the merge of los1 and los2 is just los2:
(define merge
(lambda (los1 los2)
(if (null? los1)
los2
...
)
))
If its not empty, then we must see if los2 is empty. If it is, then the merge of it and los1 is simply los1:
(define merge
(lambda (los1 los2)
(if (null? los1)
los2
(if (null? los2)
los1
...
)
)
))
If neither are empty, then we want to merge the two lists. The next element in our merged list is either the car of los1 or the car of los2 since those lists are in order. So, we make a new list from the smallest element from the front of the two lists and what we get when we merge the two list minus that element:
(define merge
(lambda (los1 los2)
(if (null? los1)
los2
(if (null? los2)
los1
(if (< (car los1) (car los2))
(cons (car los1) (merge (cdr los1) los2))
(cons (car los2) (merge los1 (cdr los2)))
)
)
)
))
Using our function, we get:
(merge '(1 4) '(1 2 8)) (1 1 2 4 8)
Use merge to write a sort function for Scheme
lists. Here are a couple of ideas for splitting the list:
Split the list into a the car and the rest of the list. What kind of
sort is this? What is the running time?
Write a function that returns two lists containing all the even and all the odd members of the list respectively. What kind of sort routine is this? What is the running time?
(path n bst) returns a list of directions (either left or right) for finding the number n in a binary search tree of numbers, bst.
The first thing to do is to define the BNF:
| The BNF for <bst> |
|---|
|
So, the following expression:
'(14 (7 () (12 () ()))
(26 (20 (17 () ())
())
(31 () ())))
represents the tree shown in the following diagram:
Before we start, let's define syntax functions for the BNF. These are helper functions that assist us in accessing the structure according to the BNF:
(define empty-tree? (lambda (bst) (null? bst))) (define node (lambda (bst) (car bst))) (define left-subtree (lambda (bst) (car (cdr bst)))) (define right-subtree (lambda (bst) (car (cdr (cdr bst)))))
Here's a pattern based on the BNF:
(define path
(lambda (n bst)
(if (empty-tree? bst)
... ;; didn't find it
... ;; is this the right node?
)
))
If we ever get to an empty tree, then the number we were looking for wasn't in the tree, so we'll signal an error (using Scheme's built-in error function):
(define path
(lambda (n bst)
(if (empty-tree? bst)
(error "number not found!") ;; didn't find it
... ;; is this the right node?
)
))
When were not an an empty tree, we're at a node and there are three cases:
So the code becomes:
(define path
(lambda (n bst)
(if (empty-tree? bst)
(error "number not found!") ;; didn't find it
(if (< n (node bst))
... ;; n is in the left subtree
(if (> n (node bst))
... ;; n is in the right subtree
... ;; n is here
)
)
)
))
Now, we build the path by consing the correct prefix (L or R):
(define path
(lambda (n bst)
(if (empty-tree? bst)
(error "number not found!") ;; didn't find it
(if (< n (node bst))
(cons 'L (path n (left-subtree bst))) ;; in the left subtree
(if (> n (node bst))
(cons 'R (path n (right-subtree bst))) ;; in the right subtree
'() ;; n is here, quit
)
)
)
))
path?
Last updated at 10:22 am on Friday, September 17, 2004.