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 untriángulo de Sierpinski. Cada triángulo está compuesto de otros, compuestos a su vez de la misma estructura recursiva.
Larecursión orecursividad 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 deautorreferencialidad,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 aparentecircularidad 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 aplicarinducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.[cita requerida]
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 es menor que podemos aplicarinducción por lo que disponemos del resultado. El caso base es que es.
Algoritmo deordenación por fusión: Sea v un vector den elementos, podemos separar el vector en dos mitades. Estas dos mitades tienen tamañon/2 por lo que, porinducció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).[cita requerida]
Enprogramació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 comodivide 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 laprogramación dinámica.
intfactorial(intx){if(x>-1&&x<2)return1;// Cuando -1 < x < 2 devolvemos 1 puesto que 0! = 1 y 1! = 1elseif(x<0)return0;// Error no existe factorial de números negativosreturnx*factorial(x-1);// Si x >= 2 devolvemos el producto de x por el factorial de x - 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 3X >= 2 -> return 3*factorial(2);X = 2 //Ahora estamos solicitando el factorial de 2X >= 2 -> return 2*factorial(1);X = 1 // Ahora estamos solicitando el factorial de 1X < 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
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.[5][6] 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)".[7] Desde esta premisa, identifica en la recursividad un reto fundamental en la producción de conocimiento que requiere nuestra reflexión:
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.[8]
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 suglosario una entrada similar a esta:
En el buscadorGoogle, al buscar «recursión», el sitio sugiere «Quizá quisiste decir:recursión».[10]
Un chiste informático dice así«:Lo primero para entender la recursividad, es entender la recursividad».[9] En lainformática también es común la elección de acrónimos recursivos.PHP son las iniciales dePHP Hypertext Preprocessor (Preprocesador de Hipertexto PHP),WINE son las deWINE Is Not an Emulator (WINE no es un emulador) yGNU significaGNU's Not Unix (GNU no esUnix).
↑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 « pertenece a ℕ» por « pertenece a ℕ».
↑«Nociones de espacios normados» , Cotlar y Cignoli, Eudeba, Buenos Aires
