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  |