recursion - Schemeの末尾再帰関数

Question

私はクリスマスのテストのために勉強していて、いくつかのサンプル試験の質問をしています、私は少し困惑しているこれに出くわしました

通常の再帰は問題なく実行できますが、末尾再帰を使用して同じものを作成する方法に頭を悩ませることはできません。

通常版：

    (define (factorial X)
      (cond
            ((eqv? X 1) 1)
            ((number? X)(* X (factorial (- X 1))))))

score 24 · Accepted Answer

関数が末尾再帰であるためには、関数が戻った後、その値を返す以外に何もする必要はありません。つまり、再帰ステップで最後に発生するのは、関数自体の呼び出しです。これは通常、回答を追跡するためのアキュムレータパラメータを使用して実現されます。

(define (factorial x acc)
  (if (zero? x)
      acc
      (factorial (sub1 x) (* x acc))))

上記のプロシージャは、最初は次の1ようにアキュムレータとして呼び出されます。

(factorial 10 1)
=> 3628800

基本ケースに達すると累積値が返さaccれ、再帰呼び出しの各ポイントでパラメーターが更新されることに注意してください。プロシージャにパラメータを1つ追加する必要がありましたが、これは、内部プロシージャまたは名前付きプロシージャを定義することで回避できますlet。たとえば、次のようになります。

(define (factorial x)
  (let loop ((x x)
             (acc 1))
    (if (zero? x)
        acc
        (loop (sub1 x) (* x acc)))))

1 に答える 1