A Scheme procedure can invoke itself and we call this recursion. This powerful technique divides a problem into smaller pieces, which are simpler to solve and combine into a final result. Writing a recursive procedure is simple by sticking to three steps:
Your recursive procedure must never perpetually call itself (but sometimes this rule is broken). This is why a base check is a must. Consider these questions when writing a recursive procedure.
Suppose you wish to compute the factorial of a non-negative integer. Each step is then as follows.
Define the procedure and the arguments:
(define (factorial x)Create the base check – a test for which the procedure returns:
(if (equal? x 0)
1Create the body of the procedure – such that it calls itself:
(* x (factorial (- x 1)))Here is the whole procedure pretty-printed:
(define (factorial x)
(if (equal? x 0)
1
(* x (factorial (- x 1)))))Here is what happens. Procedure factorial calls itself with a smaller argument each time, until it reaches zero, at which point it returns unity. On each call, the return value is multiplied by the respective procedure argument. So, (* 1 1), (* 2 1), and (* 3 2). The original procedure invocation returns the final result.
> (factorial 3)
$1 = 6Guile allows you to trace procedures. This means that every call to that procedure is reported to the user during a program run. Tracing is useful to determine whether a function is called with correct arguments.
Here is the trace of factorial.
> ,trace (factorial 3)
trace: | (factorial 3)
trace: | | (factorial 2)
trace: | | | (factorial 1)
trace: | | | | (factorial 0)
trace: | | | | 1
trace: | | | 1
trace: | | 2
trace: | 6Another reason why tracing is useful is to determine whether a recursive procedure is tail-recursive. Without getting into specifics, it means that, for large x, a stack overflow error will not happen. Observe the pattern of the trace. When the trace shape evolves like a triangle, the procedure is not tail-recursive.
Why is that so? Every time the factorial procedure returns, the * procedure is called. What we want is to let the procedure factorial call itself in the final step. This can be done by moving * from outside the procedure call to within the procedure call, by introducing a new argument r, which keeps track of the result. Here is the tail-recursive procedure:
(define (factorial-iter x r)
(if (equal? x 0)
r
(factorial-iter (- x 1) (* r x))))In this case, the pattern of the trace is shaped like a rectangle, unlike that of a triangle.
> ,trace (factorial-iter 3 1)
trace: | (factorial-iter 3 1)
trace: | (factorial-iter 2 3)
trace: | (factorial-iter 1 6)
trace: | (factorial-iter 0 6)
trace: | 6Since the factorial procedure should accept only one argument, the number, we define factorial-iter within the factorial procedure. Here is the final factorial version:
(define (factorial x)
(define (factorial-iter x r)
(if (equal? x 0)
r
(factorial-iter (- x 1) (* r x))))
(factorial-iter x 1))Let us invoke this new factorial with the number 7:
> (factorial 7)
$2 = 5040Some recursive procedures can be computed in constant space, and we say such procedures are tail-recursive. Consider the number of times you can recursively call a procedure. This number is limited by your computer memory. However, tail-recursive procedures can be called an unbounded number of times. When writing computer programs in Scheme, we heavily rely on recursion, and without tail-recursion, programs would quickly run out of stack space. This is why Scheme implementations must be properly tail-recursive, which we can loosely translate as they run tail-recursive procedures in constant space.
We have learned about lambda expressions and procedure calls, which are also expressions. Here, we consider a special case of such expressions, which we say are tail expressions, tail calls, and self-tail calls.
Consider a lambda expression in form of (lambda (<args>) <body>). Suppose the body consists of n expressions: <exp-1>, <exp-2>, …, and <exp-n>. So, (lambda (<args>) <exp-1> <exp-2> ... <exp-n>). Also consider the if special form in form of (if <test> <consequent> <alternative>).
The last expression <exp-n> in the body of a lambda expression is a tail-expression.
The expression <consequent> and the expression <alternative> are both tail-expressions, when the if special form is a tail-expression.
A tail call is a procedure call of a tail-expression.
A self-tail call is a procedure call of a tail-expression, in which the procedure calls itself recursively.
Implementations of Scheme are required to be properly tail-recursive. A Scheme implementation is properly tail-recursive if it supports an unbounded number of active tail calls. A call is active if the called procedure may still return.
Consider the factorial-iter procedure:
(define (factorial-iter x r)
(if (equal? x 0)
r
(factorial-iter (- x 1) (* r x))))Suppose you expand define with lambda:
(define factorial-iter
(lambda (x)
(if (equal? x 0)
r
(factorial-iter (- x 1) (* r x)))))It is straightforward to see that the if special form, in factorial-iter, is the only expression in the body of the lambda expression. As it is the only expression, it is also a tail-expression. Since the if special form is a tail-expression, both the consequent and the alternative expressions are also tail-expressions.
The alternative expression is a tail-expression, and it is a procedure call, which means that it is a tail call. For this tail call, the procedure factorial-iter calls itself recursively, meaning that this is a self-tail call. Scheme implementations must be properly tail-recursive, meaning that this call runs in constant space. This is why the shape of the trace of factorial-iter is a rectangle.
In loose terms, the factorial-iter procedure will not cause a stack overflow error, unlike what may happen in languages such as C.
Consider the unoptimized factorial procedure:
(define (factorial x)
(if (equal? x 0)
1
(* x (factorial (- x 1)))))Suppose you expand define with lambda:
(define factorial
(lambda (x)
(if (equal? x 0)
1
(* x (factorial (- x 1)))))It is straightforward to see that the if special form, in factorial, is the only expression in the body of the lambda expression. As it is the only expression, it is also a tail-expression. Since the if special form is a tail-expression, both the consequent and the alternative expressions are tail-expressions.
The alternative expression is a tail-expression, and it is a procedure call, which means that it is a tail call. But it is not a procedure call of factorial but that of *, which means that it is not an self-tail call. This procedure does not run in constant space.
Macros can also expand themselves. Consider the following examples of the curry macro. The curry macro is named after currying, a concept in which a procedure of many arguments is rewritten as a sequence of procedures that accept only one argument.
Suppose the expression before expansion (EBE) is:
(curry (lambda (x) x) y)Suppose the expression after expansion (EAE) is:
(lambda (y) (lambda (x) x))Begin with:
(define-syntax curry (lambda (x) (syntax-case x ()Write the macro body for the EBE:
(define-syntax curry (lambda (x) (syntax-case x ()
((curry exp var)Introduce a “guard clause” to the pattern, to make sure that var is an identifier, by using the identifier? predicate procedure:
(define-syntax curry (lambda (x) (syntax-case x ()
((curry exp var) (identifier? #'var)Write the macro body for the EAE:
(define-syntax curry (lambda (x) (syntax-case x ()
((curry exp var) (identifier? #'var)
#'(lambda (var) (begin exp))))))Expand to see macro usage:
> ,expand (curry (lambda (x) x) y)
$1 = (lambda (y) (lambda (x) x))Now note that you can chain curry:
> ,expand (curry (curry (lambda (x) x) y) z)
$2 = (lambda (z) (lambda (y) (lambda (x) x)))But also note how the curry creates the identity procedure (lambda (x) x):
> ,expand (curry x x)
$3 = (lambda (x) x)Consider the following chain:
>,expand (curry (curry (curry body x) y) z)
$4 = (lambda (z) (lambda (y) (lambda (x) body)))We can write this chain of curry calls as one macro. Let us write curry such that the EBE is:
(curry body x y z ...)Now the EAE is:
(lambda (x) (lambda (y) (lambda (z) (... body))))Begin with:
(define-syntax curry (lambda (x) (syntax-case x ()Write the macro body for the EBE:
(define-syntax curry (lambda (x) (syntax-case x ()
((curry body var var* ...)Introduce a “guard clause” to the pattern, to make sure that var is an identifier, by using the identifier? predicate procedure.
(define-syntax curry (lambda (x) (syntax-case x ()
((curry body var var* ...) (identifier? #'var)Write the macro body for the EAE. Let curry call itself:
(define-syntax curry (lambda (x) (syntax-case x ()
((curry body var var* ...) (identifier? #'var)
#'(lambda (var) (curry body var*)))And now handle the base check:
(define-syntax curry (lambda (x) (syntax-case x ()
((curry body var) (identifier? #'var)
#'(lambda (var) body))
((curry body var var* ...) (identifier? #'var)
#'(lambda (var) (curry body var* ...))))))Note that the base check must come before the macro body (curry body var var* ...) that accepts an arbitrary number of arguments.
Let us now test the macro by expanding:
> ,expand (curry body x)
$7 = (lambda (x) body)
> ,expand (curry body x y)
$8 = (lambda (x) (lambda (y) body))
> ,expand (curry body x y z)
$9 = (lambda (x) (lambda (y) (lambda (z) body)))The guard clause makes it illegal to call curry with anything that is not an valid identifier:
> ,expand (curry body 1)
While executing meta-command:
Syntax error:
unknown file:40:8: source expression failed to match any pattern in form (curry body 1)