Mami

Recursión
Saltar a: navegación, búsqueda


Anuncio de cacao con una imagen recursiva. La mujer muestra un paquete idéntico al del propio anuncio, conteniendo así a otra mujer que muestra otro paquete más pequeño, de forma recursiva.


Imagen recursiva formada por un triángulo. Cada triángulo está compuesto de otros más pequeños, compuestos a su vez de la misma estructura recursiva.Recurrencia, recursión o recursividad 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 círculo sin fin en esta definición:
Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instanciasmás simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.
Para que se entienda mejor a continuación se exponen algunos ejemplos:
Factorial: Se desea calcular (el factorial de , que se define como el producto de todos los enteros positivos de a ). Se puede definir el problema de forma recurrente como ; como esmenor que podemos aplicar inducción por lo que disponemos del resultado. El caso base es que es .
Algoritmo de ordenación por fusión: Sea v un vector de n elementos, podemos separar el vector en dos mitades. Estas dos mitades tienen tamaño n/2 por lo que por inducción podemos aplicar la ordenación en estos dos subproblemas. Una vez tenemos ambas mitades ordenadas simplemente debemos fusionarlas.El caso base es ordenar un vector de cero o un elemento, que está trivialmente ordenado y no hay que hacer nada.
En estos ejemplos podemos observar como un problema se divide en varias (una o más) instancias del mismo problema, pero de tamaño menor gracias a lo cual se puede aplicar inducción, llegando a un punto donde se conoce el resultado (el caso base).
Nota: aunque los términos "recursión"y "recursividad" son ampliamente empleados en el campo de la informática, el término correcto en castellano es recurrencia. Sin embargo este último término es algo más específico. Véase relación de recurrencia.
Índice
1 Recursión en matemáticas
1.1 Conjuntos definidos de forma recurrente
1.2 Funciones definidas de forma recurrente
1.3 Constantes
1.4 Resolución de problemas
2 Recursión eninformática
3 Humor recursivo
4 Véase también
5 Referencias
6 Enlaces externos
Recursión en matemáticas
Conjuntos definidos de forma recurrente
Un ejemplo de conjunto definido de forma recurrente es el de los números naturales, es decir, el conjunto de los números enteros no negativos:1
1. pertenece a ℕ.
2. Si pertenece a ℕ, entonces pertenece a ℕ.
3. Si verifica las anteriorescondiciones, entonces está incluido en ℕ.
Funciones definidas de forma recurrente
Aquellas funciones cuyo dominio puede ser recursivamente definido pueden ser definidas de forma recurrente.
Un ejemplo conocido es la definición recurrente de la función factorial n!:

Veamos cómo se usa esta definición para hallar el valor del factorial de 3:

Otros ejemplos de funciones y sucesiones matemáticasdefinidas de forma recursiva son:
Sucesión de Fibonacci — f(n) = f(n-1) + f(n-2)
Números de Catalan — C(2n, n)/(n+1)
Función de Ackermann
Constantes
La razón áurea se puede definir como sigue: , como una fracción continua en que todos los números son unos.
De forma similar, la identidad da lugar a una definición como fracción continua de cualquier raíz cuadrada:2
Resolución de problemasResolución de ecuaciones homogéneas de primer grado, segundo orden:
a) Se pasan al primer miembro los términos , , , los cuales también podrían figurar como , ,
b) Se reemplaza por , por y por , quedando una ecuación de segundo grado con raíces reales y distintas y .
c) Se plantea
d) Debemos tener como dato los valores de los dos primeros términos de la sucesión: y . Utilizando estos datos...