Download n - TEC Digital

Recursividad
Elaborado por Mauricio Avilés
¿Qué es recursividad?
• Proceso de hacer repeticiones que se parecen
a sí mismas
• Algo compuesto de partes, las cuales
individualmente se parecen a la totalidad de
ese algo
Recursividad en las matemáticas
• Números naturales (N)
1 pertenece a N
si n pertenece a N, entonces n+1 pertenece a N
El conjunto de los números naturales es el conjunto más
pequeño que satisface esa propiedad
Recursividad en las matemáticas
• Factorial de un número (n!)
5! = 5 * 4 * 3 * 2 * 1 = 120
7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040
n! = 1
n! = n * (n-1)!
si n = 0
si n > 0
Recursividad en las matemáticas
• Fibonacci
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…
fib(n) = 0
fib(n) = 1
fib(n) = fib(n-1) + fib(n-2)
si n = 0
si n = 1
si n > 1
Recursividad en la programación
• Las funciones pueden invocar o ejecutar otras
funciones
• Una función también puede ejecutarse a sí
misma
• Esta característica es la base de la recursividad
Recursividad en la programación
• La idea es descomponer el problema en uno
más pequeño de la misma naturaleza que el
original
• Ir disminuyendo la complejidad
• Llegar a un caso base
Sumatoria
𝑛
𝑖 = 0 + 1 + 2 + ⋯+ 𝑛
𝑖=0
Problema: crear una función que retorne la
sumatoria desde cero para un número entero
positivo n
1. Entender el problema
1. Entradas
2. Salidas
3. Restricciones
2. Pensar un algoritmo
3. Elaborar el algoritmo
4. Pruebas
Ejercicio
Problema: Calcular la cantidad de dígitos que
tiene un número entero, cualquiera que sea este
número
1. Entender el problema
• Entradas: n, el número a analizar
• Salidas: cantidad de dígitos en el número
• Restricciones: el número debe ser entero
positivo
2. Pensar un algoritmo
1. Realizar divisiones enteras entre 10
sucesivamente hasta obtener 0 como
resultado
2. Contar la cantidad de divisiones, ese es el
número de dígitos en el número
3. Formular algoritmo
def digitos(n):
if isinstance(n, int) and n >= 0:
if n==0:
return 0
else:
return 1 + digitos(n // 10)
else:
return "El número debe ser entero no negativo"
4. Pruebas
>>> digitos(1000)
4
>>> digitos(2342394032234238478)
19
>>> digitos(-2)
'El número debe ser entero no negativo'
>>> digitos(0)
0
La función debería retornar como respuesta 1
cuando n=0
¿Cómo podemos solucionar esto?
Función principal y auxiliar
• Definir una función principal para verificar
excepciones y casos especiales
• Definir una función auxiliar que es la recursiva
y es llamada desde la función principal
def cuentadigitos(n):
if isinstance(n, int) and n>=0:
if n==0:
return 1
else:
return 1+cuentadigitosaux(n//10)
def cuentadigitosaux(n):
if n==0:
return 0
else:
return 1+cuentadigitosaux(n//10)
En este problema ni
es necesario usar
una función
auxiliar.
Yo resolví el
roblema del cero
con solo cambiar el
caso base
Solución original
def digitos(n):
if isinstance(n, int) and n >= 0:
if n==0:
return 0
else:
return 1 + digitos(n // 10)
else:
return "El número debe ser entero no negativo"
Solución modificada
def digitos(n):
if isinstance(n, int) and n >= 0:
if n<10:
return 1
else:
return 1 + digitos(n // 10)
else:
return "El número debe ser entero no negativo"
Descomposición y composición de números
• Los problemas que se relacionan con dígitos
se pueden resolver por medio de procesos
repetitivos
– Descomposición: se va reduciendo el número de
alguna forma para realizar un cálculo
– Composición: construir un número nuevo u otro
tipo de dato a partir de las entradas
Ejercicio descomposición
• Determinar si un número entero positivo dado tiene
entre sus dígitos al menos un cero
>>> tieneceros(23433)
False
>>> tieneceros(12320232)
True
>>> tieneceros(-32390)
True
>>> tieneceros(0)
True
1. Entender el problema
• Entradas: el número entero a analizar
• Salidas:
– True si el número contiene ceros
– False si el número no contiene ceros
• Restricciones:
– El número debe ser entero
2. Pensar un algoritmo
1. Si el número original es 0, retornar True
2. Si no, verificar si el residuo de la división
entera por 10 es 0
1. Si el residuo es 0 retornar True
2. Si el residuo no es 0, repetir proceso con el
número sin el último dígito
3. Formular algoritmo
def tieneceros(n):
if isinstance(n, int):
if n==0:
return True
else:
return tienecerosaux(abs(n))
else:
return "El número debe ser entero"
def tienecerosaux(n):
if n==0:
return False
else:
if n%10==0:
return True
else:
return tienecerosaux(n//10)
Nótese que la función tiene dos condiciones de terminación:
• Cuando n es cero
• Cuando el residuo de la división entre 10 es cero
4. Pruebas
>>> tieneceros(28470763)
tienecerosaux(28470763)
tienecerosaux(2847076)
tienecerosaux(284707)
tienecerosaux(28470)
True
>>> tieneceros(2344)
tienecerosaux(2344)
tienecerosaux(234)
tienecerosaux(23)
tienecerosaux(2)
tienecerosaux(0)
False
• Nótese que no se
forma una pila de
llamadas de vuelta
• Esto se denomina
recursividad simple
Ejercicio composición
• Construir una función que forme un número a
partir de otro, considerando sólo los dígitos pares
del número de entrada
>>> pares(3214)
24
>>> pares(23698)
268
>>> pares(3579)
0
Ejercicios de recursividad
1. Función que eleve un número x a una potencia
n, sin utilizar el operador de exponente
2. Calcular la sumatoria de un intervalo
𝑛
𝑖 = 𝑥 + (𝑥 + 1) + (𝑥 + 2) + ⋯ + 𝑛
𝑖=𝑥
3. Función que reciba un número entero o real y
sume todos sus dígitos
Otro ejercicio
• Determinar si un número entero es primo
• Función que reciba un número entero y
retornar un valor booleano que indique si el
número es primo o no
• Entradas: n, número a analizar
• Salidas: True si es primo, False si no
• Restricciones: debe ser entero positivo
Algoritmo
1. Recorrer los números desde 2 hasta n-1
1. Si en algún caso n % div == 0 entonces no es
primo
2. Si se llega hasta n entonces sí es primo
Mejorar el algoritmo
• Todos los números primos son impares,
excepto el dos
• Cualquier número no primo tiene un divisor
menor que su raíz cuadrada
Algoritmo mejorado
1.
2.
3.
4.
Si n es 1, no es primo
Si n es 2, n es primo
Si n es par, n no es primo
Recorrer los números desde 3 hasta raíz de n
1. Si en algún caso n % div == 0, entonces no es
primo
2. Si se llega hasta raíz de n, entonces sí es primo