21

末尾再帰を使用せずに無名関数で再帰を行うにはどうすればよいですか?

例 (Vanderhart 2010、p 38 から):

(defn power
  [number exponent]
  (if (zero? exponent)
    1
    (* number (power number (- exponent 1)))))

これを匿名関数として実行したいとしましょう。そして、何らかの理由で末尾再帰を使いたくありませんでした。どうすればいいですか？例えば：

( (fn [number exponent] ......))))) 5 3)
125

これにloopを使用できますか、または loop はrecurでのみ使用できますか?

4

5 に答える 5

47

fn特別な形式は、再帰のために内部的に使用できる名前を提供するオプションを提供します。

(doc fn)
;=> (fn name? [params*] exprs*)

したがって、名前として「power」を追加して、例を完成させます。

(fn power [n e]
  (if (zero? e)
    1
    (* n (power n (dec e)))))

末尾の位置で再帰が発生した場合でも、現在のスタック フレームを置き換えるように最適化されません。Clojure では、loop/recurとでそれを明示する必要がありtrampolineます。

于 2012-05-07T23:57:54.230 に答える
18

他の回答が指摘しているように、Clojureには匿名関数の「命名」に対する構文サポートがあることを私は知っています。ただし、この問題を解決するための第一原理アプローチを示したいと思います。これは、プログラミング言語の特殊な構文の存在に依存せず、一次手続き (ラムダ) を使用する任意の言語で機能するものです。

原則として、再帰関数呼び出しを行う場合は、関数の名前を参照する必要があるため、「匿名」(つまり、名前のない関数) を使用して再帰を実行することはできません ... Y-Combinatorを使用しない限り. これがClojureでどのように機能するかの説明です。

例を挙げて使い方を説明します。まず、Y-Combinator可変数の引数を持つ関数で機能する a :

(defn Y [f]
  ((fn [x] (x x))
   (fn [x]
       (f (fn [& args]
              (apply (x x) args))))))

ここで、質問で定義されている手順を実装する無名関数。power明らかに、名前powerはなく、最も外側の関数へのパラメーターにすぎません。

(fn [power]
      (fn [number exponent]
          (if (zero? exponent)
              1
              (* number (power number (- exponent 1))))))

最後に、Y-Combinatorを匿名powerプロシージャに適用し、パラメーターとして渡す方法を次に示します(末尾再帰ではありません) number=5。exponent=3

((Y 
  (fn [power]
      (fn [number exponent]
          (if (zero? exponent)
              1
              (* number (power number (- exponent 1)))))))
 5 3)

> 125
于 2012-05-07T23:40:24.667 に答える
4

fn関数を再帰的に呼び出すために使用できるオプションのname引数を取ります。

例えば：

user> ((fn fact [x]
           (if (= x 0)
               1
               (* x (fact (dec x)))))
       5)
;; ==> 120
于 2012-05-08T00:00:51.903 に答える