1

Estoy tratando de implementar una función recursiva con python para encontrar la suma de todos los divisores positivos de un número.

Tengo el siguiente código:

def sumaDivisores(n):
    n = abs(n)
    if n == 1:    #Caso Base
        return 1
    if n > 1:     #Caso recursivo
        suma = n + sumaDivisores(n%(n-1))
        return suma
print(sumaDivisores(2))

Sin duda, estoy haciendo mal la llamada recursiva, pero no se me ocurre la forma correcta de hacerlo.

4
  • ¿Deben incluirse entre sus divisores él mismo y la unidad? Por ejemplo sumaDivisores(9) debe salir 13 y sumaDivisores(8) debe salir 15?
    – abulafia
    Commented el 18 dic. 2018 a las 18:13
  • Si, él mismo y la unidad se incluyen como divisores. Commented el 18 dic. 2018 a las 18:20
  • ninguna de las respuesta te ha funcionado? Commented el 21 dic. 2018 a las 14:17
  • Podrias aclarar si alguna respuesta funciono, o agregar una respuesta?
    – gbianchi
    Commented el 21 jun. 2019 a las 19:40

4 respuestas 4

1

Lo que se me ha ocurrido es ligeramente más complejo que lo que estabas intentando tú. Sospecho que tiene que haber una forma más simple. En todo caso, te explico qué tenías mal y mi línea de razonamiento.

El razonamiento recursivo sobre los divisores de un número sería:

  • Como mínimo el propio número se divide a sí mismo, luego n ha de ser parte de la suma.
  • Además de él, si encontramos otro divisor d que divida a n entonces podemos quedarnos con el cociente c = d//n (// es la división entera en python3). La suma que buscamos será n más la suma de los divisores de c.

La recursión por tanto en este caso no desciende "de uno en uno". n-1 no tiene por qué ser divisor de n (de hecho no lo será salvo para n=2).

Por otro lado tú lo que pasabas recursivamente era el resto de la división (operador %) lo que tampoco tiene mucho sentido.

Implementando en python lo que antes he dicho de palabra, me queda así:

def sumaDivisores(n):
    # Caso base que se resuelve directamente
    if n==1:
      return 1
    # Cualquier otro caso, hay que recorrer todos los números entre 2 y n
    # (ambos inclusive) buscando divisores
    for i in range(2,n+1):
      if n%i == 0: # Tenemos un divisor
        # Aplicamos recursividad
        return n + sumaDivisores(n//i)

Esta implementación funciona correctamente en los varios casos que he probado, pero tiene algo "sucio" que no acaba de convencerme, relacionado con la forma en que deben tratarse los casos 1 y n. Tampoco es muy eficiente buscar divisores entre 2 y n, pues si llegas hasta √n sin encontrar ninguno, ya no vas a encontrar. Pero si no seguimos hasta n, no encontrará el propio n, con lo que no haría la división n//n para encontrar el 1.

2
  • Si, funciona. Pero hasta dónde tengo entendido en recursión no se debe usar ciclos while o for. Por lo que habría que pensar en una función auxiliar que determine si un número es divisor de n. Commented el 18 dic. 2018 a las 18:49
  • Bueno, en este caso el bucle que aparece no está ahi para sustituir a la recursión, sino sólo para encontrar un divisor. El bucle que evitamos con la recursión sería el de ir sumando n + n//d1 + d1//d2 + d2//d3 ... + 1. Pero habría que tener claro si te prohiben este bucle también. En todo caso, cualquier bucle puede sustituirse por recursión, pero sería otra recursión para otro objetivo: "Encontrar el primer divisor de n"
    – abulafia
    Commented el 18 dic. 2018 a las 18:58
1
def sumaDivisores(n):
  def encontrarDivisores(m):
    if m > 0:
      if n%m == 0:
        arr.append(m)
      encontrarDivisores(m-1)
  arr = []
  encontrarDivisores(n)
  print("El número %d, tiene %s divisores; Suman %d." % (n, arr, sum(arr)))


sumaDivisores(0)  
sumaDivisores(11)
sumaDivisores(17)
sumaDivisores(23)
sumaDivisores(12)
sumaDivisores(18)
sumaDivisores(24)
1

Este problema se resuelve muy fácilmente de forma iterativa, pero, dado que estás pidiendo hacerlo de forma recursiva, acá te dejo las dos versiones. La explicación de cada una está debajo.

Versión recursiva

def sumaDivisores(n):
    n = abs(n)

    def _sumarDivisores(div_actual):
        if div_actual == 0:
            return 0

        s = _sumarDivisores(div_actual - 1)

        if n % div_actual == 0:
            return s + div_actual

        return s

    return _sumarDivisores(n)

print(sumaDivisores(10))  # 18

Este es la versión recursiva, la que necesitas. Si bien la respuesta de JackNavaRow es correcta, me parece que esta vías es más simple y fácil de entender. La función externa sumaDivisores tiene como único objetivo calcular el módulo del número en cuestión. El trabajo pesado lo hace la función interna _sumaDivisores, que realiza dos tareas fundamentalmente:

  1. Calcular la suma de los divisores menores que el divisor actual
  2. Añadir a dicha suma el divisor actual si y solo si es realmente un divisor válido

Claro está que el caso base es cuando el divisor actual es 0, en cuyo caso se retorna 0 como suma.

Versión iterativa

Clásica

def sumaDivisores(n):
    suma = 0

    for i in range(1, n + 1):
        if n % i == 0:
            suma += i

    return suma

print(sumaDivisores(10))  # 18

Con un generador

def sumaDivisores(n):
    return sum((i for i in range(1, abs(n) + 1) if n % i == 0))

print(sumaDivisores(10))  # 18

En este caso te dejo dos variantes, la forma clásica y otra aprovechando los generadores de Python.

Si mi respuesta te ayudó, márcala como aceptada (checkmark ✓ verde), sino déjame saber que fue mal.

0

Tu problema es que debes restar es el divisor y no persiste el numero a dividir adenmas falta validar los casos que sean 0

def sumaDivisores(n, divisor = None):
    n = abs(n)
    if divisor == 0:    #Caso Base
        return 0
    if not divisor:
        divisor = n
    divisor_valido = 0
    if (n%divisor == 0):
        divisor_valido = divisor
    suma = divisor_valido  + sumaDivisores(n  , divisor  -1 )
    return suma
print(sumaDivisores(8))
print(sumaDivisores(9))
2
  • Me parece que con la última línea no tendrá en cuenta al mismo n como divisor. Por ejemplo para n = 3 la suma debe dar 4 y da 2. Commented el 18 dic. 2018 a las 21:18
  • estaba sumando el residuo no el divisor, por favor chequea de nuevo Commented el 19 dic. 2018 a las 12:26

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.