2

関数型プログラミング言語のコースを受講していますが、「引数としての関数」のコンテキスト内での再帰を理解するのに苦労しています

fun n_times(f , n , x) = 
    if n=0
    then x
    else f (n_times(f , n - 1 , x))

fun double x = x+x;

val x1 = n_times(double , 4 , 7);

the value of x1 = 112

これは 'x' 'n' 回 2 倍になるので、7 倍 4 回 = 112

リストに数値を追加するなどの単純な再帰パターンは理解できますが、関数の「べき乗」は理解できますが、この関数「n_times」が自分自身を呼び出すことによってどのように評価されるかを理解できません。この機能の仕組みを説明できますか?

scala の理解を深めるために (関数型プログラミングと共に) このコースを受講しているので、scala でタグ付けしました。

4

4 に答える 4

6

nが0の場合、xが返されます。

それ以外の場合は、f (n_times(f , n - 1 , x))が返されます。

何をしn_timesますか？、times、または同等の結果で呼び出した結果を受け取ります：f（calling times on ）の結果で呼び出します。xnfn_times(f, n - 1, x)f n-1x

fたとえば、iと呼ぶことで注意してください。

f3回呼び出す：f(f(f(x)))

f2回呼び出す：f(f(x))

于 2013-01-31T22:53:13.853 に答える
4

手で伸ばすだけ。n_times nxスペースを節約するために電話します。

コア操作は

nx(f, n, x) -> f( nx(f, n-1, x))

で終了する

nx(f, 0, x) -> x

もちろん、

nx(f, 1, x) -> f( nx(f, 0, x) ) -> f( x )
nx(f, 2, x) -> f( nx(f, 1, x) ) -> f( f( x ) )
...
nx(f, n, x) -> f( nx(f,n-1,x) ) -> f( f( ... f( x ) ... ) )
于 2013-01-31T22:54:59.027 に答える
3

関数n_timesには、そうでない場合は基本ケースがn = 0あり、それ以外の場合は誘導ケースがあります。基本ケースで終了するまで、誘導ケースを再帰します。

以下に、トレースの例を示します。

   n_times(double, 4, 7)
~> double (n_times(double, 3, 7)) (* n = 4 > 0, inductive case *)
~> double (double (n_times(double, 2, 7))) (* n = 3 > 0, inductive case *)
~> double (double (double (n_times(double, 1, 7)))) (* n = 2 > 0, inductive case *)
~> double (double (double (double (n_times(double, 0, 7))))) (* n = 1 > 0, inductive case *)
~> double (double (double (double 7))) (* n = 0, base case *)
~> double (double (double 14)) 
~> double (double 28)
~> double 56
~> 112
于 2013-01-31T22:57:33.007 に答える
0

これは、すでに知っていることを考える再帰と同じですが、高階関数という別の概念が混ざっているだけです。

n_times は関数 (f) をパラメーターとして取得するため、n_times は高階関数であり、この f 関数を体に適用することができます。事実上、それが彼の仕事であり、fn 回を x に適用します。

では、どのように fn 回を x に適用するのでしょうか? n-1回適用した場合

n_times(f , n - 1 , x)

、もう一度申請します。

f (n_times(f , n - 1 , x))

いつものように、再帰を停止する必要があります。つまり、x の n=0 の場合です。

于 2013-02-01T14:21:05.360 に答える