RECURSIVIDAD

La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * ..., incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial.

El siguiente párrafo muestra una función, expresada con palabras, que calcula un factorial.

"Si el número es menor que cero, se rechaza. Si no es un entero, se redondea al siguiente entero. Si el número es cero, su factorial es uno. Si el número es mayor que cero, se multiplica por él factorial del número menor inmediato."

Para calcular el factorial de cualquier número mayor que cero hay que calcular como mínimo el factorial de otro número. La función que se utiliza es la función en la que se encuentra en estos momentos, esta función debe llamarse a sí misma para el número menor inmediato, para poder ejecutarse en el número actual. Esto es un ejemplo de recursividad.

La recursividad y la iteración (ejecución en bucle) están muy relacionadas, cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración y viceversa. Normalmente, un cálculo determinado se prestará a una técnica u otra, sólo necesita elegir el enfoque más natural o con el que se sienta más cómodo.

Claramente, esta técnica puede constituir un modo de meterse en problemas. Es fácil crear una función recursiva que no llegue a devolver nunca un resultado definitivo y no pueda llegar a un punto de finalización. Este tipo de recursividad hace que el sistema ejecute lo que se conoce como bucle "infinito".

Para entender mejor lo que en realidad es el concepto de recursión veamos un poco lo referente a la secuencia de Fibonacci.

0,1,1,2,3,5,8,13,21,34,...,

Cada elemento en esta secuencia es la suma de los precedentes (por ejemplo 0 + 1 = 0, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, ...) sean fib(0) = 0, fib (1) = 1 y así sucesivamente, entonces puede definirse la secuencia de Fibonacci mediante la definición recursiva (define un objeto en términos de un caso mas simple de si mismo):

fib (n) = n if n = = 0 or n = = 1

fib (n) = fib (n - 2) + fib (n - 1) if n >= 2

-Solución recursiva
static int fibonacci (int n)
{
if ((n == 0) || (n == 1))
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);
}

-Solución iterativa
static int fibonacci (int n)
{
int actual, ant1, ant2;
ant1 = ant2 = 1;
if ((n == 0) || (n == 1)) {
actual = 1;
} else
for (i=2; i<=n; i++) { actual = ant1 + ant2; ant2 = ant1; ant1 = actual; } } return actual; }

Un requisito importante para que sea correcto un algoritmo recursivo es que no genere una secuencia infinita de llamadas así mismo. Claro que cualquier algoritmo que genere tal secuencia no termina nunca. Una función recursiva f debe definirse en términos que no impliquen a f al menos en un argumento o grupo de argumentos. Debe existir una "salida" de la secuencia de llamadas recursivas.

Si en esta salida no puede calcularse ninguna función recursiva. Cualquier caso de definición recursiva o invocación de un algoritmo recursivo tiene que reducirse a la larga a alguna manipulación de uno o casos mas simples no recursivos.

-Bibliografia
http://www.monografias.com/trabajos14/recursividad/recursividad.shtml
http://elvex.ugr.es/decsai/java/pdf/7C-Ejemplos.pdf