ALGORITMO RECURSIVO (GRUPO 9)

 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

En ciencias de la computación, la recursividad es un elemento muy importante en la solución de algunos problemas. Por definición, un algoritmo recursivo es aquel que utiliza una parte de él mismo como solución al problema. La otra parte generalmente es la solución trivial, es decir, aquella cuya solución será siempre conocida, es muy fácil de calcular, o es parte de la definición del problema a resolver. Dicha solución sirve como referencia y además permite que el algoritmo tenga una cantidad finita de pasos.

Ventajas:

-Algunos problemas son esencialmente recursivos, por lo cual su implementación se facilita mediante un algoritmo de naturaleza recursiva, sin tener que cambiarlo a un método iterativo, por ejemplo. -En algunas ocasiones el código de un algoritmo recursivo es muy pequeño.

Desventajas:

-Puede llegar a utilizar grandes cantidades de memoria en un instante, pues implementa una pila cuyo tamaño crece linealmente con el número de recursiones necesarias en el algoritmo. Si los datos en cada paso es muy grande, podemos requerir grandes cantidades de memoria.

Diseño de algoritmos recursivos

Para desarrollar algoritmos recursivos siempre debe tenerse en cuenta que ya existe un algoritmo que permite resolver una versión reducida del problema; con esto en mente se procede como sigue:

1.    Identificar subproblemas atómicos (no descomponibles); estos subproblemas deben resolverse de forma directa, nunca utilizando el algoritmo general puesto que son los ya conocidos casos base.

2.    Descomponer el problema en subproblemas; estos subproblemas se resuelven apoyándose en el algoritmo que sabemos ya existe; la solución de estos subproblemas debe acercarnos de forma progresiva al caso base.

3.     Probar de manera informal que tanto los casos base como los casos generales encuentran solución aplicando el algoritmo diseñado.