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
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)))))
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.
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,
blog comments powered by Disqus