Repaso funciones y arreglos Que es un modulo? Cuantos tipos de módulos existes? Como simula C los procedimientos Diferencia entre definir y declarar Los módulos de lenguaje C son inyectivos, biyectivos o sobreyectivos? Variables locales y globales. Definición de: Función (Tarea Obtener xy sin pow) Parámetro Iteración Arreglo Como obtener 500 decimales con lenguaje C
Repaso Ordenar el siguiente arreglo 100,5,30,55,70,300,20 Dibujar el Triángulo de Pascal Hacer una función que obtenga el Máx. Común Divisor
Recursión Es una herramienta matemática-computacional que permite solucionar problemas utilizando su propia definición, es decir es una solución en términos de ella misma. La recursión es equivalente a la iteración, la diferencia radica en la filosofía de trabajo y en el manejo de recursos, cuando se implanta computacionalmente (tiempo y espacio en bytes) Uno de los usos es la de descomponer un problema en problemas más pequeños, como el método de ordenamiento Quicksort
Recursión Todo lo recursivo se puede hacer iterativo y viceversa. Existen problemas cuya solución recursiva es mas práctica que la iterativa ya que la complejidad del problema nos llevaría muchas líneas de código y al contrario, existen procesos que no vale la pena el esfuerzo de convertirlo a recursivo cuando la solución iterativa es lo más recomendable.
Recursión El concepto de Función Recursiva fue introducido por Kleene el año 1936. Son una clase de funciones numérico-teóricas (se llaman así las funciones f(N) : N f(N)n ) que pueden ser evaluadas algorítmicamente. Se pueden evaluar en tiempo, espacio y complejidad Ejemplo de complejidad con un método de ordenación Tarea Investigar O grande y o asintótica
Recursión Las recursiones se pueden clasificar por Su forma de estar construidas para solucionar algo en: Recursión simple ó Múltiple Su forma de solucionar el problema en : Recursión hacia de adelante ó Hacia atrás Backtracking Las combinaciones de estas clasificaciones son 5, debido a que la recursión múltiple puede darse con las dos categorías. Ejemplos: Factorial, Fibonacci, árboles binarios
Recursión Los elementos básicos de la definición de una función recursiva son: Una base (equivalente a axiomas o condiciones límite) que establece que ciertos números son, por definición, valores de la función para argumentos dados. Una regla de construcción recursiva que nos dice como determinar otros valores de la función a partir de valores conocidos. Una afirmación de que la función sólo toma aquellos valores que resultan por aplicación, un número finito de veces, de la regla de construcción recursiva sobre los valores de la función básica.
Recursión FRP Debido a que las funciones recursivas originales, fueron hechas para representar problemas básicos de las matemáticas se crearon funciones que representaban dichos procesos a éstas se les llamo “Funciones Primitivas Recursivas”. Toda función que se base en FPR se considera de la misma clase.
Recursión FRP Tomaremos como conjunto base, tres funciones que por definición decimos que son recursivas primitivas (y de ellas se pueden derivar otras): 1) Función Cero “z” : z(x) = 0 2) Función Sucesor “s” : s(0) = 1, s(1) = 2 … 3) Funciones Identidad id11(x) = x id21 (x,y) = x, id22 (x,y) = y, id31 (x,y,z) = x, id32 (x,y,z) = y, id33 (x,y,z) = z
Recursión FRP En algunos casos en las FPR se utilizan subindices para indicar cuales argumentos o parámetros se utilizaran, ej: S3(x,y-1,fh(x,y-1)) = fh(x,y-1)+1 Suma2,4(x,y,z,fg(x+1,y)) = y+fg(x+1,y)
Recursión Ejemplos de funciones recursivas primitivas Problema encontrar la forma recursiva de: suma(n1, n2) = n1 + n2 Idea Básica suma(n1, 0) = n1 suma(n1, n2) = suma(n1, n2-1) + 1 Expresada en Notación de FRP suma(n1, 0) = ?11(n1) = n1 suma(n1, n2) = sucesor3(n1, n2-1, suma(n1, n2-1))
Recursión Problema encontrar la forma recursiva de: producto(n1, n2) = n1*n2 producto(n1, 0) = 0 producto(n1, n2) = n1+prod(n1,(n2 – 1)) Expresado en Términos de FRP producto(n1, 0) = Z(n1) = 0 producto(n1, n2) = suma1,3(n1, n2 – 1, producto(n1, n2 –1))
| Página siguiente |