Search code examples
recursionsequenceforthgforthoeis

Forth, Hofstadter Q Sequence with Recursion

I'm attempting to implement Hofstadter's Q Sequence using the recursive definition:

Q(1) = 1
Q(2) = 1
Q(n) = Q(n - Q(n-2)) + Q(n - Q(n-1)) for n > 2

I get the wrong result for n > 3. Here's what I have so far:

: Q recursive
    dup 3 <
    if
        drop 1
    else
        dup dup 2dup 2 - Q - Q -rot 1- Q - Q +
    then ;

Try it online: http://ideone.com/PmnJRO (Edit: Now has the fixed, correct implementation)

I think it doesn't work because there are values added to the stack after each call of Q where n is greater than 2, making -rot not work as I expected.

Is there a simple adjustment to make this work? Or do I need to use a different approach, maybe using a variable for n?

OEIS: A005185

Solution

  • I realized my mistake. I didn't need to preserve n after calling Q, but I had used dup enough times to preserve it each call. This left n on the stack after each call, making the output incorrect. I removed one of the dup's and it works.