En programación,la recursión es una técnica donde una función se invoca a sí misma.
Existen dos casos que parecen ser los mejores para mostrar la Recursión: los factoriales y los números de Fibonacci. Especialmente este último caso.
La definición de los números de Fibonacci es un ejemplo de recursión. En el artículo REVIT ARCHITECTURE (943) – PYTHON – Funciones (27) – Funciones simples (6) Números de Fibonacci ya se explicaba que:
Fibi = Fibi-1 + Fibi-2
La definición del número i-ésimo se refiere al número i-1, y así sucesivamente, hasta que se llega a los dos primeros.
Respecto la función planteada en el artículo REVIT ARCHITECTURE (943) – PYTHON – Funciones (27) – Funciones simples (6) Números de Fibonacci se puede plantear una función más clara de entender:
Esta función fib(n) es una implementación recursiva que calcula el enésimo número en la secuencia de Fibonacci. La secuencia de Fibonacci es una serie de números en la que cada número es la suma de los dos anteriores, comenzando con 1 y 1. La función está diseñada para devolver el enésimo número de Fibonacci dado un número entero n.
Definición de la función
La función fib toma un argumento n, que es el índice en la secuencia de Fibonacci para el cual queremos calcular el valor correspondiente.
Condición base 1: Manejo de entradas inválidas
Esta primera condición verifica si el valor de n es menor que 1.
Si n es menor que 1, la función devuelve None, lo que indica que la entrada es inválida. Esto se debe a que en la secuencia de Fibonacci, los índices válidos comienzan en 1.
Condición base 2: Manejo de los primeros dos números de Fibonacci
Esta condición maneja los casos donde n es 1 o 2.
En la secuencia de Fibonacci, los primeros dos números son amJbos 1, por lo que si n es 1 o 2, la función devuelve 1 directamente.
Esto evita llamadas recursivas innecesarias para estos casos básicos.
Caso recursivo: Descomposición del problema
Si n es mayor o igual a 3, la función entra en la parte recursiva.
La función se llama a sí misma dos veces: una con el argumento n-1 y otra con n-2.
El resultado final es la suma de estos dos valores. Esto refleja la definición matemática de la secuencia de Fibonacci, donde cada término es la suma de los dos términos anteriores.
La recursión continuará descomponiendo el problema hasta que alcance las condiciones base, es decir, cuando n sea 1 o 2.
Ejemplo de cómo funciona la recursión
Si llamas a fib(5), la función se descompone de la siguiente manera:
fib(5) requiere fib(4) y fib(3).
fib(4) requiere fib(3) y fib(2).
fib(3) requiere fib(2) y fib(1).
fib(2) y fib(1) son condiciones base, por lo que ambos devuelven 1.
La suma de estos valores devuelve finalmente el valor de fib(5).
Consideraciones sobre eficiencia de la función:
Aunque este enfoque es simple y directo, no es el más eficiente porque recalcula muchos valores múltiples veces. Por ejemplo, fib(3) se calcula dos veces cuando se calcula fib(5).
Este problema puede solucionarse utilizando técnicas como la memorización (almacenar los resultados intermedios) o programación dinámica para evitar la recalculación.
En resumen, esta función fib(n) implementa la definición recursiva de los números de Fibonacci, calculando el valor de fib(n) sumando los dos valores previos en la secuencia, y manejando los casos básicos con condiciones que devuelven valores conocidos de la secuencia.
En realidad hay un pequeño riesgo al aplicar esta función. Si olvidas considerar las condiciones que pueden detener la cadena de invocaciones recursivas, el programa puede entrar en un bucle infinito. Debes tener cuidado.
El factorial también tiene un lado recursivo. El factorial se marca con un signo de exclamación, y es igual al producto de todos los números naturales desde uno hasta su argumento.
n! = 1 × 2 × 3 × … × n-1 × n
Es obvio que:
1 × 2 × 3 × … × n-1 = (n-1)!
Así que, finalmente, el resultado es:
n! = (n-1)! × n
Para saber que es un factorial puedes ver el artículo REVIT ARCHITECTURE (942) – PYTHON – Funciones (26) – Funciones simples (5) Funciones factoriales.
La función que se puede definir para calcular un factorial en relación a la que se planteó en el artículo indicado en el párrafo anterior (número 942), es la siguiente:
La función factorial_function(n) es una implementación recursiva para calcular el factorial de un número entero positivo n. El factorial de un número n (denotado como n!) se define como el producto de todos los números enteros positivos desde 1 hasta n. Por ejemplo, 5!=.
Definición de la función
La función factorial_function toma un argumento n, que es el número entero para el cual queremos calcular su factorial.
Condición base 1: Manejo de entradas inválidas
Esta condición verifica si el valor de n es menor que 0.
Si n es menor que 0, la función devuelve None, lo que indica que el factorial no está definido para números negativos en el contexto de esta función.
Condición base 2: Factorial de 0 y 1
- Esta condición maneja los casos en los que n es 0 o 1.
- El factorial de 0 (0!) y el factorial de 1 (1!) están definidos como 1.
- Por lo tanto, si n es menor que 2 (es decir, n es 0 o 1), la función devuelve 1 directamente.
- Esta condición base es esencial para detener la recursión.
Caso recursivo: Descomposición del problema
- Si n es mayor o igual a 2, la función entra en la parte recursiva.
- La función se llama a sí misma con el argumento n-1 y multiplica el resultado por n.
- Este proceso refleja la definición matemática del factorial: n!=.
- La recursión continúa hasta que n alcanza 1, en cuyo punto la función devuelve 1 y la recursión comienza a resolverse hacia arriba.
Ejemplo de cómo funciona la recursión
Si llamas a factorial_function(5), la función se descompone de la siguiente manera:
factorial_function(5) = 5 * factorial_function(4)
factorial_function(4) = 4 * factorial_function(3)
factorial_function(3) = 3 * factorial_function(2)
factorial_function(2) = 2 * factorial_function(1)
factorial_function(1) = 1 (condición base)
Al resolver estas llamadas recursivas, el cálculo sería:
factorial_function(2) devuelve 2
factorial_function(3) devuelve 6
factorial_function(4) devuelve 24
factorial_function(5) devuelve 120
Por lo tanto, factorial_function(5) = 120.
Consideraciones sobre la recursión :
Esta función es eficiente para calcular factoriales de números relativamente pequeños.
Sin embargo, para valores de n muy grandes, la recursión profunda podría causar un desbordamiento de la pila (stack overflow) debido a la gran cantidad de llamadas recursivas.
Resumen:
La función factorial_function(n) calcula el factorial de n multiplicando n por el factorial de n-1.
La función utiliza dos condiciones base: una para manejar entradas negativas (devolviendo None) y otra para manejar los casos de n = 0 y n = 1 (devolviendo 1).
La recursión se detiene cuando n alcanza 1, y el cálculo se resuelve al multiplicar cada n por el resultado del factorial de n-1.
Contenido Web de Yolanda Muriel está sujeto bajo Licencia Creative Commons Atribución-NoComercial-SinDerivadas 3.0 Unported.
yolandamuriel.com 