Recursion

Recursión (ciencias de computación)
De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Recursión es, en ciencias de computación, una forma de atajar y solventar problemas. De hecho, recursión es una de las ideas centrales de ciencia de computación.[1] Resolver un problema mediante recursión significa que la solución depende de las soluciones de pequeñas instancias del mismoproblema.[2]
El poder de la recursión evidentemente se fundamente en la posibilidad de definir un conjunto infinito de objetos con una declaración finita. Igualmente, un número infinito de operaciones computacionales puede describirse con un programa recursivo finito, incluso en el caso de que este programa no contiene repeticiones explícitas."[3]
La mayoría de los lenguajes de programación dansoporte a la recursión permitiendo a una función llamarse a sí misma desde el texto del programa. Los lenguajes imperativos definen las estructuras de loops como while y for que son usadas para realizar tareas repetitivas. Algunos lenguajes de programación funcionales no definen estructuras de loops sino que posibilitan la recursión llamando código de forma repetitiva. La teoría de la computabilidadha demostrado que estos dos tipos de lenguajes son matemáticamente equivalentes, es decir que pueden resolver los mismos tipos de problemas, aunque los lenguajes funcionales carezcan de las típicas estructuras while y for.

Árbol basado en la recursión creado usando el lenguaje de programación Logo.
Contenido[ocultar] * 1 Algoritmos recursivos * 2 Programación recursiva * 2.1Ejemplos de subrutinas definidas recursivamente (recursión generativa) * 2.1.1 Factorial * 2.1.2 Fibonacci * 2.1.3 Máximo común denominador * 2.1.4 Torres de Hanoi * 2.1.5 Búsqueda binaria * 2.2 Estructuras de datos recursivo (recursión estructural) * 2.2.1 Listas enlazadas * 2.2.2 Árboles binarios * 2.3 Recursión frente a iteración * 3Funciones de recursión de cola * 4 Orden en el llamamiento de una función * 4.1 Función 1 * 4.2 Función 2 con líneas cambiadas * 5 Recursión directa e indirecta * 6 Véase también * 7 Notas y referencias * 8 Enlaces externos |
[editar] Algoritmos recursivos
Artículo principal: algoritmo recursivo
Un método frecuente para simplificar es dividir un problema en problemas másderivados de menor tamaño del mismo tipo. Esto se conoce como dialecting. Cómo técnica de programación se denomina divide y vencerás y es pieza fundamental para el diseño de muchos algoritmos de importancia, así como parte esencial de la programación dinámica.
Virtualmente todos los lenguajes de programación modernos permiten la especificación directa de funciones y subrutinas recursivas. Cuando sellama una función de este tipo, el ordenador (para la mayoría de lenguajes en casi todas las arquitecturas basadas en una pila (stack) o la implementación en el lenguaje llevan la cuenta de las distintas instancias de la función (en numerosas arquitecturas mediante el uso de un call stack, aunque no de forma exclusiva). A la inversa, toda función recursiva puede transformarse en una funcióniterativa usando un stack.
La mayoría (aunque no todas) las funciones y subrutinas que pueden ser evaluadas por un ordenador, pueden expresarse en términos de una función recursiva (sin tener que utilizar una iteración pura); a la inversa, cualquier función recursiva puede expresarse en términos de una iteración pura, dado que la recursión es, de por sí, también iterativa. Para evaluar una función pormedio de la recursión, tiene que definirse como una función de si misma (ej. el factor n! = n * (n - 1)! , donde 0! se define como 1). Resulta evidente que no todas las evaluaciones de funciones se prestan a un acercamiento recursivo. Por lo general, todas las funciones finitas pueden describirse directamente de forma recursiva; las funciones infinitas (ej. las series de e = 1/1! + 2/2! +...