scheme - 再帰指数関数の反復バージョン

Question

基本的に、すでに作成した次の関数の反復バージョンを実行する必要があります。

(define (expo base e)
  (cond ((or (= base 1) (= e 0)) 1)
        (else (* base (expo base (- e 1))))))

方法がわからないので、助けが必要です（ラケット/スキームで））

Answer 1

このような再帰関数を反復に変換する一般的なパターンは、アキュムレータを使用することです

(define (expo base e)
   (define (go base e accum)
      (if (or (= base 1) (= e 0))
          accum
          (go base (- e 1) (* accum base)))) ; Now this is tail recursion
    ???)

の適切な初期値でWhere???を呼び出します。再帰呼び出しが以前は別の呼び出し (つまり) の中にあったことに注意してください。しかし、今は最後に呼び出されています。これにより、プログラムを一定のスペースで実行できます。goaccum*

Answer 2

アキュムレータで結果を渡すだけです。そのためには、追加のパラメーターが必要です。たとえば、内部ヘルパー プロシージャを使用するなど、いくつかの方法があります。

(define (expo base e)
  ; helper procedure
  (define (iter e acc)
          ; now the base case returns the accumulator
    (cond ((or (= base 1) (= e 0)) acc) 
          ; see how the result is accumulated in the parameter
          (else (iter (- e 1) (* base acc)))))
  ; at the beginning, initialize the parameter in the right values
  (iter e 1))

または、同じ効果に名前付きletを使用できます。

(define (expo base e)
  (let iter ((e e) (acc 1))
    (cond ((or (= base 1) (= e 0)) acc)
          (else (iter (- e 1) (* base acc))))))

再帰的な手続きとプロセスを区別するのは良いことです。上記の実装はどちらも再帰的な手続きです: 構文的に、それらが自分自身を呼び出していることは簡単にわかります。しかし、それらが生成するプロセスは反復的です。それらは末尾再帰スタイルで書かれているため、各再帰呼び出しが終了した後は何もする必要がなく、コンパイラーは再帰呼び出しを最適化し、すべての実用的な目的のために、それを反復ループ。

Scheme で反復がどのように機能するかをよりよく理解するには、素晴らしい SICP の本でこの主題について詳しく読んでください。

Answer 3

他の人が指摘したように、末尾再帰アルゴリズムは反復アルゴリズムです。しかし、おそらく明示的な反復アルゴリズムが必要でしょうか?

(define (expo base exp)
  (do ((acc   1 (* acc base))
       (exp exp (- exp 1)))
      ((= 0 exp) acc))))

-の条件を追加することもできます(= base 1)が、書かれているように、これは簡単です。expは整数であると仮定します。