Algoritmo recursivo


Algoritmo recursivo

Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.

FUNCIÓN Factorial(n)
    VAR resultado: Entero
 
    SI (n<2) ENTONCES
        resultado = 1;
    SINO
        resultado = n * Factorial(n-1);
    FSI
 
    RETORNA resultado;
FFUNCIÓN

Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema que resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.

Las claves para construir un subprograma recurrente son:

  • Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).
  • Ha de existir al menos un caso base para evitar que la recurrencia sea infinita.

Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.

Recursividad indirecta

Cuando en una subrutina hay llamadas a ella misma se habla de recursividad directa, en contraposición, cuando se tienen varias subrutinas y éstas se llaman unas a otras formando ciclos se dice que la recursión es indirecta.

Subrutina_A → Subrutina_B → Subrutina_A
Subrutina_A → Subrutina_B → Subrutina_C → Subrutina_D → Subrutina_A

Véase también

  • Recursión
  • Recursión (ciencias de computación)

Enlaces externos


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Algoritmo recursivo — Un algoritmo recursivo es un algoritmo que se define en términos de sí mismo. Son implementados en forma de subprogramas (funciones, subrutinas, procedimientos, etc) de tal forma que dentro de un subprograma recursivo hay una o más llamadas a él… …   Enciclopedia Universal

  • Algoritmo divide y vencerás — En la cultura popular, divide y vencerás hace referencia a un refrán que implica resolver un problema difícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia. La solución… …   Wikipedia Español

  • Algoritmo de relleno por difusión — Este artículo es una traducción del equivalente en inglés, y aún no está completo. Algoritmo recursivo de 4 direcciones. El algoritmo de relleno por difusión, también llamado algoritmo de relleno, o directamente del inglés floodfill determina el… …   Wikipedia Español

  • Algoritmo de Karatsuba — El algoritmo de Karatsuba es un procedimiento para multiplicar números grandes eficientemente, que fue descubierto por Anatolii Alexeevitch Karatsuba en 1960 y publicado en 1962.[1] [2] El algoritmo consigue reducir la múltiplicación de dos… …   Wikipedia Español

  • Algoritmo de de Casteljau — Saltar a navegación, búsqueda El algoritmo de de Casteljau es, en el campo del análisis numérico de la matemática, un método recursivo para calcular polinomios en la forma de Bernstein o base de Bernstein o en las curvas Bézier, toma su nombre de …   Wikipedia Español

  • Algoritmo de De Casteljau — El algoritmo de de Casteljau es, en el campo del análisis numérico de la matemática, un método recursivo para calcular polinomios en la forma de Bernstein o base de Bernstein, o en las curvas de Bézier. Toma su nombre del ingeniero Paul de… …   Wikipedia Español

  • Ecuación recurrente — Saltar a navegación, búsqueda En matemática, una relación de recurrencia es una ecuación que define una secuencia recursiva; cada término de la secuencia es definido como una función de términos anteriores. Contenido 1 Definición 2 Resolución 2.1 …   Wikipedia Español

  • Recursión — Saltar a navegación, búsqueda 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 …   Wikipedia Español

  • Árbol binario de búsqueda — Un árbol binario de búsqueda es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática. Contenido 1 Descripción 2 Operaciones 2.1 Búsqueda …   Wikipedia Español

  • Exponenciación binaria — Saltar a navegación, búsqueda La exponenciación binaria es un algoritmo utilizado para calcular de forma rápida grandes potencias enteras de un número x dado. También es conocido como potenciación por cuadrados o elevar al cuadrado y multiplicar …   Wikipedia Español