Recursión

Objetivos

Durante esta actividad, los alumnos serán capaces de:

Resolver diferentes problemas que involucren el uso de recursión e iteración.

Esta actividad promueve las siguientes habilidades, valores y actitudes: análisis y síntesis, capacidad de resolver problemas, creatividad, y uso eficiente de la informática y las telecomunicaciones.

Descripción

Esta actividad puede ser elaborada de manera individual o en parejas.

Usando el lenguaje de programación Python versión 3.2, escribe las funciones que se describen a continuación. Coloca todas las funciones en un mismo archivo llamado tarea_recursion.py. En la parte superior del archivo coloca en comentarios los datos personales de los autores de la tarea. Por ejemplo:

#--------------------------------------------------------------------
# Actividad de programación: Recursión
# Fecha: 31-Ago-2012
# Autores:
#           1166611 Pepper Pots  
#           1160611 Anthony Stark
#--------------------------------------------------------------------

Utilizando recursión, escribe la función suma_consecutiva_recursiva(a, b), la cual devuelve la suma todos los enteros consecutivos entre a y b inclusive. Devuelve 0 si a es mayor que b.

Ejemplos:
```
>>> suma_consecutiva_recursiva(10, 15)
75
>>> suma_consecutiva_recursiva(1, 100)
5050
>>> suma_consecutiva_recursiva(6, 5)
0
>>> suma_consecutiva_recursiva(42, 42)
42
```
Escribe la función suma_consecutiva_iterativa(a, b), la cual funciona de la misma manera que la función del problema anterior, pero usando iteración en lugar de recursión. Utiliza los mismos ejemplos para probarla.

Utilizando recursión, escribe la función imprime_lista_recursiva(lst, inicio, fin), la cual imprime uno por uno los elementos de la lista lst empezando en el índice inicio y terminando en el índice fin. Solo imprime los elementos cuyos índices sean menores a la longitud de lst. No hace nada si inicio es mayor que fin.

Ejemplos:

enanos = ['Balin', 'Bifur', 'Bofur', 'Bombur', 'Dori', 
          'Dwalin', 'Fili', 'Gloin', 'Kili', 'Nori', 
          'Oin', 'Ori', 'Thorin']
>>> imprime_lista_recursiva(enanos, 0, 3)
Balin
Bifur
Bofur
Bombur
>>> imprime_lista_recursiva(enanos, 7, 10)
Gloin
Kili
Nori
Oin
>>> imprime_lista_recursiva(enanos, 5, 3)
>>> imprime_lista_recursiva(enanos, 10, 20)
Oin
Ori
Thorin
>>> imprime_lista_recursiva(enanos, 15, 20)
>>> imprime_lista_recursiva(enanos, 12, 12)
Thorin

Escribe la función imprime_lista_iterativa(lst, inicio, fin), la cual funciona de la misma manera que la función del problema anterior, pero usando iteración en lugar de recursión. Utiliza los mismos ejemplos para probarla.
Escribe la función arbol_chueco(longitud) que funciona similar a la función arbol vista en clase pero con un resultado como el que se muestra a continuación:

Es importante notar que en cada paso:
- La rama izquierda es del doble de tamaño que la rama derecha.
- Hay una separación de 60° entre ambas ramas.
Escribe la función arbol_tri(longitud), la cual dibuja un árbol de tres ramas en lugar de dos, tal como se muestra a continuación:
La curva de Hilbert es una curva fractal inicialmente descrita por el matemático alemán David Hilbert en 1891. La curva está formada por cuatro partes que se pueden describir recursivamente como sigue:

Siguiendo esta descripción, la parte A se puede codificar como la función A en Python de la siguiente manera:
```
def A(orden, longitud):
    if orden > 0:
        D(orden - 1, longitud)
        setheading(180)
        fd(longitud)
        A(orden - 1, longitud)
        setheading(270)
        fd(longitud)
        A(orden - 1, longitud)
        setheading(0)
        fd(longitud)
        B(orden - 1, longitud)
```
La función setheading se usa para orientar a la tortuga en base al siguiente esquema:

Escribe las funciones B, C y D restantes para poder dibujar una curva de Hilbert dado un cierto orden y una cierta longitud.

Ejemplos:
```
A(1, 140) # Curva de Hilbert de orden 1
```
```
A(2, 45) # Curva de Hilbert de orden 2
```
```
A(3, 20) # Curva de Hilbert de orden 3
```
```
A(4, 10) # Curva de Hilbert de orden 4
```
```
A(5, 5) # Curva de Hilbert de orden 5
```

¿Qué se debe entregar?

Sube el archivo tarea_recursion.py usando el Sistema de Entrega de Tareas Automatizado. No se aceptan tareas por ningún otro medio.

Fecha límite: Viernes, 31 de agosto.

Evaluación

Esta actividad será evaluada usando los siguientes criterios:

100	La actividad cumple con todos los requerimientos.
-10	No se incluyó en comentario los datos de los autores.
10	El programa fuente contiene errores sintácticos.
50-90	El programa produce algunos errores al momento de correrlo.
DA	La solución es un plagio.

Estructura de datos

Recursión

Objetivos

Descripción

¿Qué se debe entregar?

Evaluación