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