Here are some examples of recursive functions in Scheme.
You can copy and paste these examples into your Scheme interpreter. In DrScheme, paste them into the Definitions Window.
It is informative to trace these functions. In DrScheme, put the
expression (require-library "trace.ss") at the top of the
Definitions window.
It is informative to trace both the recursive function being defined
and the combining function that forms the results. For example, in
rev turn on tracing by typing this expression in the
Interaction window: (trace rev append). To turn off
tracing, use (untrace rev append).
Sequences
Binary Trees
Other Trees
Last updated November 21, 2000 (to clarify the distinction between binary trees and other trees). Use your browser's Reload or Refresh button to get the latest version.
You can treat a list as a sequence of elements, processing the list from the beginning to the end. Use this form when the list contains no sublists, or when you don't need to deal with the internal structure of the sublists.
Here is the basic pattern:
(define (f lst ...) ;; One of the arguments is a list
(if (... base case ...) ;; Often (null? lst)
... value to return for base case ... ;; Often '()
(g ... (f (cdr lst) ...) ...))) ;; Recursive call applies f to (cdr lst)
;; Combining function g forms the result
;; Often g is cons or append
;; Often another arg. to g is (car lst)
One of the arguments to the function is a list. The base case is
usually the empty list. Each recursive call invokes the function on
the cdr of the list, which guarantees that the list gets smaller on
each recursive call until the base case is reached. The recursive
calls work their way down the list until the end. The results of the
recursive call are usually combined with something else (often the
car of the list) by another function (often
cons or append) to form the results.
This technique is called single recursion because there is a single recursive call in the body of the function.
This example returns a list, the input list reversed.
;; Like Scheme reverse
(define (rev lst)
(if (null? lst)
'()
(append (rev (cdr lst)) (list (car lst)))))
This example returns a number, the length of the list.
;; Like Scheme length
(define (len lst)
(if (null? lst)
0
(+ 1 (len (cdr lst)))))
This example searches the list and returns the list from the point
where the search was csuccessful. If the search is unsuccessful, it
returns #f.
;; Like Scheme member
(define (memb x lst)
(if (null? lst)
#f
(if (equal? x (car lst))
lst
(memb x (cdr lst)))))
This example shows how to define a higher order function using recursion.
The first argument f is itself a function.
;; Like Scheme map
(define (mapper f lst)
(if (null? lst)
'()
(cons (f (car lst)) (mapper f (cdr lst)))))
This example shows how to define Scheme append using
only car, cdr, and cons.
;; Like Scheme append, ex 17.6 from Simply Scheme
(define (app lst1 lst2)
(if (null? lst1)
lst2
(cons (car lst1) (app (cdr lst1) lst2))))
This example is much like rev above but reverses a word (an atom)
not a list.
;; backwards - reverse a word
;; Called reverse in Simply Scheme p 192 and 192.
;; Requires last and bl from simply.scm or simply-teachpack.scm
(define (backwards wd)
(if (empty? wd)
""
(word (last wd)
(backwards (bl wd)))))
Tree recursion treats a list as a branching data structure, exploring each branch. Use this form when the list contains sublists, and you must deal with the internal structure of the sublists.
When the sublist in the car of the input should be
treated the same as the sublists in the cdr, you can
treat the list as a binary tree where each branch divides in
two. The car of each list (or sublist) is the left
branch and the cdr of each list is the right branch.
Here is the basic pattern:
(define (f struc ...) ;; One of the args is a structured list
(cond (... base case 1 ...) ... value1 ...) ;; Often (null? struc), return '()
(... base case 2 ...) ... value2 ...) ;; Often (word? struc), return struc
(else (g ... (f (car lst)) ;; Recursive call applies f to (car lst)
(f (cdr lst)))))) ;; Recursive call applies f to (cdr lst)
;; Combining function g forms the result
;; Often g is cons or append
This looks almost the same as the pattern for single recursion,
except there are two recursive calls in the body of the function, one
for the car and the other for the cdr of the structure
(instead of just for the cdr, as in single recursion). The recursive
call on the car guarantees that the function will dig into nested sublists
as deeply as necessary. Often there are two base cases as well, one for the
empty list and another for an atom (tested by word? in Simply Scheme,
roughly equivalent to (not (list? ...)) using standard scheme functions).
Notice the symmetry between the car and the cdr in the
two recursive calls.
This function flattens a structured list:
;; Ex 17.12 from Simply Scheme
(define (flatten struc)
(cond ((null? struc) '())
((word? struc) (list struc))
(else (append (flatten (car struc))
(flatten (cdr struc))))))
This function counts all the words (that is, atoms) in a structured list:
;; Ex 17.13 from Simply Scheme
(define (deep-count lst)
(cond ((null? lst) 0)
((word? lst) 1)
(else (+ (deep-count (car lst))
(deep-count (cdr lst))))))
Binary trees have just two branches from each node. Other trees may
have several branches from each node. These trees can be represented
as lists where the car of the list (and each sublist)
represents the data at the node and the cdr of the list
(and each sublist) is the list of branches attached to that node (called
the forest). The leaves of the tree are represented by lists
with only one element, the data at that leaf (the cdr of
the leaf nodes are empty lists, indicating there are no more branches.
An example of such a tree appears in Simply Scheme chapter 18, on page 315 (in the second edition). Another example appears in the solution to problem 2 in our November 9 quiz.
In trees like this, the car of each list must be treated differently
than the cdr because it plays a different role --- the car
and cdr are not symmetrical.
Simply Scheme handles these trees using two procedures that
exhibit mutual recursion --- each procedure calls the other.
The argument to the first procedure is the list itself (that is, the
whole tree). The first procedure calls the second, whose argument is
the cdr of the list (that is, the list of branches or forest). The
second procedure in turn calls the first on the car of the
this list and calls itself on the cdr.
Here is the basic pattern:
(define (f n ...) ;; One of the arguments is a number
(if (... base case ...) ;; Often (= n 0) or (= n 1)
... value to return for base case ... ;; Often 1 or 0
(g ... (f (- n 1) ...) ...))) ;; Recursive call applies f to (- n 1)
;; Combining function g forms the result
;; Often g is + or *
One of the arguments to the function is a number. The base case is
usually zero or one. Each recursive call invokes the function on the
number minus one, which guarantees that the number gets smaller on
each recursive call until the base case is reached. The results of
the recursive call are usually combined with something else by another
function (often + or *) to form the results.
When the combining function is +, the base case is often
0 (because adding zero does not change the result) and when it is
*, the base case is 1 (because multiplying by one does
not change the result).
This is singly recursive, similar to functions that treat a list as a sequence.
This example takes a single numeric argument.
;; Factorial: n! = n*(n-1)*...*1 from Simply Scheme p. 194
(define (fact n)
(if (= n 1)
1
(* n (fact (- n 1)))))
This example takes two numeric arguments.
;; Like Scheme expt: raise i to the n-th power, i*i*i... n times
(define (pow i n)
(if (= n 0)
1 ; Base case: anything to the zero power is one
(* i (pow i (- n 1)))))
This example has two recursive calls, but each call makes the number smaller so eventually the function returns.
;; Fibonacci: fib(n) = fib(n-1) + fib(n-2)
(define (fib n)
(if (< n 2)
1 ; Base case: fib(1) or fib(0) is 1
(+ (fib (- n 1))
(fib (- n 2)))))
This example shows how to use recursion to build up a list. Each
recursive call uses append to add an element to the end
of the list. However the numeric argument n gets smaller on each
recursive call so the function can return.
;; Countup - put a list of numbers from 1 to n in ascending order on front of lst
;; to get just a list from 1 to n, do (countup n '())
(define (countup n lst)
(if (< n 1)
lst
(append (countup (- n 1) lst) (list n))))