Recursión

La recursividad forma parte del repertorio para resolver problemas en Computación y es de los métodos más poderosos y usados. Los algoritmos recursivos ofrecen soluciones estructuradas, modulares y elegantemente simples.

La recursividad es un concepto fundamental en matemáticas y en computación. Una definición recursiva dice cómo obtener conceptos nuevos empleando el mismo concepto que intenta describir.

En toda situación en la cual la respuesta pueda ser expresada como una secuencia de movimientos, pasos o transformaciones gobernadas por un conjunto de reglas no ambiguas, la fórmula recursiva es un buen candidato para resolver el problema.

Los razonamientos recursivos se encuentran en la base misma de las matemáticas porque son necesarios para describir conceptos centrales como el de número:

Ejemplo:

1. Factorial

Definición:

factorial (n) = n! si n > 0

factorial (n) = n*n-1*n-2* ... * 1 si n > 0

el valor de 0! se define como

factorial (0) = 1

Su definición recursiva es:

factorial (n) = 1 si n = 0

factorial (n) = n* factorial (n-1) si n > 0

así para calcular el factorial de 4:

factorial (4) = 4 * factorial (3) = 4 * 6 = 24

factorial (3) = 3 * factorial (2) = 3 *2 = 6

factorial (2) = 2 * factorial (1) = 2 * 1 = 2

factorial (1) = 1 * factorial (0) = 1 * 1 = 1

estáticaint factorial (int n)

comienza

sin = 0 entonces

regresa1

otro

regresafactorial (n-1) * n

termina

Versión iterativa:

estáticaint factorial (int n)

comienza

fact 1

parai 1 hastan

fact i * fact

regresafact

termina

Las definiciones recursivas de funciones en matemáticas que tienen como argumentos números enteros, se llaman relaciones de recurrencia.

Forma de una ecuación de recurrencia:

c_oa_r+c₁a_r-1+ c₂a_r-2+ ....+ c_ka_r-k= f(r) función matemática discreta

donde c_ison constantes, es llamada una ecuación de recurrencia de coeficientes constantes de orden k, condicionada a que c₀y c_k= 0.

Definición:Cuando una llamada recursiva es la última posición ejecutada del procedimiento se llama recursividad de cola, recursividad de extremo final o recursión de extremo de cola.

Definición:Cuando un procedimiento incluye una llamada a si mismo se conoce como recursión directa.

Definición:Cuando un procedimiento llama a otro procedimiento y este causa que el procedimiento original sea invocado, se conoce como recursión indirecta.

Una definición recursiva dice cómo obtener conceptos nuevos empleando el mismo concepto que intenta definir.

El poder de la recursividad es que los procedimientos o conceptos complejos pueden expresarse de una forma simple.

Un razonamiento recursivo tiene dos partes: la base y la regla recursiva de construcción. La base no es recursiva y es el punto tanto de partida como de terminación de la definición.

La recursividad es un método poderoso usado en inteligencia artificial, su poder es que algunos conceptos complejos pueden expresarse en una forma simple. Una definición recursiva difiere de una definición circular en que tiene una forma de escapar de su expansión infinita. Este escape se encuentra en la definición o porción no recursiva o terminal de la definición.

Las fórmulas recursivas pueden aplicarse a situaciones tales como prueba de teoremas, solución de problemas combinatorios, algunos acertijos, etc.

Al principio algunas personas se sienten un poco incómodas con la recursividad, tal vez porque da la impresión de ser un ciclo infinito, pero en realidad es menos peligrosa una recursión infinita que un ciclo infinito, ya que una recursividad infinita pronto se queda sin espacio y termina el programa, mientras que la iteración infinita puede continuar mientras no se termine en forma manual.

Cuando un procedimiento recursivo se llama recursivamente a si mismo varias veces, para cada llamada se crean copias independientes de las variables declaradas en el procedimiento.