Ver el código de «Recursión»

{{Referencias adicionales|t=20240421182654}}[[Archivo:Droste.jpg|thumb|200px|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.]]
[[Archivo:SierpinskiTriangle.svg|thumb|200px|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.]]

La '''recursión''' o '''recursividad''' es la posibilidad que tiene un cierto tipo de unidad o proceso de contenerse o aplicarse a sí mismo indefinidamente. 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 [[definición circular|circularidad]] en esta definición, se formula el concepto de recursión de la siguiente manera:

Un problema que pueda definirse en función de su tamaño, sea este N, puede dividirse en instancias más pequeñas (< N) del mismo problema y se conocerá la solución explícita a las instancias más simples, lo que se conoce como casos base, y se puede aplicar [[razonamiento inductivo|inducción]] sobre las llamadas más pequeñas y suponer que estas quedan resueltas.{{cr}}

A continuación se exponen algunos ejemplos:

* [[Factorial]]: Se desea calcular <math>n! \,</math> (el factorial de <math>n \,</math>, que se define como el producto de todos los enteros positivos de <math>1 \,</math> a <math>n \,</math>). Se puede definir el problema de forma recurrente como <math>n(n-1)! \,</math>; como <math>(n-1)! \,</math> es menor que <math>n! \,</math> podemos aplicar [[Razonamiento inductivo|inducción]] por lo que disponemos del resultado. El caso base es <math>0! \,</math> que es <math>1 \,</math>.
* 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 [[Razonamiento inductivo|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 puede observarse cómo 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).{{cr}}

== 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:<ref>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 «<math>1 \,</math> pertenece a ℕ» por «<math>1 \,</math> pertenece a ℕ».</ref>
# <math>0 \,</math> pertenece a ℕ.
# Si <math>n \,</math> pertenece a ℕ, entonces <math>n+1 \,</math> pertenece a ℕ.
# Si <math>x \,</math> verifica las anteriores condiciones, entonces <math>x \,</math> está incluido en ℕ {{cr}}.

=== Funciones definidas de forma recurrente ===

Aquellas funciones cuyo [[dominio de definición|dominio]] es un conjunto a lo más enumerable pueden ser definidas de forma recurrente.<ref>«Nociones de espacios normados» , Cotlar y Cignoli, Eudeba, Buenos Aires</ref>

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

:<math>
n!=
\begin{cases} 
\mbox{si }n=0 & \Rightarrow 1  \\ 
\mbox{si }n\geq1 & \Rightarrow n \;(n-1)!
\end{cases}
</math>

Veamos cómo se usa esta definición para hallar el valor del factorial de 3:
:<math>
\begin{align}
 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{align}
</math>

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 <math>n\geq2</math>.
* [[Números de Catalan]] — ''C''(2''n'', ''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:  

:<math>\phi = 1 + \frac{1}{\phi} =  1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + ...}}}</math>. 

De forma similar, la [[identidad (matemáticas)|identidad]] <math>\sqrt{x} = 1+\frac{x-1}{1+\sqrt{x}}</math> da lugar a una definición como fracción continua de cualquier raíz cuadrada:<ref>Ben Thurston, [http://benpaulthurstonblog.blogspot.com/2012/05/estimating-square-roots.html "Estimating square roots, generalized continued fraction expression for every square root"], ''The Ben Paul Thurston Blog''</ref>

:<math>\sqrt{x}=1+\cfrac{x-1}{2 + \cfrac{x-1}{2 + \cfrac{x-1}{2+{\ddots}}}}</math>

=== Resolución de problemas ===
[[Resolución de ecuaciones]] homogéneas de primer grado, segundo orden:

a) Se pasan al primer miembro los términos <math>a_n</math>, <math>a_{n-1}</math>, <math>a_{n-2}</math>, los cuales también podrían figurar como <math>a_{n+2}</math>, <math>a_{n+1}</math>, <math>a_n</math>

b) Se reemplaza <math>a_n</math> por <math>r^2</math>, <math>a_{n-1}</math> por <math>r</math> y <math>a_{n-2}</math> por <math>1</math>, quedando una [[ecuación de segundo grado]] con raíces reales y distintas <math>r_1</math> y <math>r_2</math>.

c) Se plantea <math> a = u\; r_1 n + v\; r_2 n </math>

d) Debemos tener como dato los valores de los dos primeros términos de la sucesión: <math>A_0 = k\,</math> y <math>A_1 = k^\prime</math>. Utilizando estos datos ordenamos el sistema de 2x2: 

:<math>\begin{cases}
u + v = k \\
u \; r_1 + u \; r_2 = k^\prime
\end{cases}</math> 

La resolución de este sistema nos da como resultado los valores <math>u_0</math> y <math>v_0</math>, que son números reales conocidos.

e) La solución general es: 

:<math>a_n = u_0 \; r_1 n + v_0 \; r_2 n</math>

== Recursión en informática ==
{{AP|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 [[Algoritmo divide y vencerás|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:

<syntaxhighlight lang="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;
}
</syntaxhighlight>

Implementación en [[C++]]:

<syntaxhighlight lang="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
 }
</syntaxhighlight>

Implementación en [[Pascal (lenguaje de programación)|Pascal]]:
<syntaxhighlight lang="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;
</syntaxhighlight>

Implementación en [[Python]]:<ref>{{cita web|url=http://ellibrodepython.com/recursividad/ |título=La recursividad, intentando crear funciones recursivas sin crear un agujero negro |autor=El Libro de Python |publicación=[[El Libro de Python]] | fechaacceso=30 de abril de 2020}}</ref>

<syntaxhighlight lang="Python">
def factorial(n):
    if n == 1 or n == 0:
        return 1
    else:
        return n * factorial(n-1)
</syntaxhighlight>

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.
 <span style="color:#0000FF">'''X = 3'''</span> //Queremos 3!, por lo tanto X inicial es 3
 <span style="color:#0000FF">'''X >= 2 -> return 3*factorial(2);'''</span>
     <span style="color:#B22222">'''X = 2'''</span> //Ahora estamos solicitando el factorial de 2
     <span style="color:#B22222">'''X >= 2 -> return 2*factorial(1);'''</span>
         <span style="color:#FF2700">'''X = 1'''</span> // Ahora estamos solicitando el factorial de 1
         <span style="color:#FF2700">'''X < 2 -> return 1;'''</span>
         [En este punto tenemos el factorial de 1 por lo que volvemos marcha atrás resolviendo todos los resultados]
     <span style="color:#B22222">'''return 2'''</span> [es decir: return 2*1 = return 2*factorial(1)]
 <span style="color:#0000FF">'''return 6'''</span> [es decir: return 3*2 = return 3*factorial(2)*factorial(1)] // El resultado devuelto es 6

== Recursión en las ciencias sociales ==
El concepto de recursión o recursividad está en el centro de los debates epistemológicos en ciencias sociales, y se refiere a la situación en que los científicos sociales se encuentran al intentar producir conocimiento acerca de un mundo del que ellos mismos son parte.<ref>{{Cite journal|title=Double Bind et Conversion|journal=Pour Une Anthropologie Réflexive|publisher=Le Seuil|publication-place=Paris|year=1992|last=Bourdieu|first=Pierre}}</ref><ref>{{Cite book|last=Giddens|first=Anthony|title=Social Theory and Modern Sociology|publisher=Polity Press|year=1987}}</ref> Según Audrey Alejandro, "como científicos sociales, la recursividad de nuestra condición alude al hecho de que somos a la vez sujetos (pues el discurso es el medio por el cual analizamos) y objetos de los discursos académicos que producimos (pues somos agentes sociales dentro del mundo que analizamos)".<ref>{{Cite journal|url=http://journals.sagepub.com/doi/10.1177/1354066120969789|title=Reflexive discourse analysis: A methodology for the practice of reflexivity|date=2021|journal=European Journal of International Relations|volume=27|issue=1|page=171|language=en|issn=1354-0661|doi=10.1177/1354066120969789|last=Alejandro|first=Audrey|s2cid=229461433}}</ref> Desde esta premisa, identifica en la recursividad un reto fundamental en la producción de conocimiento que requiere nuestra reflexión: 

{{quote|estamos socializados en discursos y predisposiciones producto del orden sociopolítico que aspiramos a transformar (un orden sociopolítico que podemos, por tanto, reproducir de manera inconsciente aun teniendo el objetivo opuesto). La recursividad de nuestra posición como académicos (y más específicamente, el hecho de que las herramientas que usamos para producir conocimiento sobre el mundo son a su vez producidas por este mundo— evidencia la necesidad crítica de implementar la práctica reflexiva y presenta el principal reto a la hora de hacerlo.<ref name=":3">{{Cite journal |last=Alejandro |first=Audrey |date=2021 |title=Reflexive discourse analysis: A methodology for the practice of reflexivity |url=http://journals.sagepub.com/doi/10.1177/1354066120969789 |journal=European Journal of International Relations |language=en |volume=27 |issue=1 |page=5 |doi=10.1177/1354066120969789 |s2cid=229461433 |issn=1354-0661}}</ref>}}

== 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''.<ref name=Hunter>{{cita libro|apellidos=Hunter|nombre=David|título=Essentials of Discrete Mathematics|año=2011|editorial=Jones and Bartlett|páginas=494|url=http://books.google.com/books?id=kuwhTxCVovQC&dq=recursion+joke&source=gbs_navlinks_s}}</ref>

En el buscador [[Google]], al buscar «recursión», el sitio sugiere «Quizá quisiste decir: ''recursión''».<ref>{{cita web|url=http://www.libertaddigital.com/internet/que-es-la-recursividad-que-es-la-recursividad-que-es-la-recursividad-1276366373/ |título=¿Qué es la recursividad? ¿Qué es la recursividad? ¿Qué es la recursividad?... |autor=Daniel Rodríguez Herrera |publicación=[[Libertad Digital]] |fecha=29 de julio de 2009 |fechaacceso=20 de enero de 2013}}</ref>

Un chiste informático dice así«:Lo primero para entender la recursividad, es entender la recursividad».<ref name=Hunter/> 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 ==
<references responsive="" />

== Enlaces externos ==
* [http://neoparaiso.com/logo/curvas-fractales.html Ejemplo de curvas recursivas fractales]

{{Control de autoridades}}
[[Categoría:Terminología matemática]]
[[Categoría:Programación]]
[[Categoría:Gramática generativa]]
[[Categoría:Autorreferencia]]