Forth, Hofstadter Q Sequence с рекурсией

Question

Я пытаюсь реализовать последовательность Q Хофштадтера, используя рекурсивное определение:

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

Я получаю неправильный результат для n > 3, Вот что у меня так далеко:

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

Попробуйте онлайн: http://ideone.com/PmnJRO (Edit: теперь имеет фиксированную, правильную реализацию)

Я думаю, что это не работает, потому что есть значения, добавленные в стек после каждого вызова Q где n больше, чем 2, делая -rot не работает, как я ожидал.

Есть ли простая настройка, чтобы сделать эту работу? Или мне нужно использовать другой подход, может быть, используя переменную для n?

OEIS: A005185

Answer 1

Я понял свою ошибку. Мне не нужно было сохранять n после звонка Q, но я использовал dup достаточно раз, чтобы сохранить это каждый звонок. Это осталось n в стеке после каждого вызова, что делает вывод неправильным. Я удалил один из dupи это работает.