Recursión
Keywords: Recursión, Algoritmo recursivo, Dominio, Factorial, Función de Ackermann, Número natural, Números naturales, Programación, Sucesión de Fibonacci
Recursión es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente circulo sin fin en esta definición, las instancias complejas de un proceso se definen en términos de instancias más simples, estando las finales más simples definidas de forma explícita.
| Tabla de contenidos |
Los números naturales
Un ejemplo de conjunto definido de forma recursiva es el de los números naturales:
- 0 pertenece a N
- si n pertenece a N, entonces n+1 pertenece a N
- Los números naturales es el conjunto menor que cumple las dos propiedades anteriores.
Funciones definidas de forma recursiva
Aquellas funciones cuyo dominio puede ser recursivamente definido pueden ser definidas de forma recursiva.
El ejemplo mas conocido es la definición recursiva de la función factorial f(n):
- f(0) = 1
- f(n) = n · f(n-1) para todo número natural n > 0
Con esta definición veamos como funciona esta función para el valor del factorial de 3:
f(3) = 3 · f(3-1)
= 3 · f(2)
= 3 · 2 · f(2-1)
= 3 · 2 · f(1)
= 3 · 2 · 1 · f(1-1)
= 3 · 2 · 1 · f(0)
= 3 · 2 · 1 · 1
= 6
Algoritmo recursivo
Un método usual de simplificación de un problema complejo es la división de este en subproblemas del mismo tipo. Esta técnica de programación se conoce como divide y vencerás y es el núcleo en el diseño de númerosos algoritmos de gran importancia, asi como también es parte fundamental de la programación dinámica.
Ejemplos
Algunas ejemplos de recursión:
- Factorial -- n! = n × (n-1)!
- Sucesión de Fibonacci -- f(n) = f(n-1) + f(n-2)
- Números de Catalan -- C(2n, n)/(n+1)
- Las Torres de Hanoi
- Función de Ackermann