More Examples of Recursive Functions

Recursive append

The recursive definition of append follows:

It is equivalent to the Lisp

(defun recAppend (x y)
  (if (null x)
      y
    (cons (car x) (recAppend (cdr x) y))))

If the first argument is NIL, recAppend returns the second argument. Otherwise it joins the two lists together.

decons is short for deconstruct and takes a List and returns two values: its first element and the rest of the list. This does the work of the (car x) and (cdr x) calls in the recAppend Lisp function. If the inputs to recAppend are (a b c) and (d e), the values produced at each stage are

Inputs	Vertex	Outputs
`NIL (a b c)`	`unless+`	`(a b c)`
`(a b c)`	`decons`	`a (b c)`
`(b c) (d e)`	`recAppend`	`(b c d e)`
`a (b c d e)`	`cons`	`(a b c d e)`

Tail-recursive reverse

recAppend is not the best implementation of append, as the repeated recursive calls require a lot of stack space. For very long lists this would result in stack overflow. It would be better to reverse the first argument, and then reverse it onto the second. This gives us the same answer, but in addition, gives us a reverse function. It would be best to implement reverse iteratively, which will be done in a later tutorial, but first we give a tail-recursive implementation.

It is equivalent to the Lisp

(defun tailRecReverse (x y)
  (if (null x)
      y
    (tailRecReverse (cdr x) (cons (car x) y))))

If the first argument is NIL, tailRecReverse returns the second argument. Otherwise, it reverses the first argument onto the second, e.g.
(tailRecReverse '(c b a) '(d e)) returns (a b c d e).

Inputs	Vertex	Outputs
`NIL (a b c)`	`unless+`	`(a b c)`
`(a b c)`	`decons`	`a (b c)`
`a NIL`	`cons`	`(a)`
`(b c) (a)`	`tailRecReverse`	`(c b a)`

In the sandbox, first tailRecReverse is called to reverse a list. Then, tailRecReverse is called twice, giving the same result we would get were recAppend called instead:

rev append calls

We can wrap the two calls into a new append function, and then call that:

newAppend

The results of making the three calls are:

rev append output

Pascal's triangle

Now, let's look at a more complex function, to compute Pascal's triangle.

pascal

This builds up a list of lists of integers in reverse order. The first two branches which output NIL when the input is 0, and ((1)) when the input is 1, are the base cases. The other branch will be easier to understand by going through the values produced at each stage:

Inputs	Vertex	Outputs
`1 6`	`=`	`NIL`
`NIL 6`	`unless+`	`6`
`6`	`sub1`	`5`
`5`	`pascal`	`((1 4 6 4 1) (1 3 3 1) (1 2 1) (1 1) (1))`
`((1 4 6 4 1) (1 3 3 1) (1 2 1) (1 1) (1))`	`car`	`(1 4 6 4 1)`
`0 (1 4 6 4 1)`	`cons`	`(0 1 4 6 4 1)`
`(0 1 4 6 4 1)`	`reverse`	`(1 4 6 4 1 0)`
`iAdd (0 1 4 6 4 1) (1 4 6 4 1 0)`	`mapcar`	`(1 5 10 10 5 1)`
`(1 5 10 10 5 1) ((1 4 6 4 1) (1 3 3 1) (1 2 1) (1 1) (1))`	`cons`	`((1 5 10 10 5 1) (1 4 6 4 1) (1 3 3 1) (1 2 1) (1 1) (1))`

The first attempt at output wasn't particularly readable, so we reversed the output of pascal to get it in the usual order, and then transcribed each list separately. This was done by mapping transcribe1 (which transcribes a single value) over each list comprising pascal's output.

Previous Up Next