Busqueda

Resultados

jueves, 5 de noviembre de 2009

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.
Se puede decir que la recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:
Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (menores que N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base ( o lo que llamo criterio de parada), se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.
La recursividad es un concepto importante en informática. Muchos algoritmos se pueden describir mejor en términos 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 un procedimiento recursivo. Como el programa 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 así mismo.
  2. Cada vez que el procedimiento se llame a si mismo(directa o indirectamente), debe estar mas cerca del criterio base.
Un procedimiento recursivo con estas dos propiedades se dice que esta bien definido.

Análogamente, una función se dice que esta definida recursivamente si la definición de la función se refiere a si misma. De nuevo, para que la definición no sea circular, debe tener las dos siguientes propiedades:
  1. Debe haber ciertos argumentos, llamados valores base, para los que la función no se refiera a si misma.
  2. Cada vez que la función se refiera a si misma, el argumento de la función debe acercarse más al valor base.
Una función recursiva con estas dos propiedades se dice también 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 una condició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 se use 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 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.

Ejemplos

function factorial(n : integer): longint;
begin
if n=0 then factorial := 1 (** Criterio base o condici¢n de parada **)
else factorial := n*factorial(n-1); (** simplificaci¢n del problema **)
end;

/*Máximo comun divisor */

function MCD(m,n : integer): integer;
begin
if (m mod n)=0 then MCD := n (* Criterio base o condici¢n de parada **)
else MCD := MCD(n, m mod n); (** simplificaci¢n del problema **)
end;


miércoles, 4 de noviembre de 2009

Ejercicios de recuperación

Para aquellos estudiantes que vienen con baja nota y desean recuperar, les propongo desarrollar uno y sólo uno de los dos ejercicios propuestos en la entrada anterior, especificamente el número 13 y el número 16, ustedes deciden cual hacer.

La entrega es estrictamente individual.
Debe ser entregado impreso o a mano y documentado.
Debe ser entregado para el dia 30/11/2009.