1

La idea del código es tomar una función con los siguientes parámetros: start, stop, step. start indica el primer número, stop el último y step la diferencia entre cada número y la idea es sumar los elementos de la secuencia.

Por ejemplo, en el caso de los siguientes parámetros: (2,5,2) la secuencia sería 2,4 y el resultado sería 6. Este es el código que se me ocurrió pero no funciona correctamente:

def recursive(start,stop,step):
    if start>=stop:
       return start
    else:
       return start+recursive(start+step,stop,step)

El código funciona bien cuando start iguala el valor de stop como en el caso de los parámetros (2,6,2) pero en el caso de (2,5,2) la salida es 2+4+6 y la idea es que solamente sume 2+4.

1 respuesta 1

1

La causa está en el condicional, imaginemos el caso que comentas, la secuencia de llamadas sería:

  • recursive(2, 5, 2), 2 > 5, luego se retorna 2 + recursive(2+2, 5, 2).
  • recursive(4, 5, 2), 4 > 5, luego se retorna 4 + recursive(4+2, 5, 2)
  • recursive(6, 5, 2), 6 <= 5, luego retorna 6.

Ahora hay que entender como funciona la recursividad que básicamente se comporta como una pila, la primera llamada a la función es la última en retornar y es de la que obtienes el resultado. Cuando se produce la primera llamada a la función esta retorna 2 + recursive(2+2, 5, 2) pero no puede retornar hasta que recursive(2+2, 5, 2) se complete y le retorne algo que sumar a 2, lo mismo pasa con las siguientes llamadas, de forma que la última llamada es la primera en completarse y retornar algo y a partir de ahí sigue la cadena hacia atrás hasta llegar a la primera llamada.

Es decir, cuando la tercera llamada recursive(6, 5, 2) retorna start (6), la segunda puede continuar y retorna 4 + 6), cuando esto se produce la primera llamada puede retornar y nos retorna 2 + 10 por lo que obtenemos 12.

El problema es que la tercera llamada nunca debió producirse, porque 6 es mayor que 5. Una posible solución siguiendo tu idea original es modificar el condicional y en vez de comparar start comparar start + step, por ejemplo:

def recursive(start,stop,step):
    sum_ = start + step
    if sum_ > stop:
        return start
    return start + recursive(sum_, stop, step)
>>> recursive(2, 5, 2)
6
>>> recursive(2, 6, 2)
12

De lo anterior se deriva uno de los problemas de la recursión, cada llamada recursiva implica la creación de un nuevo frame en la pila de llamadas y la pila no es infinita, esto puede terminar causando un desbordamiento de la misma (Stack Overflow...). Tener en cuenta que Python no realiza una optimización de la recursión de cola (que no es tu caso de todas formas) como también ocurre en otros lenguajes (aunque en el caso de Python es más bien porque Guido van Rossum no aprecia la recursión demasiado...) por lo que si la función fuera recursiva de cola aún tendríamos el mismo problema.

Por defecto Python limita las llamadas recursivas a 1000 para proteger la pila de C (su desbordamiento significa el final de malas formas del intérprete y eso no es bueno...), es un límite bastante conservador y podemos elevarlo algo con cuidado mediante sys.setrecursionlimit aunque generalmente en estos casos optar por otras aproximaciones (iteración, memoization, etc) es mejor idea.

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.