2

私は現在、多くの再帰関数を使用していますが、そのような関数がどのように機能するかを理解するのにまだ苦労しています (2 行目 (つまり| n==0 = 1) には慣れていますが、最後の行 (つまり ) にはあまり慣れていません| n>0 = fac (n-1) * n)。

fac :: Int -> Int
fac n
    | n==0 = 1
    | n>0  = fac (n-1) * n
4

4 に答える 4

8

再帰的アルゴリズムは、数学的帰納法と非常に密接に関連しています。おそらく、一方を研究することで、もう一方をよりよく理解するのに役立つでしょう。

再帰を使用するときは、次の2つの重要な原則に留意する必要があります。

  • 規範事例
  • 帰納的ステップ

帰納的ステップは、依存するすべてのものがすでに正しく計算されていることを前提としているため、多くの場合、最も難しい部分です。この信仰の飛躍を成し遂げることは難しいかもしれませんが（少なくともそれを理解するのにしばらく時間がかかりました）、それは私たちが私たちの機能に前提条件を持っているからです。これらの前提条件（この場合、n非負の整数）は、帰納的ステップと基本ケースが常に真になるように指定する必要があります。

ベースケースも難しい場合があります。たとえば、階乗N!がN * (N-1)!であることがわかっていますが、はしごの最初のステップをどのように正確に処理しますか？（この場合、簡単に定義できます0! := 1。この明示的な定義は、帰納的ステップの再帰的適用を終了する方法を提供します。）

この関数のタイプ仕様とガードパターンは、ベースケースに到達するまで誘導ステップを繰り返し使用できることを保証する前提条件を提供していることがわかりますn == 0。前提条件を満たせない場合、帰納的ステップの再帰的適用はベースケースに到達できず、計算が終了することはありません。（まあ、それはメモリが不足したときになります。:)

特に関数型プログラミング言語の場合の複雑な要因の1つは、ここにあるように、末尾呼び出しまたは末尾再帰を使用するバリアントを使用して、すべての「単純な」再帰関数を書き直したいという非常に強い願望です。

この関数はそれ自体を呼び出し、その結果に対して別の操作を実行するため、次のようなコールチェーンを構築できます。

fac 3        3 * fac 2
  fac 2      2 * fac 1
    fac 1    1 * fac 0
      fac 0  1
    fac 1    1
  fac 2      2
fac 3        6

その深い呼び出しスタックはメモリを消費します。ただし、再帰呼び出しを行った後、関数が状態を変更しないことに気付いたコンパイラーは、再帰呼び出しを最適化することができます。これらの種類の関数は通常、アキュムレータ引数を渡します。仲間のスタッカーには非常に良い例があります：Haskellの末尾再帰

factorial 1 c = c
factorial k c = factorial (k-1) (c*k)

この非常に複雑な変更:)は、前のコールチェーンが次のように変換されることを意味します。

fac 3 1       fac 2 3
  fac 2 3     fac 1 6
    fac 1 6   6

（ネストは表示のためだけにあります。ランタイムシステムは実際には実行の詳細をスタックに保存しません。）

これは、の値に関係なく、一定のメモリで実行されるnため、この最適化により、「不可能な」アルゴリズムを「可能な」アルゴリズムに変換できます。この種の手法はchar *、CプログラミングやyieldRubyプログラミングで頻繁に見られるように、関数型プログラミングで広く使用されています。

于 2011-05-14T02:25:32.643 に答える
4

あなたが書くとき、それは警備員| condition = expressionを紹介します。ガードは、真の条件が見つかるまで上から下に順番に試行され、対応する式は関数の結果です。

これは、nがゼロの場合、結果は1、そうでない場合n > 0、結果が。であることを意味しfac (n-1) * nます。が負の場合n、不完全なパターン一致エラーが発生します。

使用する式を決定したら、再帰呼び出しに置き換えて、何が起こっているかを確認するだけです。

fac 4
(fac 3) * 4
((fac 2) * 3) * 4
(((fac 1) * 2) * 3) * 4
((((fac 0) * 1) * 2) * 3) * 4
(((1 * 1) * 2) * 3) * 4
((1 * 2) * 3) * 4
(2 * 3) * 4
6 * 4
24
于 2011-05-14T02:13:33.960 に答える
2

特に再帰のより複雑なケースの場合、メンタルヘルスを救う秘訣は、再帰呼び出しに従わず、「正しいことをする」と仮定することです。たとえば、あなたの fac の例では、 を計算したいと考えていますfac n。すでに結果が得られていると想像してくださいfac (n-1)。次に、計算するのは簡単fac nです: n を掛けるだけです。しかし、誘導の魔法は、この推論が実際に機能することです (再帰を終了するために適切な基本ケースを提供する限り)。たとえば、フィボナッチ数の場合、基本ケースが何であるかを見て、n より小さいすべての数の関数を計算できると仮定します。

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

見る？を計算したいfib n。fib (n-1)と を知っていれば簡単ですfib (n-2)。しかし、それらを計算することができ、再帰の「より深いレベル」が「正しいこと」を行うと単純に仮定することができます。したがって、それらを使用するだけで機能します。

現在、多くの値が非常に頻繁に再計算されるため、この関数を記述するより良い方法があることに注意してください。

ところで：「最良の」書き方facはfac n = product [1..n].

于 2011-05-14T10:54:38.450 に答える
1

何があなたを投げますか？多分警備員（|）は物事を混乱させています。

ガードは、ifのチェーン、またはswitchステートメント（1つだけが実行でき、結果に直接評価されます。一連のタスクを実行せず、確かに副作用はありません。評価するだけです）と大まかに考えることができます。値に）

命令型のような疑似コードをパンするには...

Fac n:
   if n == 0: return 1
   if n > 0: return n * (result of calling fac w/ n decreased by one)

他のポスターによるコールツリーが役立つようです。自分に好意を持って、本当にそれを歩きます

于 2011-05-14T02:14:49.200 に答える