4

スキームでテール反発力関数をどのように実装するのか疑問に思いましたか？

スキーム用に定義された再帰的なものがあります：

(define power-is-fun
  (lambda (x y)
    (cond [(= y 0)
           1]
          [(> y 0)
           (* (power-is-fun x (- y 1)) x)])))

しかし、私はもう一方がどうあるべきかを完全に理解することはできません。

4

3 に答える 3

5

答えは似ています、あなたはただパラメータとして蓄積された結果を渡す必要があります：

(define power-is-fun
  (lambda (x y acc)
    (cond [(= y 0)
           acc]
          [(> y 0)
           (power-is-fun x (- y 1) (* x acc))])))

このように呼び出すと、の初期値がacc次1のようになります（このためのヘルパー関数を作成できるため、1毎回渡すことを覚えておく必要はありません）。

(power-is-fun 2 3 1)
> 8

再帰的プロシージャを末尾再帰に変換するためのいくつかの一般的なポインタ：

  • これまでに蓄積された結果を保持するために、関数にパラメーターを追加します
  • プロシージャを最初に呼び出すときに、アキュムレータの初期値を渡します。通常、これは、「通常の」（末尾再帰ではない）再帰でベースケースに返された値と同じです。
  • 再帰のベースケースでアキュムレータを返します
  • 再帰ステップで、累積された結果を新しい値で更新し、それを再帰呼び出しに渡します
  • そして最も重要なのは、再帰を呼び出すときが来たら、それを「追加の作業」を実行しない最後の式として呼び出すようにしてください。たとえば、元のコードでは、呼び出し後power-is-funに乗算を実行しましたが、末尾再帰バージョンでは、呼び出しpower-is-funはプロシージャを終了する前に発生する最後の処理です。
于 2012-05-17T11:56:08.123 に答える
2

ちなみに、整数のべき乗を実装するより速い方法があります。x何度も何度も乗算するのではなくy（これによりO（y）になります）、時間計算量がO（log y）であるアプローチがあります。

(define (integer-expt x y)
  (do ((x x (* x x))
       (y y (quotient y 2))
       (r 1 (if (odd? y) (* r x) r)))
      ((zero? y) r)))

do（私が知っている多くのSchemersがそうしているように）嫌いな場合は、明示的にテール再帰するバージョンがあります（letもちろん、namedを使用して記述することもできます）。

(define (integer-expt x y)
  (define (inner x y r)
    (if (zero? y) r
        (inner (* x x)
               (quotient y 2)
               (if (odd? y) (* r x) r))))
  (inner x y 1))

（ちなみに、適切なスキームの実装では、両方のバージョンをまったく同じコードにマクロ展開する必要があります。また、オスカーのソリューションと同様に、ここでのみアキュムレータを使用しますr（「結果」の略）。）

于 2012-05-17T23:51:06.337 に答える
1

オスカーのアドバイスのリストは素晴らしいです。

反復（別名線形再帰）およびツリー再帰プロセスのより詳細な処理が必要な場合は、SICPの優れた処理をお見逃しなく：

http://mitpress.mit.edu/sicp/full-text/book/book-ZH-11.html#%_sec_1.2

于 2012-05-17T12:18:30.640 に答える