recursion - 四、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 nis greater than后都会向堆栈添加值2，从而-rot无法按预期工作。

是否有一个简单的调整来完成这项工作？还是我需要使用不同的方法，也许使用变量 for n？

OEIS：A005185

Answer 1

我意识到我的错误。我不需要n在调用后保存Q，但我已经使用dup了足够的时间来保存每次调用。每次调用后，这都会留n在堆栈上，导致输出不正确。我删除了其中一个，dup它可以工作。