TIPOS DE RECURSIVIDAD

Dentro de la teoría de la recursión, se tiene que existen diferentes tipos de recursión:

Recursión directa: Cuando el código F tiene una sentencia que involucra a F.

Recursión indirecta o cruzada: Cuando la función F involucra una función G que invoca a la vez una función H, y así sucesivamente, hasta que se involucra la función F. Por ejemplo el algoritmo de Par o impar.

int par (int n)   

{

if (n==0) return n+1;   

return impar(n-1);  

}  

int impar(int n) 

{  

if (n==0) return 0;   

return par(n-1);

}

A continuación se expone otro ejemplo de programa que utiliza recursión indirecta, y nos dice si un número es par o impar. Cabe mencionar que existen otros métodos mucho más sencillos para determinar la solución a este problema, basta con determinar el resto de la división entre dos. Por ejemplo: si hacemos par(2) devuelve 1 (cierto). Si hacemos impar(4) devuelve 0 (falso).

int par(int n)
{

if (n == 0) return 1;   

return impar(n-1);

}

int impar(int n)
{

if (n == 0) return 0;   

return par(n-1);

}

Recursión simple:- Aquella en cuya función solo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iterativos.

Recursión múltiple: Se da cuando hay más de una llamada a sí misma dentro del cuerpo de la función, resultando más difícil de transformar a iterativa. Por ejemplo el algoritmo de Fibonacci.

int fibo(int n)
{

if (n<=1) return 1;

else

return fibo(n-1) + fibo(n-2);

}

¿Conoces este algoritmo en su versión iterativa?

Otro ejemplo de este tipo de recursión se encuentra en el recorrido de árboles.

Recursión anidada: En algunos de los parámetros de la llamada recursiva, hay una nueva llamada a sí misma.