Recursión

Recursión o recursividad es la forma en la cual se específica un proceso basado en su propia definición.^[1]​ La recursión tiene esta característica discernible en términos de autorreferencialidad, autopoiesis, fractalidad, o, en otras palabras, construcción a partir de un mismo tipo. Con ánimo de una mayor precisión, y para evitar la aparente circularidad en esta definición, se formula el concepto de recursión de la siguiente manera:

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 de Sierpinski. Cada triángulo está compuesto de otros, compuestos a su vez de la misma estructura recursiva.

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 instancias má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 ${\displaystyle n!\,}$ (el factorial de ${\displaystyle n\,}$, que se define como el producto de todos los enteros positivos de ${\displaystyle 1\,}$ a ${\displaystyle n\,}$). Se puede definir el problema de forma recurrente como ${\displaystyle n(n-1)!\,}$; como ${\displaystyle (n-1)!\,}$ es menor que ${\displaystyle n!\,}$ podemos aplicar inducción por lo que disponemos del resultado. El caso base es ${\displaystyle 0!\,}$ que es ${\displaystyle 1\,}$.
• 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).

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:^[2]​

1. ${\displaystyle 0\,}$  pertenece a ℕ.
2. Si ${\displaystyle n\,}$  pertenece a ℕ, entonces ${\displaystyle n+1\,}$  pertenece a ℕ.
3. Si ${\displaystyle x\,}$  verifica las anteriores condiciones, entonces ${\displaystyle x\,}$  está incluido en ℕ ^{[cita requerida]}.

Funciones definidas de forma recurrente

Aquellas funciones cuyo dominio es un conjunto a lo más enumerable ^[3]​ pueden ser definidas de forma recurrente.

Un ejemplo conocido es la definición recurrente de la función factorial n!:

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

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

${\displaystyle {\begin{aligned}3!&=3\cdot (3-1)!\\{}&=3\cdot 2!\\{}&=3\cdot 2\cdot (2-1)!\\{}&=3\cdot 2\cdot 1!\\{}&=3\cdot 2\cdot 1\cdot (1-1)!\\{}&=3\cdot 2\cdot 1\cdot 0!\\{}&=3\cdot 2\cdot 1\cdot 1\\{}&=6\\\end{aligned}}}$ 

Otros ejemplos de funciones y sucesiones matemáticas definidas de forma recursiva son:

• Sucesión de Fibonacci — f(0)= 1, f(1) = 1; f(n) = f(n-1) + f(n-2) para n ≥ 2.
• Números de Catalan — C(2n, n)/(n+1)
• Función de Ackermann

Constantes

La razón áurea se puede definir de forma recursiva, como una fracción continua en que todos los números son unos:

${\displaystyle \phi =1+{\frac {1}{\phi }}=1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+...}}}}}}}$ .

De forma similar, la identidad ${\displaystyle {\sqrt {x}}=1+{\frac {x-1}{1+{\sqrt {x}}}}}$  da lugar a una definición como fracción continua de cualquier raíz cuadrada:^[4]​

${\displaystyle {\sqrt {x}}=1+{\cfrac {x-1}{2+{\cfrac {x-1}{2+{\cfrac {x-1}{2+{\ddots }}}}}}}}$ 

Resolución de problemas

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

a) Se pasan al primer miembro los términos ${\displaystyle a_{n}}$ , ${\displaystyle a_{n-1}}$ , ${\displaystyle a_{n-2}}$ , los cuales también podrían figurar como ${\displaystyle a_{n+2}}$ , ${\displaystyle a_{n+1}}$ , ${\displaystyle a_{n}}$ 

b) Se reemplaza ${\displaystyle a_{n}}$  por ${\displaystyle r^{2}}$ , ${\displaystyle a_{n-1}}$  por ${\displaystyle r}$  y ${\displaystyle a_{n-2}}$  por ${\displaystyle 1}$ , quedando una ecuación de segundo grado con raíces reales y distintas ${\displaystyle r_{1}}$  y ${\displaystyle r_{2}}$ .

c) Se plantea ${\displaystyle a=u\;r_{1}n+v\;r_{2}n}$ 

d) Debemos tener como dato los valores de los dos primeros términos de la sucesión: ${\displaystyle A_{0}=k\,}$  y ${\displaystyle A_{1}=k^{\prime }}$ . Utilizando estos datos ordenamos el sistema de 2x2:

${\displaystyle {\begin{cases}u+v=k\\u\;r_{1}+u\;r_{2}=k^{\prime }\end{cases}}}$ 

La resolución de este sistema nos da como resultado los valores ${\displaystyle u_{0}}$  y ${\displaystyle v_{0}}$ , que son números reales conocidos.

e) La solución general es:

${\displaystyle a_{n}=u_{0}\;r_{1}n+v_{0}\;r_{2}n}$ 

Recursión en informática

Artículo principal: Recursión (ciencias de computación)

En programación, 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 numerosos algoritmos de gran importancia, así como también es parte fundamental de la programación dinámica.

Implementación en C:

int factorial (int n) { if (n > 1) { return n * factorial(n-1); }else { return 1; } } int main() { printf("Recusividad\n"); int result = factorial(5); printf("El resultado es: %i", result); return 0; } 

Implementación en C++:

 int factorial(int x) { if (x > -1 && x < 2) return 1; // Cuando -1 < x < 2 devolvemos 1 puesto que 0! = 1 y 1! = 1 else if (x < 0) return 0; // Error no existe factorial de números negativos return x * factorial(x - 1); // Si x >= 2 devolvemos el producto de x por el factorial de x - 1 } 

Implementación en Pascal:

 FUNCTION Factorial (CONST N: INTEGER): INTEGER; BEGIN IF N > 1 THEN Factorial := N * (Factorial (N - 1)); ELSE BEGIN IF ((N=0) OR (N=1)) Factorial := 1; ELSE Factorial := 0; END; END; END; 

Implementación en Python^[5]​:

def factorial(n): if n == 1 or n == 0: return 1 else: return n * factorial(n-1) 

El seguimiento de la recursividad programada es casi exactamente igual a los ejemplos antes dados, para intentar ayudar a que se entienda mejor se ha acompañado con muchas explicaciones y con colores que diferencia los distintos sub-procesos de la recursividad.

X = 3 //Queremos 3!, por lo tanto X inicial es 3 X >= 2 -> return 3*factorial(2); X = 2 //Ahora estamos solicitando el factorial de 2 X >= 2 -> return 2*factorial(1); X = 1 // Ahora estamos solicitando el factorial de 1 X < 2 -> return 1; [En este punto tenemos el factorial de 1 por lo que volvemos marcha atrás resolviendo todos los resultados] return 2 [es decir: return 2*1 = return 2*factorial(1)] return 6 [es decir: return 3*2 = return 3*factorial(2)*factorial(1)] // El resultado devuelto es 6 

Humor recursivo

La recursividad se emplea a menudo de forma humorística en textos informáticos, filosóficos o matemáticos. No es raro que un libro de texto de estas disciplinas incluya en su glosario una entrada similar a esta:

Recursividad, véase Recursividad.^[6]​

En el buscador Google, al buscar «recursión», el sitio sugiere «Quizá quisiste decir: recursión».^[7]​

Un chiste informático dice así«:Lo primero para entender la recursividad, es entender la recursividad».^[6]​ En la informática también es común la elección de acrónimos recursivos. PHP son las iniciales de PHP Hypertext Preprocessor (Preprocesador de Hipertexto PHP), WINE son las de WINE Is Not an Emulator (WINE no es un emulador) y GNU significa GNU's Not Unix (GNU no es Unix).

Véase también

• Recursión (ciencias de computación)
• Algoritmo recursivo
• Fractal
• Sistema-L
• Torres de Hanói
• Relación de recurrencia
• Iteración
• Metaficción

Referencias

1. «Recursión» |url= incorrecta con autorreferencia (ayuda). Wikipedia, la enciclopedia libre. 27 de diciembre de 2017. Consultado el 26 de marzo de 2018. 
2. Algunos autores consideran que los números naturales son los números enteros positivos, es decir, excluyen el 0 de este conjunto. En ese caso, basta sustituir la línea que dice «${\displaystyle 1\,}$  pertenece a ℕ» por «${\displaystyle 1\,}$  pertenece a ℕ».
3. «Nociones de espacios normados» , Cotlar y Cignoli, Eudeba, Buenos Aires
4. Ben Thurston, "Estimating square roots, generalized continued fraction expression for every square root", The Ben Paul Thurston Blog
5. El Libro de Python. «La recursividad, intentando crear funciones recursivas sin crear un agujero negro». El Libro de Python. Consultado el 30 de abril de 2020. 
6. Hunter, David (2011). Essentials of Discrete Mathematics. Jones and Bartlett. p. 494. 
7. Daniel Rodríguez Herrera (29 de julio de 2009). «¿Qué es la recursividad? ¿Qué es la recursividad? ¿Qué es la recursividad?...». Libertad Digital. Consultado el 20 de enero de 2013. 

Enlaces externos

• Ejemplo de curvas recursivas fractales

•   Datos: Q179976
•   Multimedia: Recursion