Instituto Tecnológico de Saltillo
Departamento de Sistemas y Computación
RECURSIVIDAD
M.C. Juan José Contreras Gaytán
¿Qué es la Recursividad?
La recursividad o recursión es un concepto que proviene de las
matemáticas y que, aplicado al mundo de la programación, nos permite
resolver problemas o tareas donde éstas pueden ser divididas en
subtareas cuya funcionalidad es la misma.
Dado que los subproblemas a resolver son de la misma naturaleza, se
puede usar la misma función para resolverlos.
Dicho de otra manera, “…una función recursiva es aquella que está definida
en función de sí misma, por lo que se llama repetidamente a sí misma hasta
llegar a un punto de salida….”
Factorial iterativo
Definición recursiva: def factorial(n):
resultado = 1;
5! = 5 * 4 * 3 * 2 * 1 i=2
5! = 120 while i <= n:
resultado *= i
i += 1
return resultado;
if __name__ == "__main__":
n = int(input("Valor de n: "))
print("Resultado: ", factorial(n))
Ejemplo: Factorial recursivo
Definición recursiva:
n! = n * (n-1)! si n > 1
n! = 1 si n = 1 def factorial(n):
if n == 1:
return 1 #Caso base
2*factorial(1)
4 else:
3*factorial(2)
3 return n * factorial(n-1)
2
4*factorial(3)
5*factorial(4)
1 if __name__ == "__main__":
Pila n = int(input("Valor de n: "))
print("Resultado: ", factorial(n))
[Link]
Características del método recursivo
Cualquier función recursiva tiene dos secciones de código claramente
divididas:
• Por un lado, tenemos la sección en la que la función se llama a sí
misma.
• Por otro lado, tiene que existir siempre una condición en la que la
función retorna sin volver a llamarse. Es muy importante porque de
lo contrario, la función se llamaría de manera indefinida.
Ejemplo: fibonacci
Definición recursiva:
Fibo(n) = Fibo(n-1) + Fibo(n-2) si n > 1
Fibo(n) = n si n = 0, 1
def fibonacci(n):
if n == 0 or n == 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
if __name__ == "__main__":
n = int(input("Valor de n: "))
print("Resultado: ", fibonacci(n))
[Link]
Condiciones que debe cumplir un
Método Recursivo
• Asegurar que existe una condición de salida, en la
que no se producen llamadas recursivas (caso base).
• Cada llamada, en el caso no base, conduce a
problemas cada vez más pequeños que terminarán
en el caso base.
Recursividad
✓ Poderosa herramienta de programación
✓ Alternativa a algoritmos iterativos
✓ Forma elegante de programar, pero no eficiente
✓ Un método es recursivo si contiene invocaciones a sí
mismo
Ejemplo: Multiplicación Entera
Definición recursiva:
a * b = a + (a * b – 1) si b > 0 def multi (a, b) :
a * b = 0 si b = 0 if b == 0:
return 0 #Caso base
else :
return a + multi(a, b-1)
a b
if __name__ == "__main__":
4 * 3 = 4 + (4 * 2)
= 4 + 4 + (4 * 1) a = int(input("Valor de a: "))
= 4 + 4 + 4 + ( 4 * 0) b = int(input("Valor de b: "))
= 4 + 4 + 4 + 0 = 12
print("Resultado: ", multi(a, b))
Ejemplo: Sumar valores de un Vector
Escribir un método recursivo que permita sumar los elementos de un vector.
lista = [ ]
def sumaVector(vector):
if len(vector) == 1:
return vector[0]
else:
return vector[0] + sumaVector(vector[1:])
if __name__ == "__main__":
id = int(input('Ingresar elemento: (Escribe 0 para finalizar)'))
while id != 0:
[Link](id)
id = int(input(""))
print("Resultado =", sumaVector(lista))
[Link]
Ejemplo: Invertir un número
def invertir ( n ) :
if n < 10:
print(n) #Caso base
else:
print(n % 10)
invertir(n / 10)
if __name == “__main__”:
n = int(input("Valor de n: "))
invertir(n) 7654
[Link]
Bibliografía
[1] [Link]
[2]. [Link]
[3] [Link]
python-soluciones-eficientes-y-elegantes/
[4] [Link]
python/blob/master/[Link]