About me

About me

Feeds

RSS feed

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 [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?

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 


  1. ^ Recursion on Wikipedia.

blog comments powered by Disqus