2016-07-29 7 views
3

Я пытаюсь реализовать Hofstadter's Q Sequence используя рекурсивное определение:Forth Хофштадтер 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

ответ

4

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