Scheme : 반복적 인 프로세스를 반복적 인 것으로 바꾼다

Question

이것은 n < 3이고 f (n) = f (n-1) + 2f (n-2) + 3f라면 함수 f (n) = n에 대한 재귀 프로 시저이다. (n - 3) n ≥ 3 일 경우

(define (f n) 
    (if (< n 3) 
     n 
     (+ (f (- n 1)) 
     (* 2 (f (- n 2))) 
     (* 3 (f (- n 3)))))) 

문제는 반복적 인 재귀로 변경하는 것입니다. 나는이 함께했다 : 이것에

> (f 3) 
4 
> (f 4) 
11 
> (f 5) 
25 
> (g 3) 
6 
> (g 4) 
19 
> (g 5) 
45 
> 

지출 시간,하지만 난 내가 잘못 뭘하는지 볼 수 없습니다 :

(define (g n) 
    (if (< n 3) 
     n 
     (g-helper n))) 

(define (g-helper n) 
    (if (< n 3) 
     n 
     (+ (basemaker 0 1 (- n 1)) 
     (g-helper (- n 1)) 
     (* 2 (basemaker 0 2 (- n 2)) 
      (g-helper (- n 2))) 
     (* 3 (basemaker 0 3 (- n 3)) 
      (g-helper (- n 3)))))) 

(define (basemaker counter constant n) 
    (cond ((= 2 n) 2) 
     ((= 1 n) 1) 
     ((= 0 n) 0) 
     (else 
      (basemaker (+ counter constant) constant (- n constant))))) 

뭔가 잘못된 것입니다. 코드가 반복적이고 까다 롭다는 것을 알고 있지만 구문을 개선하기 전에 프로세스에 대해 이해하지 못했던 것을보고 싶습니다.

감사합니다. 몸 안에 "마지막"전화 자체 g-helper에하지, +의 때문에

Answer 1

오류의 일부는, 코드의 문제는,하지 g-helper 기능 만 basemaker 꼬리 재귀입니다,하지만.

꼬리 재귀 방식으로 재귀 함수를 작성하려면 일반적으로 계산 중에 부분 결과를 "누적"하고 마지막에 반환되는 매개 변수를 추가하여 함수를 변환합니다. 그러나이 경우에는 세 개의 결과 값 트랙을 유지하는 세 개의 개의 추가 매개 변수가 필요합니다.이 값은 n 값에서 함수를 계산하기 위해 이전 세 개의 값을 사용해야하기 때문입니다. 그래서 여기 가능한 솔루션

초기

(define (g n) 
    (define (aux n fn1 fn2 fn3) 
    (if (< n 3) 
     fn1 
     (aux (- n 1) (+ fn1 (* 2 fn2) (* 3 fn3)) fn1 fn2))) 
    (if (< n 3) 
     n 
     (aux n 2 1 0))) 

은 상기 파라미터 N, N = 2에 대한 기능 값을 지정 = 1이고, n = 0을 각각 상기 계산시 함수에 대한 새로운 값이된다 이전의 3 개의 값으로부터 계산되고, 다른 2 개의 값을 "이동"시킴으로써 다음 반복으로 전달된다. 프로세스가 3보다 작은 값 (즉, 2)에 도달하면 프로세스가 종료되고 그 결과는 함수의 이전 결과입니다.