No es un bug, es una característica no documentada

jueves, 11 de diciembre de 2014

Programación. Recursividad (I)

18:26 Posted by Inazio , No comments
Ejercicio introductorio
Escribe una función en notación algorítmica que devuelva el factorial de un número natural introducido como parámetro

funcion factorial(n:entero) devuelve entero
{Pre: n>0}
Variables
            resultado:entero;
            indice:entero;
Principio
            resultado:=1;
            para indice:=2;indice menor que n;indice++
                        resultado=resultado*indice;
            devuelve resultado
Fin

¿Otra manera?
¿Existe otra manera cualitativamente distinta de hacer lo que nos han pedido, que suponga al mismo tiempo una forma distinta de pensar en algoritmo para dar solución a problemas?

Sí, existe otra forma, que además es más intuitiva, y hace que podamos resolver problemas con algoritmos que nos resultan más sencillos de pensar.

Solución recursiva
funcion factorial (n:entero) devuelve entero
{Pre: n>0}
Principio
            si n=1
                        entonces
                                   devolver(1);
                        si no
                                   devolver (n*factorial(n-1);
            fsi
Fin

Hasta ahora conocíamos violaciones de segmento, ahora podemos generar desbordamiento de pila (por cierto, nombre de un muy buen foro de programación: http://stackoverflow.com )

Llamadas recursivas
n*factorial(n-1);
(n-1)*factorial(n-1);
(n-1)*factorial(n-2);
(n-1)*factorial(n-3);
3*factorial(2);
2*factorial(1);
1;

Ejercicio. 
Escribe una función que calcule el máximo común divisor (mcd) de dos números naturales, a y b, sabiendo que mcd(a,b)=mcd(b, a MOD b) si a>=b, y en caso contrario, mcd(a, b)=mcd(a, b MOD a). Da una solución recursiva.
Ejemplo à mcd(60, 45) = mcd(45, 15) = mcd(15,0)

Solución:
funcion mcd(a, b:entero) devuelve entero
{ Pre: a>=0, b>=0}
Principio
            si a=0
                        entonces devolver(b);
                        si no
                                    si b=0
                                                entonces devolver(a)
                                                            si no
                                                                        si a>b
                                                                                    entonces devolver (mcd(b,a MOD b));
                                                                                    si no devolver (mcd(a,b MOD a));
                                                                        fsi
                                    fsi
            fsi
fin

Algoritmo recursivo

Un algoritmo recursivo debe tener:
è Un tratamiento de todos los casos triviales que puedan darse en el problema a resolver. Dicho tratamiento no puede hacer llamadas recursivas y sí tiene que dar una solución inmediata a esos casos triviales.
è Un tratamiento del(los) casos no trivial(es). Dicho tratamiento hará uso de una ley de recurrencia que mediante una fórmula o conjunto de acciones u operaciones resolverá el caso no trivial mediante llamadas a la propia función (o procedimiento) con parámetros “más pequeños” que converjan a uno de los casos triviales.

Para que el caso sea válido y funcione, cada llamada recursiva debe de hacer que la siguiente llamada se aproxime más a un caso trivial de forma que al final se llegue a dicho caso.

Tipos de algoritmos recursivos

Lineales. Cada invocación genera una nueva invocación y sólo una (excepto la última, claro). Un ejemplo es el anterior ejercicio del factorial.
è Final. Lo último que hace el algoritmo es precisamente esa invocación.
è No final. Tras la invocación aún hay que hacer algún cálculo en el resultado de la invocación. El ejercicio de factorial sería no lineal, ya que tras la invocación hay que hacer la multiplicación
Múltiples. Una misma invocación puede generar más de una invocación, por ejemplo, un ejercicio de calcular Fibonacci.

Inconvenientes

En general las soluciones recursivas son:
è Menos eficientes que las iterativas
è Más claras y sencillas que las iterativas

Lo bueno es pensar en recursivo e implementar en iterativo.


Podemos transformas en muchos casos los algoritmos recursivos en iterativos con más o menos dificultad.

0 comentarios:

Publicar un comentario