3

そのため、再帰の概念についてはかなり理解していますが、実装によっては本当につまずきます。たとえば、次の単純なフィボナッチ関数を考えてみましょう。

def fib(x):
    if x == 0 or x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)

これにより、フィボナッチ計算がより扱いやすい小さなチャンクに分割されることがわかりました。しかし、それはどのようにして最終結果に至るのでしょうか? 再帰的な場合に返される return とは正確には何ですか? 1を返すまで関数を呼び出し続ける関数への呼び出しを返すだけのようですが、実際の計算/操作を行うことは決してないようです。これを従来の階乗関数と比較してください。

def factorial(n):
    if n == 1:
         return 1
    else:
         return n * factorial(n)

ここで、関数は定義された整数 n を毎回操作していることは明らかですが、フィボナッチ関数は 1 が返されるまで関数自体を操作するだけです。

最後に、Merge Sort アルゴリズムのようなものを導入すると、事態はさらに奇妙になります。つまり、このコードのチャンク:

    middle = int(len(L)/2)
    left = sort(L[:middle], lt)
    right = sort(L[middle:], lt)
    print(left, right)
    return merge(left, right, lt)

left と right は並べ替えを再帰的に呼び出しているように見えますが、print ステートメントは、すべての再帰呼び出しでマージが機能していることを示しているようです。それでは、各再帰呼び出しは何らかの形で「保存」され、マージが最終的にリターン時に呼び出されたときに操作されますか? 秒ごとにますます混乱しています....再帰を強く理解する寸前のように感じますが、再帰呼び出しに対してreturnが正確に何をするかについての私の理解は私の邪魔をしています。

4

3 に答える 3

9

再帰関数がどのように機能するかを理解していないことは非常に一般的ですが、再帰関数は通常の関数とまったく同じように機能するため、関数と戻り値がどのように機能するかを理解していないことを示しています。

print 4

これは、printステートメントが値を出力する方法を知っているために機能します。値が与えられ、それ4を印刷します。

print 3 + 1

ステートメントは、print印刷方法を理解していません3 + 1。3 + 1値ではなく、式です。幸いなことprintに、式が表示されないため、式を印刷する方法を知る必要はありません。Pythonは、式ではなく、物に値を渡します。つまり、Pythonが行うことは、コードが実行されるときに式を評価することです。この場合、その結果、価値4が生み出されます。次に、値4がステートメントに与えられ、printステートメントが喜んで出力します。

def f(x):
    return x + 1

print f(3)

これは上記と非常によく似ています。f(3)は式であり、値ではありません。printそれでは何もできません。Pythonは式を評価して、印刷に与える値を生成する必要があります。これは、名前を調べて、幸いにもステートメントfによって作成された関数オブジェクトを見つけ、引数を使用して関数を呼び出すことによって行われます。def3

これにより、関数の本体がにxバインドされて実行され3ます。の場合と同様にprint、returnステートメントは式に対して何も実行できないx + 1ため、Pythonはその式を評価して値を見つけようとします。x + 1with xbound to3は値を生成し4、それが返されます。

関数から値を返すと、関数呼び出し式の評価がその値になります。したがって、に戻ってprint f(3)、Pythonは式f(3)を値に正常に評価しました4。その後、印刷printできます。

def f(x):
    return x + 2

def g(y):
    return f(y * 2)

print g(1)

ここでも、g(2)は値ではなく式であるため、評価する必要があります。評価g(2)するf(y * 2)と、にyバインドされ1ます。y * 2値ではないので、それを呼び出すことはできませんf。最初にそれを評価する必要があります。これにより、値が生成されます2。次に、を呼び出すことができます。これは、にバインドされfて2戻ります。から返され、内部の式の値になる値に評価されます。これは最終的に返す値を与えるので、式は値に評価され、次に出力されます。x + 2x2x + 24ff(y * 2)ggg(1)4

Pythonを評価するためにドリルダウンすると、f(2)Pythonはすでに評価の途中でありg(1)、何が評価されるかがわかると、適切な場所に戻ることに注意してくださいf(2)。

それでおしまい。これですべてです。再帰関数について特別なことを理解する必要はありません。return関数のこの特定の呼び出しを呼び出した式を、に与えられた値にしreturnます。関数を呼び出す関数を呼び出す関数を呼び出す高レベルの式ではなく、即時式。最も内側のもの。中間の関数呼び出しがたまたまこれと同じ関数であるかどうかは関係ありません。この関数が再帰的に呼び出されたかどうかを知る方法はありませんreturn。ましてや、2つの場合で動作が異なることは言うまでもありません。return 常に常に常にその値を直接に返しますそれが何であれ、この関数の呼び出し元。これらのステップのいずれかを「スキップ」して、値をさらに外側の呼び出し元（再帰関数の最も外側の呼び出し元など）に返すことは決してありません。

しかし、これが機能することを確認fib(3)するために、の評価をより詳細に追跡してみましょう。

fib(3):
    3 is not equal to 0 or equal to 1
    need to evaluate fib(3 - 1) + fib(3 - 2)
        3 - 1 is 2
        fib(2):
            2 is not equal to 0 or equal to 1
            need to evaluate fib(2 - 1) + fib(2 - 2)
                2 - 1 is 1
                fib(1):
                    1 is equal to 0 or equal to 1
                    return 1
                fib(1) is 1
                2 - 2  is 0
                fib(0):
                    0 is equal to 0 or equal to 1
                    return 1
                fib(0) is 1
            so fib(2 - 1) + fib(2 - 2) is 1 + 1
        fib(2) is 2
        3 - 2 is 1
        fib(1):
            1 is equal to 0 or equal to 1
            return 1
        fib(1) is 1
    so fib(3 - 1) + fib(3 - 2) is 2 + 1
fib(3) is 3

より簡潔に、をfib(3)返しますfib(2) + fib(1)。fib(1)1をfib(3)返しますが、それに加えて。の結果を返しますfib(2)。fib(2)戻りますfib(1) + fib(0); これらは両方とも戻り1ます。したがって、それらを合計するとfib(2)、の結果が得られ2ます。に戻ってfib(3)、それはでしたfib(2) + fib(1)、私たちは今それがであると言う立場に2 + 1あり3ます。

あなたが見逃していた重要な点は、fib(0)またはfib(1)が戻る間1、それら1はより高いレベルの呼び出しが合計している式の一部を形成するということでした。

于 2012-09-21T06:41:10.440 に答える
9

この演習を試してください:

fib(0)の値は? fib(1)の値は? それらを書き留めましょう。

fib(0) == 1
fib(1) == 1

これらは「基本ケース」であるため、これはわかっています。これは、fib定義の最初のケースと一致します。

よし、盛り上げよう。fib(2)の値は? 関数の定義を見ると、次のようになります。

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

fib(1)とfib(0)の値がどうなるかはわかっています。どちらも少し仕事をしてから、答えが返ってきます。したがって、fib(2)が最終的に値を与えることがわかります。

わかりました、それをぶつけてください。fib(3)の値は? 定義を見ると、次のようになります。

fib(3) == fib(2) + fib(1)

fib(2)とfib(1)が最終的に数値を計算すること は既にわかっています。fib(2)はfib(1)よりも少し多くの作業を行いますが、どちらも最終的には底を打ち、追加できる数値が得られます。

最初に小さなケースに行き、問題のサイズを大きくすると、サブ問題が処理方法を知っているものであることがわかります。

標準的な高校の数学の授業を経験したことがあるなら、すでにこれに似たものを見たことがあるでしょう: 数学者は「数学的帰納法」と呼ばれるものを使用します。これは、プログラマーがツールとして使用する再帰と同じ考え方です。

于 2012-09-21T06:08:59.420 に答える
3

概念を本当に理解するには、数学的帰納法を理解する必要があります。再帰が理解されると、単純に単純になります。単純な関数を考えてみましょう。

     def fun(a):  
          if a == 0: return a
          else return a + 10

return ステートメントはここで何をしますか? 単純に を返しますa+10。なぜこれがわかりやすいのでしょうか？もちろん、1 つの理由は、再帰がないことです。;) return ステートメントが非常に理解しやすいのは、呼び出されたときに利用可能な a と 10 があるためです。

ここで、sum of n numbers再帰を使用した簡単なプログラムを考えてみましょう。さて、再帰をコーディングする前に重要なことの 1 つは、それが数学的にどのように機能するかを理解しなければならないということです。数値の合計の場合、数値がnわかっている場合はそれを返すことができることがわかっています。それがわからない場合はどうなりますか。さて、項の和を見つけて足します。sumn-1sum + nsumn-2n-1

だから、sumofN(n) = n + sum(n-1)。

さて、終わりの部分です。これが無期限に続くことはありません。なぜならsumofN(0) = 0

それで、

 sumofN(n) = 0, if n = 0,  
            n + sum(n-1) , otherwise

コードでは、これは次のことを意味します。

      def sumofN(n):  
          if n == 0: return 0  
          return n + sum(n-1)

ここで sumofN(10) と呼ぶとします。返します10 + sumofN(9)。私たちは10私たちと一緒にいます。他の用語はどうですか。他の関数の戻り値です。つまり、その関数が戻るまで待ちます。ここでは、呼び出される関数はそれ自体であるため、sumofN(9) が戻るまで待機します。そして、9 + sumofN(8) に達すると、sumofN(8) が戻るまで待機します。

実際に起こることは

10 + sumofN(9) 、つまり
10 + 9 + sumofN(8) 、つまり
10 + 9 + 8 + sumofN(7) .....

最後に sumofN(0) が返されると、

10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0 = 55

この概念は、再帰を理解するために必要なすべてです。:)。では、マージソートはどうでしょうか。

   mergesort(someArray)  = { l = mergesort the left part of array,
                             r = mergesort the right part of the array,  
                             merge(l and r)  
                           }

左の部分が返されるまで、「一番左」の配列でmergesortを呼び出し続けます。それができたら、実際に「一番左」の配列を見つける正しい配列を見つけます。左と右ができたら、それらをマージします。

再帰についての 1 つのことは、正しい視点から見れば非常に簡単であり、その正しい視点は数学的帰納法と呼ばれるということです。

于 2012-09-21T08:45:23.157 に答える