Recursion Assigment

Ejercicios sobre funciones recurrentes
Objetivos
•
•

Desarrollar habilidad para diseñar e implementar soluciones recursivas o recurrentes
Establecer criterios para comparar solucionesiterativas y recursivas para un mismo problema

Preludio
Muchos autores hablan de las reglas básicas de la recursión. Estas son:
1.
2.

3.
4.

Casos Base. Siempre debe haber al menos un caso de base(o de escape) en el cual la función hace el trabajo sin
necesidad de recurrir.
Recurra sobre “casos más pequeños”. Cuando se haga un llamado recursivo, este debe tener un parámetro, en algúnsentido, más pequeño que el original. Es decir, el parámetro de la recursión debe estar “más cerca” del caso base que el
parámetro del llamado original.
Tenga fe en que el llamado recursivo hace sutrabajo. Crea que el llamado recursivo hace el trabajo correcto, y que
una vez termina, ya se tiene disponible el resultado esperado
Algunas formas de recursión son terriblemente derrochadoras de tiempoy espacio. Se debe tener cuidado con las
recursiones porque en ocasiones, aunque entregan la respuesta correcta, también hacen una enorme cantidad de trabajo
redundante.

Las reglas 1 y 2 se debensatisfacer en cualquier recursión, porque de lo contrario la computación no termina.
La regla 3 es importante. Cuando usted esté diseñando una función recursiva para resolver un problema, deberíapensar en
cómo obtener la solución a partir de las soluciones de versiones más simples o pequeñas del mismo problema.
La regla 4 tiene que ver con la eficiencia de la solución. Puede ser que elalgoritmo solución requiera demasiado tiempo y
espacio (memoria) para ejecutarse, hasta el punto de que no sea útil o sea mucho mejor una solución iterativa.
Ejercicios
Haga un solo archivo fuente queincluya al menos un subprograma para cada uno de los siguientes problemas:
I. Escriba una función recurrente, long mcd(long n, long m) que retorne el máximo común divisor de n y m. Use
la siguiente...