Funciones: recursividad¶
Función recursiva sin return¶
Una función recursiva se llama a sí misma, pero en algún momento se debe interrumpir.
Método 1¶
def cuenta_regresiva(n): # cuenta atrás (countdown) usando una función que se llama a sí misma
if n > 0:
print(n)
n -= 1
cuenta_regresiva(n) # la función se llama a si misma despues de imprimir n y reducir el valor de n en 1
else:
print("Hasta la vista, Baby.")
#print("Fin función", n) # si queremos ver cuándo termina cada una de las funciones
cuenta_regresiva(5)
Método 2¶
Se llama 'caso base' al momento en el que queremos que termite la recursividad.
def countdown(n): # cuenta atrás (countdown) usando una función que se llama a sí misma
if n == 0: # caso base
print("Despegando...")
else:
print(n)
countdown(n-1)
countdown(5)
Función recursiva con return: acumula¶
Dado un número entero n>1 sumar todos los números desde 1 hasta n.
Por ejemplo, para n=5 se obtendría la suma de 1+2+3+4+5 que es 15.
Compruebe que la suma de los números del 1 al 100 es igual a 5050.
Midiendo el mundo
Cálculo del acumulado por iteración¶
def sumando(n):
total = 0
for i in range(n+1):
total += i
return total
print(sumando(5))
Cálculo del acumulado por recursión¶
def suma(n):
if n == 0:
return 0 # definimos el resultado para el caso base
else:
return n + suma(n-1) # definimos el resultado para el resto de los casos
print(suma(5))
_ representa 'algo que aún no se'
- 5 +
_ - 4 +
_ - 3 +
_ - 2 +
_ - 1 +
_ - 0 → al llegar a cero ya devuelve algo, devuelve cero
Ahora se completa el ciclo hacia atrás, rellenando los huecos _
- 5 + 10 → 15
- 4 + 6 → 10
- 3 + 3 → 6
- 2 + 1 → 3
- 1 + 0 → 1
- 0 → 0 (ahora, empezamos a leer comenzando por el último)
Factorial de un número¶
- El factorial de 5 es:
- Por definición, el factorial de 0 es 1.
Función factorial importando la librería math¶
from math import factorial
factorial(5) # pruebe a calcular el factorial de 1000
Cálculo del factorial por iteración¶
def factor(n):
f = 1 #por definición el factorial de cero es 1
for i in range(1, n+1):
f *= i
return f
n = 5
print("El producto de 5*4*3*2*1 es", 5*4*3*2*1)
print("El factorial de", n, "es", factor(n))
Cálculo del factorial por recursión¶
def fac(n):
if n == 0: # condición de parada
return 1 # caso base
else:
return n * fac(n-1) # equivale a else:n*=fac(n-1);return n
n = 5
print(f"El factorial de {n} es {fac(n)}")
Imprimir una lista por recursividad¶
Dada una lista imprimir sus elementos comenzando desde un índice dado.
def imprimir_lista(l, i): # l es la lista e i es el índice por el que comenzar a imprimir
if i != len(l):
print(l[i])
imprimir_lista(l, i+1) # al poner i+1 estamos comenzando el proceso, pero habiendo incrementado i en 1
l = [6, 7, 8, 9]
imprimir_lista(l, 0) # Estamos pidiendo comenzar por el índice 0
Sucesión de Fibonacci¶
Fibonacci por iteraciones¶
fibo=[0, 1]
for i in range (17):
fibo.append(fibo[-1] + fibo[-2])
print(fibo)
Fibonacci por recursión¶
def fib(n):
if n <= 0: return 0
if n == 1: return 1
return fib(n-1) + fib(n-2)
#print(fib(18)) # 2584
[fib(i) for i in range(19)]
Otra versión similar a la anterior con una línea menos.
def fib(n): # necesariamente debe ser n>=0
if n <= 1: return n # si n=1 retorna 1. si n=0 retorna 0
return fib(n-1) + fib(n-2)
[fib(i) for i in range(19)]
Ejercicio
Encuentre la suma de todos los términos pares en Fibonacci que no superen los cuatro millones.
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)
if __name__ == "__main__":
n = valor = suma = 0
while True:
valor = fib(n)
if valor > 4_000_000:
break
suma += valor
print(f"n={n:2}, fib({n:2d})={valor:7}, suma={suma:7}")
n += 2 # comenzando en n=0 da los pares
Reverso de un string por recursión¶
def reverso(cadena):
if len(cadena) == 0: return ''
return cadena[-1] + reverso(cadena[:-1])
print(reverso('sogima'))
Ejercicio del palíndromo
- Detecte si una palabra es un palíndromo o no
- Resuelva el caso con una función por iteraciones y por recursividad.
- ¿Cuál de las dos versiones le resulta preferible?
Ventajas de la recursión¶
- Al dividir el problema en partes más pequeña es más abordable.
- Puede llegar a mostrarse un código más limpio y ordenado.
Inconvenientes de la recursión¶
- La lógica es difícil de seguir.
- En Python la llamada recursiva a una función ocupa una gran cantidad de memoria ya que permanece abierta cada una de las llamadas (cada una de las instancias).
- Python establecen en 3000 en número límite de llamadas recursivas a una función, después de ello arroja un error.
RecursionError: maximum recursion depth exceeded in comparison
- Si la recursividad es demasiado profunda, puede quedarse sin espacio de pila, lo que se denomina desbordamiento de pila (stack overflow).
- Otro inconveniente es que las subfunciones recursivas requieren mucho tiempo por lo que son ineficientes.
import sys
sys.getrecursionlimit()
Ese límite se podría ampliar.
#import sys
#sys.setrecursionlimit(5000)
¿Cómo crear un stack overflow?¶
Una forma sencilla de crear un desbordamiento de pila es crear una función que se llame a si misma.
Se producirá un error del tipo:
- RecursionError: maximum recursion depth exceeded
def hola():
hola()
hola()
Calcular el máximo¶
Ya existe una función en Python que calcula el máximo de varios números, pero vamos a crear nuestra propia función para calcular el máximo por iteración y por recursividad.
Función max interna de Python¶
max(3, 9, 6)
Función máximo creada por iteración¶
def mimax(*numeros): #se pone * cuando el número de datos de entrada es indeterminado
maximo = numeros[0]
for numero in numeros:
if numero > maximo:
maximo = numero
return maximo
print(mimax(3, 9, 6))
def mymax(numeros): # usando una lista no es necesario usar *
maximo = numeros[0]
for numero in numeros:
if numero > maximo:
maximo = numero
return maximo
lista=[3, 9, 6]
print(mymax(lista))
Función máximo creada por recursión¶
Método 1 por recursión¶
def maximo(l):
if len(l) == 1: return l[0]
else: return max(l[0], maximo(l[1:])) #calcula el max entre el primer elemento de la lista y el resto de ella
num=[3, 9, 6]
maximo(num)
Una variante del código anterior, ahora usando el final de la lista.
def maxi(l):
if len(l)==1: return l[0]
return max(l[-1], maxi(l[:-1])) #calcula el max entre el último elemento de la lista y el resto de ella
lista=[3, 9, 6]
maxi(lista)
Método 2 por recursión¶
Otro método, en este caso sin usar la función matemática max.
Se comparan el último y el primer elemento de la lista y se va dejando el mayor en la primera posición.
def maximo(li): # al final la lista li solo tendrá un elemento que será el máximo
if len(li) == 1: return li[0] # caso base: el máximo habrá quedado en la primera posición de la lista
else:
li[-1] > li[0] # actúa si el último valor de la lista es mayor
li[-1], li[0] = li[0], li[-1] # permutamos los valores, último y primero de la lista
li.pop() # eliminamos el último valor de la lista
return maximo(li)
li=[3, 9, 6]
maximo(li)
Método 3 por recursión¶
Sin usar la función matemática max y sin ir eliminando el último elemento de la lista.
def maximiza(l):
if len(l) == 1:
return l[0]
else:
candidato = maximiza(l[1:])
m = l[0]
if candidato > m:
m = candidato
return m
num=[3, 9, 6] # si la lista estuviera vacía daría error y necesitaríamos control de errores
maximiza(num)
Máximo Común Divisor¶
MCD con la librería math.gcd¶
from math import gcd
gcd(300, 33880)
El inconveniente de esta librería es que solo calcula el MCD de dos números.
Existe una propiedad del MCD que dice:
gcd(a,b,c) = gcd(gcd(a,b),c) para 0≠a, b, c∈Z
MCD por recursión¶
from math import gcd
def mcd(l):
if len(l)==2:
return gcd(l[0], l[1])
else:
return gcd(l[-1], mcd(l[:-1]))
lista = [300, 33880, 70]
mcd(lista)