scheme - これを末尾再帰関数に変えることはできますか?

Question

HtDPを通過すると、次の問題に遭遇しました。関数乗算を設計します。自然数 n を消費し、* を使用せずに任意の数 x で乗算します。

これは私が思いついたものです：

(define (multiply n x)
  (cond
    [(= x 1) n]
    [else (+ n (multiply n (- x 1)))]))

動作しますが、最善の解決策ではないと考えています。私の理解に基づいて、これは for ループとして解決できるため、末尾再帰にする必要があります。

Answer 1

他の人が関数を末尾再帰にする方法を示したので、これは、指定したものよりもはるかに高速な2つの正の整数を乗算する関数の代替バージョンです。関数がどのように機能するかわかりますか？

(define (times x y)
  (let loop ((x x) (y y) (z 0))
    (if (zero? x) z
      (loop (quotient x 2) (+ y y)
            (if (odd? x) (+ y z) z)))))

Answer 2

末尾再帰ソリューションの重要なポイント: 不変式 n * x + r = const を維持します。この場合、x がゼロの場合、r には n * x が含まれます。

(define (iter-mul n x r)
  (cond ((= x 0) r)
        (else (iter-mul n (- x 1) (+ r n))))) 

次のように使用できます。

(define (mul n x) (iter-mul n x 0))

Answer 3

おそらく最もエレガントではありませんが、これは少なくとも末尾再帰です:

(define (acc a n x)
  (if(= x 0)
    a
    (acc (+ a n) n (- x 1))))

(define (multiply n x)
  (acc 0 n x))

Answer 4

このプロシージャは、結果を格納するためのアキュムレータ パラメータを使用して、末尾再帰に簡単に変換できます。以下は and に対して定義されてn >= 0おりx >= 0、ヘルパー プロシージャを明示的に定義したり、プロシージャに別のパラメータを追加したりする必要がないように、名前付きlet (loopは末尾再帰プロシージャであり、ループ コンストラクトではありません) を使用しています。方法は次のとおりです。

(define (multiply n x)
  (let loop ((acc 0)
             (x x))
    (cond
      [(= x 0) acc]
      [else (loop (+ n acc) (- x 1))])))

また、コードにバグがあることにも注意してください。実行してみてください(multiply 1 0)- 無限ループです。