ALGORITMOS PYTHON-páginas-5

Vista previa del material en texto

[21]
Como se puede observar en el ejemplo anterior, mediante el modelo recursivo se puede dividir un 
problema en pequeños subproblemas, y para poder resolver cada uno de estos se necesitará de la 
solución del caso siguiente o anterior (dependiendo del problema). Estas quedarán pendiente en 
memoria para resolver cuando se alcance una condición de fin o caso base, y el algoritmo retroceda 
resolviendo cada una de estas llamadas que quedó en espera y liberando la memoria hasta obtener 
el resultado final.
A continuación se puede observar en la figura 2 cómo se programa esta técnica en Python para dar 
solución al problema antes planteado:
Figura 2. Implementación de función recursiva en Python
Para poder entender cómo resolver un problema de forma recursiva, analicemos detalladamente 
los pasos del algoritmo anterior que dan solución al ejemplo del factorial:
1. Primero recuerde que en programación para representar el modelo recursivo se hace a través 
de una función recursiva, en la cual se define su nombre y los parámetros de entrada.
2. Mediante condicionales (if-else) se determinan las condiciones de fin. Debe tener al menos una.
3. Llamada recursiva de sí misma, es decir que dentro de la función debe llamarse a sí misma.
4. En el ejemplo gráfico (tablas) a medida que se reemplaza el valor de un problema por su resul-
tado, se actualiza el valor del resultado a calcular. Cuando se desarrolla una función recursiva 
debemos recordar que cuando se realizan estas llamadas hay que actualizar los parámetros de 
entrada. En dicha llamada esto es sumamente importante ya que será lo que permitirá lograr 
alcanzar la condición de fin y no caer en un ciclo infinito de llamadas recursivas y que se des-
borde la pila de llamadas en memoria. En este caso particular cuando se llama a sí misma se le 
resta uno al valor de la variable e.
5. Como es una función debe devolver un resultado. En este caso puede devolver uno de los valores 
de las condiciones de fin, o el resultado de llamada recursiva con su correspondiente tratamiento.
[22]
Ahora veamos otro ejemplo. En esta ocasión en la figura 3 se puede observar el algoritmo recursivo 
e iterativo para resolver un mismo problema, obtener el valor en la sucesión de Fibonacci de un 
número n dado.
Figura 3. Algoritmo Fibonacci recursivo e iterativo
Claramente hay una diferencia entre ambas funciones. La primera –versión recursiva arriba en la 
figura – solo son cuatro líneas de código y refleja el modelo matemático de la sucesión de Fibonacci. 
En cambio la segunda –versión iterativa abajo en la figura– es necesario hacer un tratamiento parti-
cular para lograr representar el modelo de dicha sucesión que llevará algunas líneas más de código.
El modelo recursivo, como se dijo anteriormente, permite dividir un problema grande en proble-
mas más pequeños sin alterar la naturaleza del problema y su solución. Sin embargo, esto no impli-
ca que esta sea la mejor solución. Estos problemas también pueden ser resueltos de manera iterati-
va, para ello es necesario utilizar alguna de las estructuras de control de ciclo y variables auxiliares 
para almacenar los resultados (acumuladores, contadores o auxiliares) que reemplace las llamadas 
recursivas. Esto muchas veces cambiará la estrategia utilizada para resolver el problema. Además 
al tener dos alternativas a la hora de resolver un determinado problema, es muy importante que se 
analicen las ventajas y desventajas de implementar y desarrollar una solución recursiva o iterativa.
El modelo recursivo brinda ciertas ventajas respecto al iterativo, entre ellas se puede destacar que 
el código a desarrollar es más claro y sencillo, dado que se respeta el modelo del problema y la 
solución. La mayor desventaja del modelo recursivo frente al iterativo es que, dependiendo de la 
[23]
dimensión del problema a tratar y las estructuras de datos donde se implemente –en particular si 
este es muy grande–, la cantidad de llamadas recursivas necesarias para llegar hasta el caso base 
pueden ser muchas y podría desbordar la pila de memoria disponible para esta actividad. En cam-
bio, el modelo iterativo solo requiere de un ciclo formado por una variable de control, más las va-
riables auxiliares para los resultados. De tal forma se consume mucha menos cantidad de memoria.
En el siguiente capítulo se presentarán técnicas que permiten comparar un algoritmo recursivo 
frente a uno iterativo, de esta manera se logrará dominar los criterios suficientes para optar entre 
una implementación recursiva o una iterativa de un determinado algoritmo.
[24]
Guía de ejercicios prácticos
A continuación planteamos una serie de problemas. Para resolverlos se deberá desarrollar una fun-
ción recursiva.
1. Implementar una función que permita obtener el valor en la sucesión de Fibonacci para un 
número dado.
2. Implementar una función que calcule la suma de todos los números enteros comprendidos 
entre cero y un número entero positivo dado.
3. Implementar una función para calcular el producto de dos números enteros dados.
4. Implementar una función para calcular la potencia dado dos números enteros, el primero re-
presenta la base y segundo el exponente.
5. Desarrollar una función que permita convertir un número romano en un número decimal.
6. Dada una secuencia de caracteres, obtener dicha secuencia invertida.
7. Desarrollar un algoritmo que permita calcular la siguiente serie:
8. Desarrollar un algoritmo que permita convertir un número entero en sistema decimal a siste-
ma binario.
9. Implementar una función para calcular el logaritmo entero de número n en una base b. Re-
cuerde que:
10. Desarrollar un algoritmo que cuente la cantidad de dígitos de un número entero.
11. Desarrollar un algoritmo que invierta un número entero sin convertirlo a cadena.
12. Desarrollar el algoritmo de Euclides para calcular el máximo común divisor (MCD) de dos 
número entero.
13. Desarrollar el algoritmo de Euclides para calcular también el mínimo común múltiplo (MCM) 
de dos número entero.
14. Desarrollar un algoritmo que permita realizar la suma de los dígitos de un número entero, no 
se puede convertir el número a cadena.
[25]
15. Desarrollar una función que permita calcular la raíz cuadrada entera de un número entero. 
Puede utilizar una función auxiliar para que la función principal solo reciba como parámetro 
el número a calcular su raíz.
16. Implementar un función recursiva que permita obtener el valor de an en una sucesión geomé-
trica (o progresión geométrica) con un valor a1= 2 y una razón r = -3. Además desarrollar un 
algoritmo que permita visualizar todos los valores de dicha sucesión desde a1 hasta an.
17. Escribir una función recursiva que permita mostrar los valores de un vector de atrás hacia adelante.
18. Implementar una función recursiva que permita recorrer una matriz y mostrar sus valores.
19. Dada la siguiente definición de sucesión recursiva, realizar una función recursiva que permita 
calcular el valor de un determinado número en dicha sucesión.
20. Desarrollar un algoritmo que permita implementar la búsqueda secuencial con centinela de 
manera recursiva, y permita determinar si un valor dado está o no en dicha lista.
21. Dada una lista de valores ordenadas, desarrollar un algoritmo que modifique el método de 
búsqueda binaria para que funcione de forma recursiva, y permita determinar si un valor dado 
está o no en dicha lista.
22. El problema de la mochila Jedi. Suponga que un Jedi (Luke Skywalker, Obi-Wan Kenobi, Rey u 
otro, el que más le guste) está atrapado, pero muy cerca está su mochila que contiene muchos 
objetos. Implementar una función recursiva llamada “usar la fuerza” que le permita al Jedi “con 
ayuda de la fuerza” realizar las siguientes actividades:
a. sacar los objetos de la mochila de a uno a la vez hasta encontrar un sable de luz o que no 
queden más objetos en la mochila;
b. determinar si la mochila contiene un sable de luz y cuantos objetos fueron necesarios sa-
car para encontrarlo;c. Utilizar un vector para representar la mochila.
23. Salida del laberinto. Encontrar un camino que permita salir de un laberinto definido en una 
matriz de [n x n], solo se puede mover de a una casilla a la vez –no se puede mover en diagonal– 
y que la misma sea adyacente y no esté marcada como pared. Se comenzará en la casilla (0, 0) 
y se termina en la (n-1, n-1). Se mueve a la siguiente casilla si es posible, cuando no se pueda 
avanzar hay que retroceder sobre los pasos dados en busca de un camino alternativo.