В-четвертых, Q-последовательность Хофштадтера с рекурсией

Я пытаюсь реализовать 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 (изменение: теперь фиксированная, правильная реализация)

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

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

OEIS: A005185


recursion sequence forth gforth oeis
person mbomb007    schedule 29.07.2016    source источник

Ответы (1)


arrow_upward
5
arrow_downward

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

person mbomb007    schedule 29.07.2016