第四，带有递归的Hofstadter Q序列

Question

我正在尝试使用递归定义来实现Hofstadter的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（编辑：现在具有固定，正确的实现）

我认为这是行不通的，因为每次调用Qwhere n大于之后，都会向堆栈中添加值2，从而使-rot行不通。

是否有一个简单的调整即可完成这项工作？还是我需要使用其他方法，也许将变量用于n？

OEIS：A005185

Answer 1

我意识到我的错误。n调用之后Q，我不需要保留，但是我已经用了dup足够的时间来保存每个调用。n每次调用后，此变量将保留在堆栈中，从而使输出不正确。我删除了其中一个，dup它可以正常工作。