Procedures in Scheme are first class, meaning that they can be passed as arguments, bound to variables and returned as values from other procedures. Arguments are passed by value. Note that the order in which the arguments are evaluated is not defined. We shall now study procedures in further detail.
Procedures which call themselves within the body of their lambda expression are said to be recursive. In general, recursive procedures need a terminating condition (otherwise they will run forever) and a recursive step (describing how the computation should proceed).
We will use one of MzScheme's procedures trace to illustrate the behaviour of recursive procedures. The procedure trace shows the intermediate steps as the recursion proceeds as well as the intermediate values returned.
For example, let us define a procedure for counting the factorial of a number.
We know that 
equals 1 and we will use this as our terminating
condition. Apart from that, we know that 
is the same as
,
which gives us our recursive step. We are now ready to define the procedure
itself:
(define fact
(lambda (n)
(if (= n 0) ; the terminating condition
1 ; returning 1
(* n (fact (- n 1)))))) ; the recursive step
Let' see what happens if we try to compute the factorial of 7 by using the procedure trace:
> (fact 7) 5040 > (trace fact) (fact) > (fact 7) |(fact 7) | (fact 6) | |(fact 5) | | (fact 4) | | |(fact 3) | | | (fact 2) | | | |(fact 1) | | | | (fact 0) | | | | 1 | | | |1 | | | 2 | | |6 | | 24 | |120 | 720 |5040 5040 > (untrace fact) (fact)
If the recursion is applied over the top-level items of a list it is said to be flatly recursive. For example, if we have a list (1 2 (3 4)) then the top level items are 1, 2 and (3 4).
Scheme provides a procedure append, which appends the lists given as arguments. We will now define our own append procedure, which will take two lists as arguments and return a list consisting of these arguments. For example, if we have the lists (a b c) and (d e f), our procedure append would return (a b c d e f) if these lists were given as arguments.
We start by trying to figure out how to append the lists. Clearly, we need to find a way to attach the items of the latter list to the items of the first list. We also need the procedures cons, car and cdr. To construct our list, we will need to build a new list containing the items. The first element of this list will be the first element in the list (a b c) and the last elements will be the elements in (d e f). Since (d e f) is a list, we can construct our list by consing the elements of our first list with our second list. However, we still need to pick out the elements of our first list, one at a time until it is empty. By this we find our terminating condition: when the first list is empty, return the second list. The second list will then be consed to the elements of the list we are constructing, which at this point already contains all the elements of the first list.
(define append
(lambda (ls1 ls2)
(if (null? ls1)
ls2
(cons (car ls1) (append (cdr ls1) ls2)))))
To see how this works, let's use trace and see what happens:
> (trace append) (append) > (append '(a b c) '(d e f)) |(append (a b c) (d e f)) | (append (b c) (d e f)) | |(append (c) (d e f)) | | (append () (d e f)) | | (d e f) | |(c d e f) | (b c d e f) |(a b c d e f) (a b c d e f)
Deep recursion is recursion over all of the atomic items of a list structure, i.e. the procedure is applied to the car and cdr of a list. Deep recursion is also referred to as tree recursion. We might have lists containing other lists, e.g. (1 2 (3 4 5)). The list as a whole has nesting level 0, whereas the top level items 1, 2 and (3 4 5) have the nesting level 1. For example, the element 3 in (1 2 (3 4 (5 (6 7)))) has nesting level 2, whereas the element 7 has nesting level 4.
Let's define a procedure for counting the number of atomic items in a list structure. If the list is empty, it contains 0 elements. If the list is not empty and not a pair, it contains 1 element. Otherwise, it contains the number of elements in its car plus the number of elements in its cdr. We are now ready to define our procedure (also found in SICP p. 109):
(define count-leaves
(lambda (ls)
(cond ((null? ls) 0)
((not (pair? ls)) 1)
(else (+ (count-leaves (car ls))
(count-leaves (cdr ls)))))))
Let's see how count-leaves works:
> (count-leaves '(1 2 3 4)) 4 > (count-leaves '(1 2 (3 4))) 4 > (count-leaves '(1 2 (3 4 (5 6 (7 8) 9 (10 11))))) 11
To see the procedure calls and return tables of count-leaves, we use the procedure trace:
> (trace count-leaves) (count-leaves) > (count-leaves '(a (b c (d e)))) |(count-leaves (a (b c (d e)))) | (count-leaves a) | 1 | (count-leaves ((b c (d e)))) | |(count-leaves (b c (d e))) | | (count-leaves b) | | 1 | | (count-leaves (c (d e))) | | |(count-leaves c) | | |1 | | |(count-leaves ((d e))) | | | (count-leaves (d e)) | | | |(count-leaves d) | | | |1 | | | |(count-leaves (e)) | | | | (count-leaves e) | | | | 1 | | | | (count-leaves ()) | | | | 0 | | | |1 | | | 2 | | | (count-leaves ()) | | | 0 | | |2 | | 3 | |4 | |(count-leaves ()) | |0 | 4 |5 5
A recursive procedure executing an iterative process in constant space is said to be tail-recursive. In other words, instead of having to wait for the computation of recursive procedure calls to return with a value needed, thus having to construct return tables, we are able to define procedures which save the state of a computation in a variable, which, when the terminating condition is reached, will be returned as the final value of the procedure. Iterative procedures are implemented by using tail recursion. This is actually the most important feature to understand together with the fact that the intermediate results of the computation will not be saved in a return table, but in a variable that by the end of the computation will be returned as the final result. Hence, the last thing that a tail-recursive procedure does before terminating is calling itself!
Let us take a look at the recursive as well as the iterative version of factorial:
;; The recursive version
(define fact
(lambda (n)
(if (= n 0)
1
(* n (fact (- n 1))))))
;; The iterative version used in SICP p.33
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))
;; The iterative version using letrec, equivalent to the one in SICP
(define factorial
(lambda (n)
(letrec ((iter
(lambda (product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))))
(iter 1 1)))
What makes the latter procedure iterative is the fact that the variable product will be updated as the computation continues. When the final condition is reached, product will be returned. The update is performed when the procedure is called--as you can see, the variable product is an argument (in this case the first) of iter and when iter is recursively called, it is called with the first argument being (* counter product). If the final condition is reached at this point, this argument will be returned, otherwise another tail-recursive step which updates the product will be taken.
Tail recursion also differs from normal recursion by the fact that the procedure called recursively will not be an argument of another procedure, e.g. multiplication. The recursive step of the recursive fact is the following:
(* n (fact (- n 1))))))
The computation therefore needs to wait for each call to fact to return, after which multiplication is applied. Tail recursion does not share this wasteful defect. The recursive step of the iterative fact is the following:
(iter (* counter product)
(+ counter 1))))))
As we can see, iter calls itself recursively without being an argument to any other procedure, thus not needing to wait for any values to return. It also saves the state of the computation by passing it as an argument and returning the current state as the final state when the terminating condition is reached.
Let's use trace and see the procedures fact and factorial in action:
;; We start with the recursive one > (trace fact) (fact) > (fact 5) |(fact 5) | (fact 4) | |(fact 3) | | (fact 2) | | |(fact 1) | | | (fact 0) | | | 1 | | |1 | | 2 | |6 | 24 |120 120 ;; and compare this to the iterative one > (factorial 5) |(factorial 5) |120 120
Actually, the iterative version performs equally many calls, but the procedure trace does not show them. The following calls are made:
(iter 1 1) (iter 1 2) (iter 2 3) (iter 6 4) (iter 24 5) (iter 120 6) ==> 120
What trace does make clear is the fact that no return tables are needed.
Even if tail recursive procedures are more efficient in most cases, they are not usually as straightforward to implement as recursive ones. It takes some insight and some practice, but the reader is encouraged to try to figure out how to write a recursive procedure tail-recursively.
The syntax of do is the following:
(do ((var1 init1 step1)
...)
(test expr ...)
command ...)
First the init expressions are evaluated in some unspecified order and the results are stored in the bindings of the variables var1... After this the iteration can begin. First test is evaluated. If test is true, the following expressions are evaluated from left to right and the value of the last expr is returned. The iteration then terminates. If test evaluates to false, then the command expressions are evaluated in order for effect. The step expressions are evaluated and the result is stored in the variables var1 ..., which are bound to fresh locations. The next iteration can now begin. Note that it is an error for a variable to occur more than once in the list of variables.
For example, the following expression binds the string ``foobar'' to the variable str and the value 0 to the variable i. The variable i will be increased by one for each iteration until i equals the length of str. When this happens, str will be returned, otherwise the character at index i in str will be set to the character b.
> (do ((str (string #\f #\o #\o #\b #\a #\r))
(i 0 (+ i 1)))
((= i (string-length str)) str)
(string-set! str i #\b))
"bbbbbb"