## Recursion without an explicit base case

15th February 2017

The usual definition of a recursive algorithm is that it can be specified by two properties:

- A simple base case: a terminating scenario that does not use recursion to produce an answer.
- A set of rules that reduce all other cases toward the base case
^{[1]}.

A typical example is the recursive algorithm for factorial:

- factorial(0) is 1, the base case.
- factorial(n) is n * factorial(n-1), reducing all other cases towards the base case.

In Lisp, this is expressed as:

(defun rec1 (n) (cond ((= n 0) 1) (t (* n (rec1 (1- n))))))

But does there always have to be a test for a base case?

For further discussions about this topic see Recursive functions without an explicit base case.

### A recursive function with no base case

How about the following function?

- rec(n) is 1 + (n * rec(n-1)).

This is a recursively-defined function with no explicit base case, and it actually works fine:

- rec(0) is 1.
- rec(1) is 2.
- rec(2) is 5.
- rec(3) is 16.

and so on.

Attempting to write this in Lisp doesn't work, however:

(defun rec (n) (1+ (* n (rec (1- n)))))

Trying it in the Listener:

CL-USER > (rec 1) Stack overflow

The problem is that the ***** operator evaluates all its arguments before invoking the function, causing a stack overflow.

### Getting this to work using a macro

You could argue that when ***** evaluates its first argument, and finds that it's zero, it should just return zero without evaluating any more arguments, in a similar way to **and**.

We can achieve this behaviour by using a macro to define a new version of *, *2:

(defmacro *2 (a b) `(if (zerop ,a) 0 (* ,a ,b)))

Now our function **rec** will work:

(defun rec (n) (1+ (*2 n (rec (1- n)))))

For example:

CL-USER > (rec 10) 9864101

Perhaps it looks as if we've sneaked in a conditional test for a base case through the back door, but that's not really true. An implementation of a Lisp-like language could provide this modified version of the * operator with a slight increase in efficiency, and no other noticeable change.

### Postscript

This is an interesting function; the first 20 terms are as follows:

1, 2, 5, 16, 65, 326, 1957, 13700, 109601, 986410, 9864101, 108505112, 1302061345, 16926797486,

236975164805, 3554627472076, 56874039553217, 966858672404690, 17403456103284421,

330665665962404000

### Update

12th August 2024: Following a discussion with Xero I've added "explicit" in the title.

blog comments powered by Disqus