1

このプログラムは、数値が素数かどうかをどのように認識しているのか疑問に思っていました。除算する偶数を見つけるために剰余をチェックすることは理解していますが、数値の因数が 2 つしかないことをどのように知るのでしょうか? 私は再帰の概念に慣れていないので、手順の説明が役に立ちます。

コード

def RecIsPrime(m):
    """Uses recursion to check if m is prime."""
    def PrimeHelper(m, j):
        """Helper Function to iterate through all j less than m up to 1 to look for even divisors."""
        if j == 1:  # Assume 1 is a prime number even though it's debatable.
            return True
        else:
            #do this task if both conditionals are true
            #else break and return false.
            return m % j != 0 and PrimeHelper(m, j - 1)
    return PrimeHelper(m, m -1)

ソース

https://github.com/hydrogeologist/LearningPython/blob/master/_recursion%20example%20in%20Python

行数: 184 ～ 194

4

2 に答える 2

2

m - 1 から m を分割する 1 までの数があるかどうかをチェックします。偶数だけをチェックするわけではありません。

EG、RecIsPrime(10)これらのネストされた関数を呼び出す必要があります。

PrimeHelper(10, 9) = 10 % 9 != 0 and PrimeHelper(10, 8)
↪ PrimeHelper(10, 8) = 10 % 8 != 0 and PrimeHelper(10, 7)
  ↪ PrimeHelper(10, 7) = 10 % 7 != 0 and PrimeHelper(10, 6)
    ↪ PrimeHelper(10, 6) = 10 % 6 != 0 and PrimeHelper(10, 5)
      ↪ PrimeHelper(10, 5) = 10 % 5 != 0 == false

10 % 5 != 0はfalseであるため、 の右側はand評価されません。PrimeHelper(10, 5)戻りfalse、再帰を続行しません。あなたは
になりますが、 であることがわかったので、これも false を返し、他のすべての呼び出しも同様です。PrimeHelper(10, 6)10 % 6 != 0truePrimeHelper(10, 5)false

于 2016-11-05T13:47:10.063 に答える
0

このコードは末尾再帰のケースです。つまり、反復を実行する再帰的な方法と見なすことができます。Python は実際にはそのように解釈しないことに注意してください (これは最適化になります)。

のすべての再帰呼び出しでmPrimeHelperの値は同じですが、jの値は前の呼び出しでの値と比較して 1 少ないことを確認してください。

したがって、コードはこのバリアントに匹敵します。

def RecIsPrime(m):
    for j in range(m-1, 1, -1):
        if m % j == 0:
            return False
    return m > 1

このバリアントでは、すべての反復が元のコードの再帰呼び出しに対応します。return False元のコードでによって行われるチェーンを壊すことに注意してくださいm % j != 0。つまり、そこで 2 つの目的を果たします。

  1. 戻るFalse
  2. PrimeHelperもう電話しないで

RecIsPrime1 以下の引数で呼び出した場合、2 つのバリアントは同じように動作しないことに注意することが重要です。そのような場合、再帰コードは「ゼロによる除算」エラー ( の場合RecIsPrime(1)) を生成するか、永久に再帰します (たとえばRecIsPrime(-1)、またはそれより小さい値)。これはバグです。それを修正するには、次のように変更します。

return PrimeHelper(m, m -1)

に

return m > 1 and PrimeHelper(m, m -1)

これは 1 の場合も修正します: 1 が素数かどうかは単に「議論の余地がある」以上のものです: 絶対にそうではありません.

于 2016-11-05T13:52:09.953 に答える