是這個函數尾遞歸嗎？

在球拍，我定義了下面的函數，我想知道它是否是尾遞歸：是這個函數尾遞歸嗎？

(define foo 
    (λ (c m s1 s2) 
     (if (< c m) 
      (if (= (modulo m c) 0) 
       (foo (+ c 1) m (+ s1 c) s2) 
       (foo (+ c 2) m s1 (+ s2 c))) 
      (cons s1 s2))))

我的問題實際上是這樣的，但我必須寫別的東西來滿足我後質量標準。實際上，我不知道我的職位質量標準是。

來源

2013-03-18 象嘉道

這與您之前的問題基本相同。是的，這是尾遞歸：當函數foo發生遞歸調用時，它處於尾部位置。意思是：在執行遞歸調用之後，沒有其他任何事情要做，那個執行分支結束了。 (cons s1 s2)部分是遞歸的基本情況，所以它不計數。爲了更清楚地看到它的foo程序是相同的：

(define (foo c m s1 s2) 
    (cond ((>= c m) 
     (cons s1 s2))     ; base case of recursion 
     ((= (modulo m c) 0) 
     (foo (+ c 1) m (+ s1 c) s2)) ; recursive call is in tail position 
     (else 
     (foo (+ c 2) m s1 (+ s2 c))))) ; recursive call is in tail position

我們先來看看什麼是不一尾遞歸的例子。例如，如果第二if的後事件部分被定義如下：

(+ 1 (foo (+ c 1) m (+ s1 c) s2))

那麼顯然遞歸調用不會在尾部位置，因爲遞歸返回之後進行的操作：將一個到遞歸的結果。

來源

2013-03-18 01:01:40

我很難想象解釋器在這種情況下如何重複使用與最優化相同的調用堆棧。 – 2013-03-18 14:42:30

在我上面的實現中，它更加清晰，將'foo'的尾調用看作一個奇怪的'for for'，其中參數是每次迭代中更新的變量，第一個條件是循環的退出條件。然後很容易看到，相同的堆棧幀在調用之間重複使用 - 只有參數值需要更新 – 2013-03-18 15:05:01

非常感謝。 – 2013-03-18 15:12:50

對foo的唯一調用位於尾部位置，因此該函數看起來是遞歸給我的。

來源

2013-03-18 01:00:53

見11.20，中Scheme R6RS 59頁描述了尾調用並顯示基本計劃語法形式的尾調用位置，像if和lambda

你的內foo調用foo在尾部位置。（因爲他們是在內部if尾位置，外if尾位置和lambda尾位置）

來源

2013-03-18 04:51:19 GoZoner

下面是一個僞代碼（Common Lisp的實際上）代碼的翻譯框架變異版本：

(defun foo (c m s1 s2) 
    (prog 
     ((c c) (m m) (s1 s1) (s2 s2)) ; the frame 
     BACK 
     (if (< c m) 
      (if (= (modulo m c) 0) 
       (progn 
       (psetf s1 (+ s1 c)  ; set! 
         c (+ c 1)) ; in parallel 
       (go BACK)) 
       (progn 
       (psetf s2 (+ s2 c)  ; set! 
         c (+ c 2)) ; in parallel 
       (go BACK))) 
      (return-from foo (cons s1 s2))))))

由於在每次尾部呼叫後沒有更多的事情可做，我們可以只需(go BACK)。

來源

2013-03-18 15:09:16

是這個函數尾遞歸嗎？

回答

相關問題