scheme - このスキームコードの末尾再帰はありますか？

Question

編集：みんなに感謝します。私はこの言語に慣れていないので（2日前に使い始めたばかりです）、そのため、condsに慣れていません。時間があれば書き直すかもしれませんが、基本的なロジックが正しいことを確認したかっただけです。再度、感謝します！

私の割り当ては、リストxと要素nの2つのパラメーターのみを使用して、リストからn番目の要素1 <= n<=listlengthを削除する末尾再帰関数を作成することです。したがって、（remove 1'（abcd））は（bcd）を返します。私は次のように書いていますが、それが実際に末尾再帰であることを確認したいと思います。私が曖昧なのは、再帰呼び出しをIFステートメント内にネストできるかどうかだけです。

(define (remove n x)
  ; if n is 1, just return the cdr 
  (if (and (not (list? (car x))) (= n 1))
     (cdr x)
     ; if the car is not a list, make it one, and call recursively
     (if (not (list? (car x)))
        (remove (- n 1) (cons (list (car x)) (cdr x)))
        ; if n !=1, insert the cadr into the list at the car.
        ; Else, append the list at the car with the cddr
        (if (not(= n 1))
           (remove (- n 1) (cons (append (car x) (list(cadr x))) (cddr x)))
           (append (car x) (cddr x))))))

Answer 1

はい、プロシージャは末尾再帰です。つまり、再帰呼び出しが実行される場合は常に、その特定の実行ブランチで最後に発生し、再帰が戻った後は何もする必要がありません。したがって、再帰呼び出しは次のようになります。末尾位置で。

condこれは、ネストされたsの代わりにを使用してプロシージャを書き直すと明確にわかりifます。ここでは、実行のすべてのブランチがベースケースまたは再帰ケースのいずれかにつながり、すべての再帰呼び出しがテール位置にあることがわかります。

(define (remove n x)
         ; base case #1
  (cond ((and (not (list? (car x))) (= n 1))
         ; return from base case, it's not recursive
         (cdr x))
         ; recursive case #1
        ((not (list? (car x)))
         ; recursive call is in tail position
         (remove (- n 1) (cons (list (car x)) (cdr x))))
         ; recursive case #2
        ((not (= n 1))
         ; recursive call is in tail position
         (remove (- n 1) (cons (append (car x) (list(cadr x))) (cddr x))))
         ; base case #2
        (else
         ; return from base case, it's not recursive
         (append (car x) (cddr x)))))

特別なフォームの結果/代替部分がif末尾再帰と見なされる理由のより技術的な説明については、アルゴリズム言語スキームに関する改訂^ 7レポートの現在のドラフトのセクション3.5を参照してください-言語仕様、ここにありますpdfファイルへのリンク（本質的に同じ考慮事項がR5RSに適用されますが、R7RSでより詳細に説明されているだけです）。特に：

次の式のいずれかがテールコンテキストにある場合、⟨テール式⟩として示されているサブ式はテールコンテキストにあります

..。

(if ⟨expression⟩ ⟨tail expression⟩ ⟨tail expression⟩)

(if ⟨expression⟩ ⟨tail expression⟩)

Answer 2

構文形式の末尾再帰位置に関するSchemeの仕様は次のとおりです。