0

もともと私は「末尾再帰ベクトルを理解する->リスト回答」という1つの質問を投稿しましたが、これは追加の質問です。スキームに関する私の一般的な理解は本当に漠然としています。だから私は今、さらにいくつかの質問があります:

;;;;;; original code ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define vector->list:rec
 (lambda (v)
  (letrec ((helper
      (lambda (vec r i)
        (if (< i 0) 
            r
            (helper vec (cons (vector-ref v i) r) (- i 1))  ;; Q1
            ))))
    (if (> (vector-length v) 0)  ;; line 9
      (helper v                  ;; line 10 
              (cons (vector-ref v (- (vector-length v) 1)) '()) 
              (- (vector-length v) 2))
      '()))))

Q2) 末尾再帰は、私を理解するのを非常に困難にします。彼らが末尾再帰を必要とする理由を理解し、基本的に反復を避けるためにそれを使用するので、ヘルパーを中間ルーチンとして使用します..各反復をスタックに入れるのを避けることができます....このようなもの。そして、次のような letrec/lambda 式:

;;;;;;;;;letrec/lambda express;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (some-procedure...)
  (letrec ((helper (lambda (x) 
               ...
               (if some-test?
                   (helper ...))))) ; recursive call --- Q2-1
       ...
    (helper ...)  ; call to recursive local procedure  ---- Q2-2
  ...))

行 Q2-2: なぜこれが「ローカル再帰的」なのですか? 「ローカル」は、中間ルーチンの再帰的なように聞こえます...ここでの中間は、私の理解を意味します..

[私の混乱] 末尾再帰は、プログラム全体の最後までそれ自体を反復 (呼び出し) すべきではありません。今までの私の理解に基づいて...ヘルパーはletrec式にカプセル化された中間ルーチンのためのものです..?.)ので、最後に自分自身を呼び出すだけです.(私の意味..: letrecの外..?).

4

1 に答える 1

2

まず、あなたの例を少し書き直したでしょう：

(define (vector->list-iter v)  
  (let loop ((i (- (vector-length v) 1)) (acc '()))
    (if (< i 0)
        acc
        (loop (- i 1) (cons (vector-ref v i) acc)))))

違いを確認するために、非末尾再帰バージョンを作成します。

(define (vector->list-rec v)
  (define len (vector-length v))
  (let loop ((i 0))
    (if (>= i len)
        '()
        (cons (vector-ref v i) (loop (+ i 1))))))

Scheme にはループ機能はありません。前のステップでやるべきことがもっとあるので、スタックを成長させないのは再帰と再帰だけであり、末尾再帰と呼ばれます。

ベクトルは任意の方法で反復できるため (O(1) アクセスです)、最後から最初または最初から最後に反復できます。リストは最後から最初にしか作成できないため、非末尾再帰バージョンはcons、最初の要素を除くリスト全体を作成するまで、最初の要素には適用されません。これにより、ベース ケースにヒットしたときに 5 つの要素のベクトルが 5 つの継続を持つようになります。大きなベクトルの場合、スタック オーバーフローが発生する可能性があります。

最初の例では、最初に最後の要素で構成されるリストを作成し、それが完了すると再帰します。コンスは再帰の前に行われたので、何もコンスする必要はありません。このように対処できるすべての問題ではありません。リストをコピーしたいとします。最初から最後まで反復できますが、最初から最後まで構築できます。ミューテーションや余分なコンシングがなければ、そのようなプロシージャを末尾再帰にする方法はありません。

于 2014-05-09T12:30:34.247 に答える