## Recursion without a 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 .

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?

### A recursive function with no base case

• 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

1. ^ Recursion on Wikipedia.

Previous: Pairwise function