En primer lugar, lo que estoy tratando de hacer es NO el mayor divisor COMÚN . Estoy tratando de encontrar el mayor divisor . Por ejemplo, para el número 12, mi mayor divisor será 6. Para el número 15 será 5 y para 17 será 1.

Lo que hice fue esto con una iteración:

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

greatest_divisor(12)
>6

Que funciona correctamente. Lo que necesito es la forma recursiva de esta función. Si pudieras pensar en algo que funcione, ¡te lo agradezco!

0
baymurat 9 dic. 2020 a las 12:41

2 respuestas

La mejor respuesta

En general, necesitaría menos iteraciones si primero encontrara el divisor menor (mayor que 1) y luego dividiera n por ese divisor para obtener el mayor. En ese caso, no tiene que iterar más que hasta la raíz cuadrada de n . Cuando no se encuentra ninguno, devuelve 1.

Aquí está la solución iterativa para eso:

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

Realmente no hay ganancia en hacer esto recursivo, ya que será solo un caso de recursión de cola:

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
trincot 9 dic. 2020 a las 09:58

Primero, comenzaría con una observación matemática: encontrar el divisor mayor es lo mismo que encontrar el divisor más pequeño (pero 1), y ese divisor más pequeño será primo. Esa propiedad podría conducir a algoritmos más eficientes si quisiera buscar una gran cantidad de valores.

A continuación, cualquier método iterativo se puede reescribir como recursivo definiendo un punto de partida y una condición de parada. En general, se evita porque los métodos recursivos tienen un impacto en la pila y se rompen si recurre demasiado, mientras que los métodos iterativos solo pueden requerir recursos constantes.

Entonces, aquí una transformación directa de su propio código es:

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)
1
Serge Ballesta 9 dic. 2020 a las 09:57
65214227