RECURSIVIDAD DEFINICIÓN

RECURSIVIDAD DEFINICIÓN

Es una técnica que permite que una función se llame a si misma. El concepto de recursividad va ligado a la repetición. Son recursivos aquellos algoritmos que, estando encapsulados dentro de una función, son llamados desde ella misma una y otra vez, en contraposición al los algoritmos iterativos que hacen uso de los ciclos repetitivos.

Existen varios tipos de recursividad pero todos ocurren cuando una función se llama así misma. Esto no provoca un bucle infinito, pero para evitar este problema se construye una "condición de escape", cuando el número es suficiente pequeño se termina la recursión y se regresa un valor fijo.

TIPOS DE RECURSIVIDAD

Recursividad Simple

Aquella en cuya definición aparece una llamada recursiva. Se puede transformar fácilmente en algoritmos iterativos. En conclusión la función se llama a sí mismo una sola vez.

Ejemplo:

Para poder calcular la factorial de un número se utiliza la recursividad simple pues la factorial se lo puede expresar de la siguiente manera:

n!=n*( n-1)

Es así como podemos desarrollar la función recursiva que determine la factorial de un número ingresado.

int factorial (int n)

{

if (n==0 || n==1)

Return 1;

else

return n*factorial de (n-1);

}

Recursividad Múltiple

Se da cuando hay más de una llamada a si mismo dentro del cuerpo de la función, resultando más difícil desarrollarlo de manera iterativa.

Ejemplo:

Para hallar el enésimo termina de la serie de Fibonacci se lo realiza de forma simple usando la recursividad.

int Fibonacci (int n)

{

If(n==0)

return 0;

If (n==1)

Return 1;

Else

Return Fibonacci (n-2) + Fibonacci (n-1);

}

Es mucho más sencillo usar la recursividad pues se va descomponiendo el proceso hasta llegar a proceso más simples que nos permiten encontrar la solución de nuestro problema.

Recursividad anidada

En alguno de los argumentos de la llamada recursiva hay una nueva llamada a sí mismo.

Ejemplo:

La función de Ackermann es una función recursiva que toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define como sigue:

En código C, se tiene que:

int ack (int m, int n)

{

If (n==0)

Return (m+1);

else

If (m==o)

Return (ack (n-1 , 1));

return (ack (n-1, ack(n , m-1)));

}

...