´ a la Computacion ´ Introduccion Funciones recursivas Esteban E. Mocskos ([email protected]) Facultad de Ciencias Exactas y Naturales, UBA CONICET 17/04/2015 E. Mocskos (UBA–CONICET) Clase 8: Funciones Recursivas 17/04/2015 1 / 10 Definiciones recursivas ´ definidas en funcion ´ de Las definiciones recursivas son aquellas que estan s´ı misma. ´ de Una de las primeras definiciones que vimos fue la de la definicion Suc : N → N, S(n) = n + 1 ´ Suc se usa para definir a los numeros La funcion naturales... Entonces, cualquier ´ ´ (finita) de aplicaciones de la funcion ´ natural se podr´ıa escribir como una sucesion Suc. Pero para que esto funcione, ¿Que´ nos esta´ faltando?¡El caso base! El 5 se podr´ıa escribir como: Suc(Suc(Suc(Suc(1)))) ´ de funcion ´ recursiva tiene dos partes: Una definicion 1 2 ´ de un caso base. Por ejemplo: f act(0) = 1 Caso base: puede haber mas ´ en ambas partes de la definicion, ´ pero la Caso Recursivo: Se menciona la funcion ´ a los llamada recursiva se acerca (en algun ´ sentido) al caso base con relacion ´ ´ parametros del lado izquierdo de la ecuacion. Por ejemplo: f act(n) = n · f act(n − 1) E. Mocskos (UBA–CONICET) Clase 8: Funciones Recursivas 17/04/2015 2 / 10 ´ Recordemos el principio de induccion ´ sobre los numeros Sea p(n), n ∈ N, una proposicion naturales. ´ Si p satisface: 1 (Caso base) p(1) es Verdadera, 2 (Paso inductivo) (∀h ∈ N )p(h) Verdadera → p(h + 1) Verdadera, entonces p(n) es Verdadero, ∀n ∈ N. ´ Atencion ¿Esto no les parece, de algun ´ modo, similar a la manera en que se definen las funciones recursivas? E. Mocskos (UBA–CONICET) Clase 8: Funciones Recursivas 17/04/2015 3 / 10 Definiendo funciones recusivas en la computadora Como estamos viendo, las definiciones recursivas tiene una fuerte historia y ´ en la matematica. ´ utilizacion ´ de recursion ´ y de funciones para crear un El paradigma funcional utiliza la nocion forma de computar. No daremos lenguaje funcional en este curso, pero sepan que existen otros mundos. ´ puede reemplazar a las En los lenguajes imperativos, el mecanismo de recursion estructuras de control iterativas (ciclos: while, for). Por ejemplo: def f a c t ( n ) : i f n == 1 : return 1 else : r e t u r n n * f a c t ( n−1) E. Mocskos (UBA–CONICET) Clase 8: Funciones Recursivas 17/04/2015 4 / 10 Suma de numeros ´ Supongamos que tenemos que calcular la suma de una lista de numeros enteros. ´ ´ ´ ¿Como ser´ıa la especificacion? problema listSum([list: Z]) = result: Z{ requiere True P asegura result = |list|−1 list[i] i=0 } ´ utilizando for: Hagamos un programa en Python que implemente esta especificacion def l i s t s u m ( l i s t ) : theSum = 0 for i in l i s t : theSum = theSum + i r e t u r n theSum print ( listsum ([1 ,3 ,5 ,7 ,9])) E. Mocskos (UBA–CONICET) Clase 8: Funciones Recursivas 17/04/2015 5 / 10 Suma de numeros ´ Supongamos que tenemos que calcular la suma de una lista de numeros enteros. ´ ´ ´ ¿Como ser´ıa la especificacion? problema listSum([list: Z]) = result: Z { requiere True P asegura result = |list|−1 list[i] i=0 } ´ utilizando Hagamos un programa en Python que implemente esta especificacion while: def l i s t s u m ( l i s t ) : theSum = 0 i =0 while i <l e n ( l i s t ) : theSum = theSum + l i s t [ i ] i +=1 r e t u r n theSum print ( listsum ([1 ,3 ,5 ,7 ,9])) E. Mocskos (UBA–CONICET) Clase 8: Funciones Recursivas 17/04/2015 6 / 10 Suma de numeros ´ Hagamos un programa en Python que implemente la suma de una lista de enteros ´ haciendo recursion. ´ para hacer la funcion ´ recursiva, Primero, tenemos que adaptar la especificacion ¿Que´ tenemos que cambiar? problema listSum([list: Z]) = result: Z { requiere True P asegura result = |list|−1 list[i] i=0 } ´ recursiva (al menos en estos ejemplos relativamente La idea de plantear una funcion sencillos) es no usar ni while ni for, pero s´ı podemos hacer list[0] para acceder al primer elemento de la lista y list[1:] para tener el resto. Veamos el ejemplo de [1,3,5,7,9]: result result result result result = = = = = 1 1 1 1 1 + + + + + listSum([3,5,7,9]) 3 + listSum([5,7,9]) 3 + 5 + listSum([7,9]) 3 + 5 + 7 + listSum([9]) 3 + 5 + 7 + 9 E. Mocskos (UBA–CONICET) Clase 8: Funciones Recursivas 17/04/2015 7 / 10 Suma de numeros, el programa ´ ´ Veamos como queda esto en Python: def listsum ( list ): if len ( list ) == 0: return 0 else : return list [0] + listsum ( list [1:]) print ( listsum ([1 ,3 ,5 ,7 ,9])) Veamos que´ pasa cuando hacemos la ´ ejecucion: ´ de llegar al Veamos que´ pasa despues caso base: Figuras reproducidas de http://interactivepython.org/courselib/static/pythonds/Recursion/recursionsimple.html E. Mocskos (UBA–CONICET) Clase 8: Funciones Recursivas 17/04/2015 8 / 10 ´ de Fibonacci Sucesion ´ de Fibonacci se nombra a partir del matematico ´ La sucesion Leonardo de Pisa, conocido como Fibonacci. En su libro “Liber Abaci” publicado en 1202 introduce esta secuencia en base a un ejercicio planteado con conejos. ´ idealizada de conejos que Los numeros de Fibonacci representan una poblacion ´ siguen las siguientes condiciones: ´ nacidos, un nene y una nena, constituyen la poblacion ´ inicial. Dos conejos recien Estos conejos son capaces de aparearse a la edad de un mes. Los conejos son inmortales. Cada par de conejos que se aparean producen un nuevo par (otro nena y nena) cada mes a partir del segundo mes. ´ despues ´ de n meses. Los numeros de Fibonacci Fn representan la poblacion ´ ´ comienza por 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . . La sucesion ´ formal (y que se usa actualmente incluyendo F0 ) ser´ıa: La definicion F0 F1 Fn E. Mocskos (UBA–CONICET) = = = 0 1 Fn−1 + Fn−2 Clase 8: Funciones Recursivas n≥2 17/04/2015 9 / 10 ´ de Fibonacci Implementando la sucesion ´ Veamos como quedar´ıa escrito en Python: def f i b ( n ) : i f n == 0 : return 0 e l i f n == 1 : return 1 else : r e t u r n f i b ( n−1) + f i b ( n−2) ´ ´ de esta funcion ´ si hacemos fib(5)? ¿Como ser´ıa la ejecucion ´ ¿Cuantas veces se calcula fib(3)? ¡2! ¿Y fib(2)? ¡3! Reproducida de http://www.python- course.eu/recursive_functions.php ´ Y... ¿si ahora quisieramos calcular fib(6)? E. Mocskos (UBA–CONICET) Clase 8: Funciones Recursivas 17/04/2015 10 / 10
© Copyright 2024 ExpyDoc
