## An erratic two-dimensional recursive function Q2

14th March 2020

I have been looking for interesting recursive functions to use as a benchmark for different implementations of languages such as my Lisp interpreter, uLisp. My search has taken me from the Fibonacci function, Pascal's triangle, and the Hofstadter Q sequence, to a new erratic two-dimensional function I've called Q2.

### Two-dimensional Fibonacci function

I started by thinking about how to make a two-dimensional version of the Fibonacci function. The number at coordinates (x, y) would be the sum of the two numbers at (x-1, y) and (x, y-1). Here's the function, which I've called fib2:

```(defun fib2 (x y)
(if (or (< x 1) (< y 1)) 1
(+ (fib2 (1- x) y) (fib2 x (1- y)))))```

Here's fib2 solved for values of x and y from 0 to 11, with (0, 0) at the bottom left corner:

```1     11    66    286   1001  3003  8008  19448 43758 92378 184756
1     10    55    220   715   2002  5005  11440 24310 48620 92378
1     9     45    165   495   1287  3003  6435  12870 24310 43758
1     8     36    120   330   792   1716  3432  6435  11440 19448
1     7     28    84    210   462   924   1716  3003  5005  8008
1     6     21    56    126   252   462   792   1287  2002  3003
1     5     15    35    70    126   210   330   495   715   1001
1     4     10    20    35    56    84    120   165   220   286
1     3     6     10    15    21    28    36    45    55    66
1     2     3     4     5     6     7     8     9     10    11
1     1     1     1     1     1     1     1     1     1     1    ```

It soon dawned on me that fib2 is just Pascal's triangle, so the number fib2(x, y) is the number of combinations of n things taken k at a time, or nCk, where n = x + y and k = x.

One of my favourite recursive functions is the Hofstadter Q sequence, one of several recursive sequences described in Douglas Hofstadter's brilliant book "Gödel, Escher, Bach: an Eternal Golden Braid". It is defined as follows:

```(defun q (n)
(if (<= n 2) 1
(+
(q (- n (q (- n 1))))
(q (- n (q (- n 2)))))))```

It is related to the Fibonacci sequence, except that in this case the two preceding terms specify how far to go back in the sequence to find the two terms to be summed. The intriguing thing about it is that its behaviour is quite erratic; for example, q(14) = 8, q(15) = 10, and q(16) = 9.

### Two-dimensional function Q2

I thought about whether one could combine Pascal's triangle with the double recursion used in Hofstadter's Q sequence. So the value at (x, y) would be the sum of two values, found by going back (x-1, y) in the x direction, and (x, y-1) in the y direction. Here's the function which I've called Q2:

```(defun q2 (x y)
(if (or (< x 1) (< y 1)) 1
(+ (q2 (- x (q2 (1- x) y)) y)
(q2 x (- y (q2 x (1- y)))))))```

It has beautifully erratic behaviour; here's the function for values of x and y from 0 to 15, with (0, 0) at the bottom left corner:

```1    6    6    6    6    2    42   2    170  2    497  2    1200 2    2541 2
1    5    5    6    10   15   2    85   2    262  2    638  2    1341 2    2541
1    5    5    6    3    6    36   2    128  2    327  2    703  2    1341 2
1    5    5    4    5    20   2    70   2    177  2    376  2    703  2    1200
1    5    5    5    9    2    35   2    92   2    199  2    376  2    638  2
1    5    5    5    4    19   2    50   2    107  2    199  2    327  2    497
1    4    4    5    9    2    26   2    57   2    107  2    177  2    262  2
1    4    4    5    2    14   2    31   2    57   2    92   2    128  2    170
1    4    4    3    8    2    17   2    31   2    50   2    70   2    85   2
1    4    4    4    4    9    2    17   2    26   2    35   2    36   2    42
1    3    3    4    5    2    9    2    14   2    19   2    20   6    15   2
1    3    3    4    2    5    4    8    2    9    4    9    5    3    10   6
1    3    3    2    4    4    4    3    5    5    5    5    4    6    6    6
1    2    2    3    3    3    4    4    4    4    5    5    5    5    5    6
1    2    2    3    3    3    4    4    4    4    5    5    5    5    5    6
1    1    1    1    1    1    1    1    1    1    1    1    1    1    1    1 ```

It's such a simple function I can't believe it hasn't been discussed before; if anyone can find a reference please let me know.

### Benchmarks

It's a time-consuming function to calculate (without memoization). Here are some benchmarks for calculating Q2(14, 15) = 2514:

• LispWorks running on a 2.8 GHz MacBook Pro: 137 secs.
• SBCL running on a 2.8 GHz MacBook Pro: 213 secs.

How does your version of Lisp fare?

### Unsolved problems

Obviously Q2(x, y) = Q2(y, x). However, the function raises several interesting questions:

• Is Q2(x, y) always 2 when x = y?
• Is Q2(x+1, y+1) always larger than Q2(x, y) when x and y differ by 1?
• Is there an explicit formula for Q2(x, y)?

### Footnote: printing the function

Here's the program I used to print out the function values:

```(defun test (size)
(let (a)
(dotimes (x size a)
(let (b)
(push (dotimes (y size (reverse b)) (push (q2 x y) b)) a)))
(format t "~{~{~5a~}~%~}" a)))```