Scheme：將遞歸過程改爲迭代過程

Question

這是函數f（n）= n的遞歸過程，如果n和f（n）= f（n-1）+ 2f（n-2）+ 3f （n - 3）如果n≥3

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

問題集是將其更改爲迭代遞歸。我想出了這個：

(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))))) 

的東西是錯誤的：

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

在這花了幾個小時，但我看不到我在做什麼錯。 我知道代碼是重複性和笨重的，但我想在查看語法之前，先看看我沒有理解的過程。

謝謝。

Answer 1

的一部分從錯誤中，與您的代碼的問題是，只有功能basemaker是尾遞歸，但不g-helper，因爲其體內的「最後」呼籲是，+，不g-helper本身。

要以遞歸尾遞歸的方式編寫遞歸函數，通常需要通過在計算過程中添加一個參數來「累積」部分結果並在結尾返回該參數來轉換該函數。然而，在這種情況下，我們需要另外的參數來追蹤函數在其計算過程中的三個結果的軌跡，因爲要計算函數的值爲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 = 2的函數的值中，n = 1，n = 0時分別與計算期間的功能的新的值是從前三個值計算得出，並通過「移位」其他兩個值傳遞給下一次迭代。 當我們達到小於3的值（即2）時，該過程終止，結果是該函數的前一個結果。