넷째, 재귀

Question

와 호프스 태터 Q 순서는 내가 재귀 정의를 사용하여 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 중 하나를 제거하고 작동합니다.