0

次のように機能するScheme（R5RS）で関数を作成する必要があります：（power-close-to bn）そして、「e」と呼ばれる整数を返す必要があります：b ^ e> n with b、eおよびn 個の整数。

(power-close-to 2 10) 4 は b^e > n となる最初の整数であるため、4 を返さなければなりません。この関数を反復的に作成しましたが、再帰的な形。これは私のコードです：

(define e 0)
(define (power-close-to b n)
  (for ((e (< (expt b e) n))
    (+ e 1))
    e))

しかし、試してみると、Scheme は次のエラーを出します: "for: undefined;" 私のSchemeは「for」の手順を知らないようですが、インターネット上の複数のSchemeコードで見たので、私の場合、彼が「for」を知らないと言った理由がわかりません。

ご協力いただきありがとうございます！

編集：再帰的にしようとしましたが、これは私がやった方法ですが、まだ反復的であると思います。再帰的にする方法が本当にわかりません。

(define e 0)
(define (power-close-to b n)
  (if (< (expt b e) n)
    (and (set! e (+ e 1)) (power-close-to b n)) 
    e))

私もこれを試しましたが、試してみると、何も出力されず、終了しません（ただし、これは再帰的です（と思います））

(define e 0)
(define (power-close-to b n)
  (if (< (expt b e) n)
    (* b (power-close-to b n)) 
    e))
4

2 に答える 2

2

だれかが、Scheme の再帰手続きを反復手続きに変換するように頼んだ場合、一般的には、言語のループ構造を使用する必要があるということではなく、末尾再帰を使用する必要があることを意味します。

すべての Scheme インタプリタがループを提供しているわけではないことに注意してforください (ほとんどがdoループを提供しますが、それが演習のポイントではないと思います)。あなたが報告しているエラーは、インタープリターにfor構造がないことを意味するため、プロシージャを末尾再帰的な方法で書き直すことが期待される可能性は十分にあります。私が言いたいことの例を挙げましょう。これは再帰階乗です。

(define (fac n)
  (if (zero? n)
      1
      (* n (fac (sub1 n)))))

(fac 10)
=> 3628800

これで、反復プロセスを生成するような方法で同じプロシージャを作成できます(構文的には再帰を使用しますが)。

(define (fac n acc) ; now the result is stored in the accumulator parameter
  (if (zero? n)     ; when recursion ends
      acc           ; return accumulator
      (fac (sub1 n) (* n acc)))) ; else update accumulator in each iteration

(fac 10 1) ; initialize the accumulator in the right value
=> 3628800

ポイントは何ですか、あなたは尋ねますか？プロシージャの 2 番目のバージョンは末尾再帰形式で記述されているため (再帰呼び出しが終了した後は何もする必要がないことに注意してください)、末尾呼び出しの最適化と呼ばれるコンパイラのトリックが開始され、プロシージャは定数スタック空間で実行されます。他の非関数型言語のループとして効率的 - 再帰呼び出しを非常に安価にします。power-close-toここで、末尾呼び出しを使用するように実装を作成してみてください。

于 2013-10-04T16:45:00.777 に答える