7. Recursión como herramienta en resolución de problemas computacionales

RECURSIVIDAD

Recursividad: técnica con la que un problema se resuelve sustituyéndolo por otro problema de la misma forma pero más simple.

·         Un objeto es recursivo si su definición requiérela definición previa del objeto en un caso más sencillo.

·         Una función es recursiva si su resolución requiere la solución previa de la función para casos más sencillos.

ALGORITMO RECURSIVO

Un 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.

• Es una herramienta muy potente, útil y sencilla. 
• Ciertos problemas se adaptan de forma natural a soluciones recursivas.
•  La implementación de estos algoritmos se realiza general mente en conjunto con una estructura de datos, la pila, en la cual se van almacenando los resultados parciales de cada recursión.

El ejemplo del cálculo recursivo del factorial de un número llevado al campo de la programación, en este ejemplo C++:

int factorial(int x)

{

if (x > -1 && x < 2) return 1;  // Cuando -1 < x < 2 devolvemos 1 puesto que 0! = 1 y 1! = 1

else if (x < 0) return 0;       // Error no existe factorial de números negativos

return x * factorial(x - 1);    // Si x >= 2 devolvemos el producto de x por el factorial de x - 1

}

CLASIFICACIÓN DE ALGORITMOS RECURSIVOS

• Según desde dónde se haga la llamada recursiva:
• Recursividad directa.-la función se llama a misma.
• Recursividad indirecta.- La función A llama la función B, y ésta llama a A.

• Según el número de llamadas recursivas generadas en tiempo de ejecución:
• Función recursiva lineal o simple.- Se genera una única llamada interna.
• Función recursiva no linéal o múltiple.- Se generan dos o más llamadas internas.

• Según el punto dónde se realice la llamada recursiva, las funciones recursivas pueden ser:
• Final (Trail recursion).- La llamada recursiva es la última instrucción que se produce dentro de la función.
• No Final (Non trail recursive function).- Se hace alguna operación al volver de la llamada recursiva.

Las funciones recursivas suelen ser más eficientes (en la constante multiplicativa en cuanto al tiempo, y sobre todo en cuanto al espacio de memoria) que las no lineales.
Algunos compiladores pueden optimizar automáticamente estas funciones pasandolas a iterativas.

DISEÑO DE FUNCIONES RECURSIVAS

·         El problema original se puede transformar en otro problema similar “más simple”.

·         Tenemos alguna forma directa de solucionar problemas triviales.

Etapas de diseño recursivo:

Un diseño recursivo consta de las siguientes etapas:

      1) Definición del problema

      2) Análisis de Casos. Identificación de la función limitadora.

      3) Validación de la inducción.-la función.

DISEÑO DE FUNCIONES RECURSIVAS

a) Definición del problema.- existe al menos una condición determinación en la cual no es necesaria una llamada recursiva. Son los casos triviales o bases que se solucionan directamente.

Sin =0 ón=1, el factorial es 1

b) Análisis de casos.- Cada llamada recursiva se realiza con un dato más pequeño, de forma que se llegue a la condición de terminación.

Factorial(n)=n*Factorial(n-1)

En la llamada, n va haciéndose más pequeño, y en algún momento llegará a 0 ó 1.

c) Validación de la inducción.- Si las llamadas recursivas funcionan bien, el módulo completo funciona bien.

Factorial(0)=1

Factorial(1)=1

Paran>1, si suponemos correcto el cálculo del factorial de (n-1),

Factorial(n)=n*Factorial(n-1)

VENTAJAS E INCONVENIENTES DE LA RECURSIVIDAD

Ventajas:

• Solución de problemas de manera natural, sencilla, comprensible y elegante.
• Facilidad de comprobar y verificar que la solución es correcta.

Inconvenientes:

• En general, las soluciones recursivas son más ineficientes en tiempo y espacio que las versiones iterativas, debido a las llamadas a subprogramas, la creación de variables dinámicamente en la pila, la duplicación de variables, etc.
• En general, cualquier función recursiva se puede convertir en una función iterativa.

Ventaja de la función iterativa:

• Más eficiente en tiempo y espacio.

Desventaja de la función iterativa:

• En algunos casos, muy complicada; además, suelen necesitarse estructuras de datos auxiliares.

CÁLCULO DE LA COMPLEJIDAD

En un algoritmo recursivo, la función T(n) que establece su tiempo de ejecución se da por la ecuación E(n) de recurrencia, donde en la expresión aparece la propia función T.

T(n)=E(n), y en E(n) aparece la propia función T.

Para resolver este tipo de ecuaciones hay que encontrar una expresión no recursiva de T.

 

ITERACIÓN

• En programación, Iteración es la repetición de una serie de instrucciones en un programa de computadora. Puede usarse tanto como un término genérico (como sinónimo de repetición) así como para describir una forma específica de repetición con un estado mutable. 
• A veces es necesario realizar alguna computación de manera repetida como componente del algoritmo
• Este código estará o adentro de un ciclo tal como es o se puede “vestir” como una subrutina 
• Llamas repetidas de una subrutina o la ejecución de un bloque de código en un ciclo se conoce como iteración
• Ya lo usábamos en clase por ejemplo para generar potencias de dos y los números de Fibonacci

Cuando se usa en el primer sentido, la recursividad es un ejemplo de iteración, pero que usa su propia notación (notación recursiva), que no es el caso de iteración. Sin embargo, cuando se usa en el segundo sentido (caso más restringido), la iteración describe el estilo de programación usado en lenguajes de programación imperativa. Esto está en contraposición de la recursividad, la cual tiene un enfoque más declarativo.

He aquí un ejemplo de iteración, en pseudocódigo imperativo:

 var i=0, a=0;        // inicializo a antes de comenzar la iteración

 for i from 1 to 3 {  // ciclo 3 veces

     a = a + i       // incremento a con el valor actual de i

     print a              // se imprime el número 6

     }

En este fragmento de programa, el valor de la variable i cambia a medida que la ejecución del programa progresa, tomando los valores 1, 2 y 3. Este cambio de valor —o estado mutable— es característico de una iteración.

La iteración puede aproximarse por medio de técnicas recursivas en lenguages de programación funcional. El ejemplo que sigue está escrito en Scheme. Nótese que es un código recursivo (un caso especial de iteración), pues la definición de "cómo iterar", la función iter, se llama a sí misma de manera de solucionar la instancia del problema. Específicamente, usa recursión al final de la cola, la cual está presente en lenguajes como Scheme para que no se requiera usar grandes cantidades de espacio del stack.

Fuente:

http://es.wikipedia.org/wiki/Iteraci%C3%B3n

Presentacion en PowerPoint "Algoritmos Recursivos" de M.C. Blanca Idalia Martinez Cavazos