Lenguajes de programación: Recursividad-LABORATORIO

Se llama recursividad a una función que se llama a sí misma.

Utilidad

Cuando se puede describir un problema de la misma naturaleza, aunque de menor complejidad.

Pero se tiene que conocer la solución no recursiva para el caso más sencillo, es decir el caso base y hacer que la división de nuestro problema acabe recurriendo al caso base.

¿Cómo es que funciona?

El problema se va descomponiendo en subproblemas cada vez de menor complejidad.
Se tiene que llegar al caso base.
Con las soluciones parciales se llega a la solución final.

Diseño de la función recursiva

Solución para el caso general, que es dónde se aplica la recursión y pueden añadirse otros pasos adicionales para juntar las soluciones parciales.
Solución para el caso base, debe existir por lo menos un caso base y no debe ser recursivo.

Aspectos a considerarse para decidir entre recursión o iteración

El tiempo que puede tardarse en realizar las recursiones y el uso de memoria.
La redundancia ya que algunas soluciones recursivas suelen resolver un problema en repetidas ocasiones.
Aveces es necesaria la recursión cuando es muy difícil de encontrar la solución iterativa.
La elegancia y legibilidad de una solucíon recursiva.

Ahora ejemplos para identificar los casos base y como funciona la recursión:

Factorial

Código:

#!/usr/bin/python
numero = int(input("Factorial de:"))

def factorial(numero):
if numero == 0:  #Este es el caso base
return 1
else:
return numero * factorial(numero-1) #Caso general

print factorial(numero)

Su ejecución:

Potencia

Código:

#!/usr/bin/python

base = int(input("La base es:"))
exponente = int(input("El exponente es:"))

def potencia(base, exponente):
if exponente == 0: #Este es el caso base
return 1
else:
return base * potencia(base, exponente-1) #Caso general

print potencia(base, exponente)

Y su ejecución:

Fibonacci

Código:


#!/usr/bin/python
numero = int(input("Fibonacci de:"))
def fibonacci(numero):
if numero == 0: #Caso base
return 0
if numero == 1: #Caso base
return 1
else:
return fibonacci(numero-1) + fibonacci(numero-2) #Caso recursivo

print fibonacci(numero)

Su ejecución:

Torres de Hanoi

Y por último las Torres de Hanoi que fué el tema que me tocó exponer, hay dos casos recursivos el primero es el que se encarga básicamente de pasar los discos de la torre inicial a la torre temporal, y el segundo de la torre temporal a la torre final.

Aquí les dejo el código:

#!/usr/bin/python

ndiscos = int(input("Numero de discos:"))

def Hanoi(ndiscos, inicial, temporal, final):
if ndiscos > 0:
Hanoi(ndiscos-1, inicial, final, temporal)
print 'Se mueve de la torre', inicial, 'a la torre', final
Hanoi(ndiscos-1, temporal, inicial, final)

Hanoi(ndiscos, 1, 2, 3)

Su ejecución: