RECURSIVIDAD

La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una funcion desde la misma funcion. Como ejemplo útil se puede presentar el calculo 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 parrafo 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 es un concepto importante en informatica. Muchos algoritmos se pueden describir mejor en terminos de recursividad.

Supongamos que P es un procedimiento que contiene una sentencia de Llamada a si mismo o una sentencia de Llamada a un segundo procedimiento que puede eventualmente llamar de vuelta al procedimiento original P. Entonces P se dice que es u procedimiento recursivo. Como el progrma no ha de continuar ejecutandose indefinidamente, un procedimiento recursivo ha de tener las dos siguientes propiedades:

(1) Debe existir un cierto criterio, llamado criterio base, por el que el procedimiento no se llama asi mismo.

(2) Cada vez que el procedimiento se llame a si mismo(directa o inderectamente), debe estar mas cerca del criterio base.

Un procedimiento recursivo con estas dos propiedades se dice que esta bien definido.

Similarmente, una funcion se dice que esta definida recursivamente si la definicion de la funcion se refiere a si misma. De nuevo, para que la definicion no sea circular, debe tener las dos siguientes propiedades:

(1) Debe haber ciertos argumentos, llamados valores base, para los que la funcion no se refiera a si misma.

(2) Cada vez que la funcion se refiera a si misma, el argumento de la funcion debe acercarse mas al valor base.

Una funcion recursiva con estas dos propiedades se dice tambien que esta bien definida.

Tipos.

Podemos distinguir dos tipos de recursividad:

Directa: Cuando un subprograma se llama a si mismo una o mas veces directamente. Indirecta: Cuando se definen una serie de subprogramas usándose unos a otros.

Características.

Un algoritmo recursivo consta de una parte recursiva, otra iterativa o no recursiva y un acondición de terminación. La parte recursiva y la condición de terminación siempre existen. En cambio la parte no recursiva puede coincidir con la condición de terminación. Algo muy importante a tener en cuenta cuando usemos la recursividad es que es necesario asegurarnos que llega un momento en que no hacemos más llamadas recursivas. Si no se cumple esta condición el programa no parará nunca.

Ventajas e inconvenientes. La principal ventaja es la simplicidad de comprensión y su gran potencia, favoreciendo la resolución de problemas de manera natural, sencilla y elegante; y facilidad para comprobar y convencerse de que la solución del problema es correcta. El principal inconveniente es la ineficiencia tanto en tiempo como en memoria, dado que para permitir su uso es necesario transformar el programa recursivo en otro iterativo, que utiliza bucles y pilas para almacenar las variables.

Politica de Privacidad