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!
2 respuestas
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)
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)
Preguntas relacionadas
Nuevas preguntas
python
Python es un lenguaje de programación multipropósito, de tipificación dinámica y de múltiples paradigmas. Está diseñado para ser rápido de aprender, comprender y usar, y hacer cumplir una sintaxis limpia y uniforme. Tenga en cuenta que Python 2 está oficialmente fuera de soporte a partir del 01-01-2020. Aún así, para preguntas de Python específicas de la versión, agregue la etiqueta [python-2.7] o [python-3.x]. Cuando utilice una variante de Python (por ejemplo, Jython, PyPy) o una biblioteca (por ejemplo, Pandas y NumPy), inclúyala en las etiquetas.