Каков рекурсивный алгоритм для функции greatest_divisor()?

#python #recursion #iteration

#python #рекурсия #итерация

Вопрос:

Прежде всего, то, что я пытаюсь сделать, НЕ является наибольшим ОБЩИМ делителем. Я пытаюсь найти наибольший делитель. Например, для числа 12 мой наибольший делитель будет равен 6. Для числа 15 это будет 5, а для 17 — 1.

То, что я сделал, было это с итерацией :

 def greatest_divisor(n):
    for d in range(n-1,0,-1):
        if n % d == 0:
            return d
            break
    

greatest_divisor(12)
>6

который работает правильно.
Что мне нужно, так это рекурсивная форма этой функции. Если вы могли бы придумать что-то работающее, я ценю это!

1. разве 12 сам по себе не является наибольшим делителем?

2. Я не понимаю, как рекурсия поможет здесь. Наибольший делитель делителя всегда будет меньше указанного делителя. Также вы можете изменить начальную точку вашей итерации на floor(n/2) as n , которая никогда не может быть разделена на что-либо большее, чем n/2 .

Ответ №1:

В общем случае вам потребуется меньше итераций, если сначала вы найдете наименьший делитель (больше 1), а затем разделите n на этот делитель, чтобы получить наибольшее. В этом случае вам не нужно повторять больше, чем до квадратного корня из n . Если ничего не найдено, верните 1.

Вот итеративное решение для этого:

 def greatest_divisor(n):
    for low in range(2, int(n**0.5) 1):
        if n % low == 0:
            return n // low
    return 1

На самом деле нет никакой выгоды в том, чтобы сделать это рекурсивным, поскольку это будет просто случай хвостовой рекурсии:

 def greatest_divisor(n, low=2):
    if n % low == 0:
        return n // low
    if low*low > n:
        return 1
    return greatest_divisor(n, low 1)

Ответ №2:

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

Далее любой итеративный метод можно переписать как рекурсивный, определив начальную точку и условие остановки. Обычно этого избегают, потому что рекурсивные методы влияют на стек и прерываются, если вы повторяете слишком глубоко, в то время как итеративные методы могут требовать только постоянных ресурсов.

Итак, здесь прямое преобразование вашего собственного кода:

 def r_greatest_divisor(n, cur=None):
    if cur is None:
        cur = n - 1
    if cur <= 1:
        return 1
    if n % cur == 0:
        return cur
    return r_greatest_divisor(n, cur - 1)