Recursión

De Wikipedia, la enciclopedia libre

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 círculo 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.

(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)

Tabla de contenidos

1 Los números naturales
2 Funciones definidas de forma recurrente
3 Algoritmo recurrente
4 Ejemplos

[editar] Los números naturales

Un ejemplo de conjunto definido de forma recurrente 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 de números enteros positivos.

[editar] Funciones definidas de forma recurrente

Aquellas funciones cuyo dominio puede ser recursivamente definido pueden ser definidas de forma recurrente.

El ejemplo más conocido es la definición recurrente de la función factorial n!:

$n!= \begin{cases} \mbox{si }n=0 & \Rightarrow 1 \\ \mbox{si }n>1 & \Rightarrow (n-1)! \;n \end{cases}$

Con esta definición veamos como funciona esta función para el valor del factorial de 3:

3! = 3 · (3-1)!
   = 3 · 2!
   = 3 · 2 · (2-1)!
   = 3 · 2 · 1!
   = 3 · 2 · 1 · (1-1)!
   = 3 · 2 · 1 · 0!
   = 3 · 2 · 1 · 1
   = 6

[editar] Algoritmo recurrente

Artículo principal: 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, así como también es parte fundamental de la programación dinámica.

[editar] Ejemplos

Resolución de ecuaciones homogéneas de primer grado, segundo orden:

a) Se pasan al primer miembro los términos an, an-1, an-2, los cuales también podrían figurar como an+2, an+1, an b)Se reemplaza an por r², an-1 por r y an-2 por 1, quedando una ecuación de segundo grado con raíces reales y distintas de r1 y r2. c)Se plantea a = u · r1n + v · r2n

e)Debemos tener como dato los valores de los dos primeros términos de la sucesión: A0 = k y A1 = k’. Utilizando estos datos ordenamos el sistema de 2x2: u + v = k y u·r1 + u·r2 = k’. La resolución de este sistema no da como resultado los valores u0 y v0, que son números reales conocidos.

e)La solución general es:

an = u0 · r1n + v0 · r2n

Algunos ejemplos de recurrencia: