用尾遞歸求解「n-rooks」

Question

我試圖用尾遞歸解決n個問題，因爲它比標準遞歸更快，但是我們無法確定如何使它全部工作。我擡頭一看這個問題背後的理論和發現，是被什麼東西給解決方案稱爲這是由下式給出「電話號碼」：

其中T（1）= 1和T （2）= 2

我創建了評估這個方程遞歸函數，但它只能快速上升到T（40），我需要它來計算，其中n> 1000，目前由我估計會採取計算天數。

尾遞歸似乎是我最好的選擇，但我希望這裏有人可能知道如何使用尾遞歸編程這個關係，因爲我並不真正瞭解它。

我在LISP工作，但將開放給使用支持尾遞歸

Answer 1

尾遞歸任何語言只是一種循環表示爲遞歸。當你有一個「分叉」的遞歸定義時，從T（n）到T（n-1）和T（n-2）的初始實現很可能是指數的，那麼T（n -2），T（n-3），T（n-3），T（n-4），使每一步的計算加倍。

訣竅是逆轉計算，以便從T（1）和T（2）建立起來。這隻需要每個步驟都有恆定的時間，所以整體計算是線性的。

開始

(let ((n 2) 
     (t-n 2) 
     (t-n-1 1)) 
    …) 

讓我們用一個do循環更新：

(do ((n 2 (1+ n)) 
    (t-n 2 (+ t-n (* n t-n-1))) 
    (t-n-1 1 t-n)) 
    …) 

現在你只需要停下來，當你達到你想要的n：

(defun telephone-number (x) 
    (do ((n 2 (1+ n)) 
     (t-n 2 (+ t-n (* n t-n-1))) 
     (t-n-1 1 t-n)) 
     ((= n x) t-n))) 

要完成後，檢查你的輸入：

(defun telephone-number (x) 
    (check-type x (integer 1)) 
    (if (< x 3) 
     x 
     (do ((n 2 (1+ n)) 
      (t-n 2 (+ t-n (* n t-n-1))) 
      (t-n-1 1 t-n)) 
      ((= n x) t-n)))) 

此外，編寫測試和添加文檔這是什麼以及如何使用它。這尚未經過測試。

當寫這個尾遞歸，遞歸你用新值：

(defun telephone (x) 
    (labels ((tel-aux (n t-n t-n-1) 
      (if (= n x) 
       t-n 
       (tel-aux (1+ n) 
          (+ t-n (* n t-n-1)) 
          t-n)))) 
    (tel-aux 2 2 1))) 

當尾遞歸優化，這種鱗片像環（但常數因子可能會有所不同）。請注意，Common Lisp不要求尾部呼叫優化。