1. ホーム
  2. recursion

[解決済み] Schemeにおける再帰的関数

2022-02-15 05:16:01

質問

オブジェクトとベクトルを受け取り、オブジェクトのパラメータに先行するすべてのオブジェクトのリストを返す再帰的な関数を作成する必要があります。

こんな感じで、イテレーションを使ってやってみました。

(define (precedes obj vec)
  (do ((i 1 (+ i 1))
      (list '() (if (eqv? obj (vector-ref vec i))
            (cons(vector-ref vec (- i 1)) list)
            list)))
    ((= i (vector-length vec)) list))
)

が、再帰を使って同じことをするにはどうしたらいいのかわからず、かなり困っています。再帰的に呼び出しながら、どうやってベクターを通してインクリメントし続けることができるのか、混乱しています。今のところ、私が持っているのはこれだけです。

(define (precedes2 obj vec)
  (define list '())
  (if (eqv? obj (vector-ref vec i))
      (cons(vector-ref vec(- i 1)) list)
      list)))

if文に関しては以前と同じロジックを使おうと思ったのですが、更新されたベクトルで同じ関数を今どのように呼び出すのかがわかりません。何か手助けがあれば助かります。

どのように解決するのですか?

あなたは、反復的な実装から再帰的な実装に移行するという興味深い立場にいます。通常、人々は逆の方向に進みます。 幸いなことに する -ループから再帰処理への移行は非常に簡単です。 一般に する ループは次のように書き換えることができる。

(do ((i i-init i-step)
     (j j-init j-step)
     ...)
    (test result)
  body)

になる

(define f (i j ...)
  (cond
    (test result)
    (else body (f i-step j-step ...))))

(f i-init j-init ...)

その訳は、通常、名前付きletを使って書かれますが。

(let f ((i i-init)
        (j j-init)
        ...)
  (cond
    (test result)
    (else body (f i-step j-step ...))))

つまり、(コードのテストはしていませんが)あなたのオリジナルの関数は

(define (precedes obj vec)
  (do ((i 1 (+ i 1))
      (list '() (if (eqv? obj (vector-ref vec i))
            (cons(vector-ref vec (- i 1)) list)
            list)))
    ((= i (vector-length vec)) list))
)

は、次のようになります。

(define (precedes obj vec)
  (let loop ((i 1)
             (list '()))
    (cond
      ((= i (vector-length vec)) list)
      (else (loop (+ i 1)
                  (if (eqv? obj (vector-ref vec i))
                      (cons (vector-ref vec (- i 1)) list)
                      list))))))