Programación Recursiva

Definir la recursión en programación

• En el ámbito de la informática, una función recursiva es una función que resuelve un problema resolviendo versiones más pequeñas del mismo problema.
• La función recursiva se llama a sí misma, pasando una versión modificada del problema original a la llamada.
• Este proceso continúa hasta que se encuentra una solución, o se llega a un caso base -un caso para el que la solución está definida explícitamente-, deteniéndose el proceso de autollamada.

Significado de la recursión en programación

Ejemplos prácticos de programación recursiva

      def fibonacci(n): if n <= 1: return n else: return (fibonacci(n-1) + fibonacci(n-2))   

Niveles en la programación recursiva

Guía para principiantes sobre problemas de programación recursiva

Como programador principiante, comprender la recursividad puede resultar inicialmente complejo. Bastante, teniendo en cuenta el cambio de enfoque respecto a los métodos iterativos. Es imprescindible empezar con problemas sencillos, avanzando gradualmente hacia grupos complejos.

• Familiarízate con el concepto de funciones recursivas: esto implica comprender que las funciones recursivas se llaman a sí mismas para resolver una versión más pequeña del mismo problema.
• Comprender los casos base: un concepto crucial en la recursividad. El caso base actúa como un billete de salida del bucle aparente de recursividad. Este caso suele ser algo que puede resolverse sin más recursión.

    def factorial(n): if n==1: 
            devuelve 1 si no 
            devuelve n * factorial(n-1)

Retos de Programación Recursiva Avanzada

    def TorreOfHanoi(n , origen, destino, auxiliar): if n==1: print ("Mueve el disco 1 del origen",origen, "al destino",destino) return TorreOfHanoi(n-1, origen, auxiliar, destino) print ("Mueve el disco",n, "del origen",origen, "al destino",destino) TorreOfHanoi(n-1, auxiliar, destino, origen)

Explorar las estrategias de recursión

Programación Dinámica vs Recursión

Por otra parte, la Recursión es un concepto en el que una función se llama a sí misma para resolver instancias más pequeñas del mismo problema. Sin embargo, no gestiona explícitamente la superposición de subproblemas y, por tanto, puede provocar repeticiones e ineficacia en determinados escenarios. Considera el ejemplo clásico de encontrar el enésimo número de Fibonacci. Utilizando la recursividad, la complejidad temporal es \(O(2^{n})\). Esto se debe a que la función calcula los mismos subproblemas, una y otra vez, lo que conlleva una complejidad temporal exponencial. He aquí cómo sería un código recursivo para Fibonacci en Python:

def fibonacci(n): if n <= 1: return n else: return(fibonacci(n-1) + fibonacci(n-2))

def fibonacci(n): fib = [0, 1] + [0]*(n-1) for i in range(2, n+1): fib[i] = fib[i-1] + fib[i-2] return fib[n]

Uso eficaz de la recursión en programación

• Caso Base: Define siempre un caso base para la recursividad. El caso base es la versión más sencilla del problema, que puede resolverse directamente. Si no se define el caso base, tu función puede recurrir infinitamente y provocar un desbordamiento de pila.
• Caso recursivo: Esta parte debe descomponer el problema en versiones más sencillas y hacer una llamada recursiva. El caso recursivo debe modificar el problema cada vez, de modo que te acerques más al caso base.
• Eficacia: La recursión puede ser menos eficiente debido a la sobrecarga de las llamadas a funciones y a la repetición de los mismos cálculos, como se observa en el cálculo recursivo de Fibonacci. Utiliza la recursión de forma inteligente, cuando no se trate de múltiples subproblemas superpuestos. Si el problema implica subproblemas superpuestos, considera la posibilidad de utilizar la programación dinámica en su lugar.
• Legibilidad: Una función recursiva bien escrita suele ser más fácil de entender y depurar que su homóloga iterativa. Las soluciones recursivas son limpias y elegantes. Si la legibilidad es una prioridad, la recursividad puede ser una buena elección.