Простая рекурсия - как это работает? (Python)

Question

Мне было интересно, как эта программа знает, является ли число простым или нет. Я понимаю, что он проверяет остатки, чтобы найти четные числа для деления, но откуда он знает, что число имеет только 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

Answer 1

Он проверяет, есть ли число от m - 1 до 1, которое делит m, он не проверяет только четные числа.

Например, для 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 и не продолжает рекурсию.
В PrimeHelper(10, 6) ты получаешь 10 % 6 != 0 быть true, но мы только что видели PrimeHelper(10, 5) быть false так что это также вернет false и все остальные вызовы.

Answer 2

Этот код представляет собой случай хвостовой рекурсии, то есть его можно рассматривать как рекурсивный способ выполнения итерации. Обратите внимание, что Python на самом деле не интерпретирует это (что было бы оптимизацией), но все же полезно видеть это так:

Посмотрите, как каждый рекурсивный вызов PrimeHelper имеет то же значение для m, но имеет значение для j, которое на единицу меньше по сравнению со значением, которое оно имело в предыдущем вызове.

Таким образом, код сопоставим с этим вариантом:

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 в исходном коде, т.е. там он служит двум целям:

1. Вернуть False
2. Не звони PrimeHelper больше не

Важно отметить, что эти два варианта не ведут себя одинаково при вызове RecIsPrime с аргументом 1 или меньше. В этих случаях рекурсивный код может вызвать ошибку "деление на ноль" (когда RecIsPrime(1)) или навсегда (например, RecIsPrime(-1) или любое меньшее значение). Это ошибка. Чтобы исправить это изменение:

return PrimeHelper(m, m -1)

от

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

это также исправляет случай для 1: это больше, чем просто "спорный", является ли 1 простым или нет: это определенно нет.