Concepto De Recursividad

Concepto de 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 cálculo 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.

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.

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.

Procedimeintos recursivos.

Un procedimiento o función recursiva es aquella que se llama así misma

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 ves una función H,

y así sucesivamente, hasta que se involucra la función F. Por ejemplo el algoritmo de

Par o impar.

Recursión simple.- Aquella en cuya función solo aparece una llamada

recursiva. Se puede transformar con facilidad en algoritmos iteractivos.

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 iteractiva. Poe

ejemplo el algoritmo de Fibonacc

Recursión anidada.- En algunos de los argumentos de la llamada hay

una nueva llamada a sí misma. Por ejemplo la función de Ackerman:

int Ack(int m, int n)

{ if (m==0) return n+1

if (n=00) return Ack(n-1, 1)

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

}

Uni.

Al estar trabajando con recursividad, la memoria de la computadora hace uso

de una pila de recursión, la cual se divide de manera lógica en 4 segmentos:

1. Segmento de código.- Parte de la memoria donde se guardan las

instrucciones del programa en código máquina.

2. Segmento de datos.- Parte de la memoria destinada a almacenar las variables

estáticas.

3. Montículo.- Parte de la memoria destinada a las variables dinámicas.

4. Pila de programa.- parte destinada a las variables locales y parámetros de la

función que está siendo ejecutada.

Funciones mutuamente recursivas.

Cuando se trabaja llamados a la ejecución de las funciones, se provocan las

siguientes operaciones:

1. Reservar espacio en la pila para los parámetros de la función y sus variables

locales.

2. Guardar en la pila la dirección de la línea de código desde donde se ha

llamado a la función.

3. Almacenar los parámetros de la función y sus valores de pila.

4. Al terminar la función, se libera la memoria asignada en la pila y se vuelve a la

instrucción actual.

Pero cuando se trabaja con funciones recursivas, se provoca además lo

siguiente:

1. La función se ejecutará normalmente hasta la llamada a sí misma. En ese

momento se crean en la pila nuevos parámetros y variables locales.

2. El nuevo ejemplar de función comienza a ejecutarse.

3. Se crean más copias hasta llegar a la primera llamada (ultima en cerrarse).

Recursión infinita

La iteración y la recursión pueden producirse infinitamente. Un bucle infinito

ocurre si la prueba o test de continuación del bucle nunca se vuelve falsa. Una

recursión infinita ocurre si la etapa de recursión no reduce el problema en cada

ocasión de modo que converja sobre el caso base o condición de la salida.

En un algoritmo recursivo distinguimos como mínimo 2 partes:

a). Caso trivial, base o de fin de recursión:

Es un caso donde el problema puede resolverse sin tener que hacer uso de

una nueva llamada a sí mismo. Evita la continuación indefinida de las partes

recursivas.

b). Parte puramente recursiva:

Relaciona el resultado del algoritmo con resultados de casos más simples. Se

hacen nuevas llamadas a la función, pero están más próximas al caso base.

La recursividad en diseño se refiere a la manera de cómo representar los

procedimientos recursivos al momento de diseñar los programas.

Un ejemplo en ukna función genérica seria este:

METODO1

{

Procedimiento x

Condición ( )

{

Llamada al metodo1;

}

Fin;

}

En un diagrama seria algo así:

Seudocódigo:

1. Creamos la forma que contendrá una listbox para despliegue.

2. Creamos el arreglo que contendrá los elementos (vocales)

3. Después creamos el método despliegue. El cual contendrá:

a. Un ciclo for (int i=0;i_4;i++) dentro del cual se hará el despliegue en el índice

i del arreglo vocales

b. llamara al método despliegue.

Seudocódigo:

...