Programación. Recursividad (I)

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.