四、带递归的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?

的变量

Answer 1

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

Forth, Hofstadter Q Sequence with Recursion