Download n - TEC Digital
Transcript
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