1

ラケットで、私は次の関数を定義し、それが末尾再帰であるかどうか疑問に思っています:

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

私の質問はほぼこのようなものですが、投稿の品質基準を満たすために何か他のものを書かなければなりません。実際、投稿の品質基準が何であるかわかりません。

4

4 に答える 4

5

これは、前の質問と実質的に同じです。はい、これは末尾再帰です。関数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))

その場合、再帰呼び出しが末尾位置にないことは明らかです。再帰が返された後、再帰の結果に 1 を追加するという操作が実行されるためです。

于 2013-03-18T01:01:40.473 に答える
1

これは、コードをフレーム変更バージョンに変換した疑似コード (実際には 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-18T15:09:16.397 に答える
0

への唯一の呼び出しfooは末尾の位置にあるため、その関数は末尾再帰に見えます。

于 2013-03-18T01:00:53.943 に答える
0

セクション 11.20、Scheme R6RSの 59 ページでは、テール コールについて説明し、基本的な Scheme 構文形式のテール コールの位置を示していますif。lambda

foowithinへの呼び出しfooは末尾の位置にあります。（内側ifテール位置、外側ifテール位置、lambdaテール位置にあるため。）

于 2013-03-18T04:51:19.483 に答える