recursion - 第四，Hofstadter Q 序列的递归

Question

我正在尝试实现 Hofstadter's Q Sequence使用递归定义:

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

Answer 1

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