recursividad
Post on 13-Jun-2015
3.270 Views
Preview:
DESCRIPTION
TRANSCRIPT
C.E.C.O N° 4 (Algoritmos y lenguajes)
Recursividad
Integrantes:Buslaiman, EmeliCortés, CristianDiaz, María RosaOliva, CristianPáez, María Vanesa
DefiniciónEs un concepto fundamental en matemáticas y en computación.
El proceso de resolver un problema reduciéndolo a uno o mas sub problemas.
Un proceso es recursivo si forma parte de si mismo.
Tipos de Recursividad
Recursividad Directa.
Recursividad Indirecta.
Algoritmo Recursivo
Es un algoritmo que expresa la solución de un problema en términos de una llamada a si
mismo.
Reglas para realizar un Algoritmo
1) Caso Base.2) Progreso.3) Credibilidad.4) Interés compuesto.
Ventajas e Inconvenientes
La principal ventaja es la simplicidad de compresión y su gran potencia.
El principal inconveniente es la ineficiencia tanto en tiempo como en memoria.
ImplementaciónLa recursividad es un método poderoso usado en inteligencia artificial.
Las fórmulas recursivas pueden aplicarse a situaciones Matemáticas, etc.
Existen ciertas estructuras cuya definición es recursiva.
Recursión Vs Iteración
Tanto la iteración como la recursión se basan en estructuras de control
La iteración utiliza una estructura repetitiva.
La recursión una estructura de selección.
Asignación de memoriaLa memoria de un ordenador a la hora de ejecutar un programa queda dividida en dos partes:
La zona donde se almacena el código del programa
La zona donde se guardan los datos: pila (utilizada para llamadas recursivas).
Programa principal llama a una rutina “M”.
Se crea en la pila de un registro de activación o entorno “E”.
Almacena constantes, variables locales y parámetros formales.
Estos registros se van apilando conforme se llaman sucesivamente desde una función a otras.
Cuando finaliza la ejecución, se va liberando el espacio.
Ejemplos de Recursividad
EL FACTORIAL !PARA
RECORDAR
Se llama n factorial o
factorial de n al producto de todos los
naturales desde 1 hasta n.
3!= 1 * 2 * 33!=6
//Solución no
estructurada
int factorial (int n) {
if (n==0)
//Caso base
return 1;
else
//Caso General
return n*factorial(n-
1);
}
4!=4* 3!
3!= 3*2!
2!= 2 *1!
1!= 1 *0!
0!= 1
Ejemplo:
4!=4* 3!
3!= 3*2!
2!= 2 *1!
1!= 1 *1
4!=4* 3!
3!= 3*2!
2!= 2
4!=4* 3!
3!= 6 4!=24
2 3 4
BÚSQUEDA DICOTOMICA
2 3 4 5 6 7 81 9
Valor a
buscar
3
1
3 4
Int desde,hasta,medio,elemento,posicion; // desde y // hasta indican los límites del array que se está mirando.
int array[N]; // Dar valor a elemento.
for(desde=0,hasta=N-1;desde<=hasta;){
if(desde==hasta) // si el array sólo tiene un elemento: {
if(array[desde]==elemento) // si es la solución:
posicion=desde; // darle el valor.
else // si no es el valor:
posicion=-1; // no está en el array.
break; // Salir del bucle. }
medio=(desde+hasta)/2; // Divide el array en dos.
if(array[medio]==elemento) // Si coincide con el central: {
posicion=medio; // ese es la solución
break; // y sale del bucle. }
else if(array[medio]>elemento) // si es menor:
hasta=medio-1; // elige el array izquierda.
else // y si es mayor:
desde=medio+1; // elige el array de la derecha. }
EL PRODUCTO
int producto (int a, int b){if (b==0) return (0);else return (a+ producto (a, b-1));}
Producto(3,2)= 3 + producto(3,1)
Producto (3,2)= 3 + 3Producto(3,2)=6
Producto(3,1)= 3 + producto(3,0) = 3 + 0
Recursividad en ListasLa estructura de listas es recursiva cuando (el “resto” de una lista es a su vez una lista), la mayoría de los programas sobre listas serán recursivos de forma natural.Ejemplo: Supongamos que tenemos la lista de las personas que asistirán a un a reunión y queremos averiguar si una determinada persona irá a ella.
En Prolog seria: miembro(X, L)" que significa X es miembro de la lista L.1. miembro(X, [X|Y]).2. miembro(X, [Y|Z]) :- miembro(X,Z).
Una posible pregunta al programa es: ? miembro(pedro, [maría, pedro, juan, ana]).
? miembro(pedro, [maria, pedro, juan, ana]).
2. {X1®pedro, Y1®maria, Z1® [pedro,juan,ana]}
? miembro(pedro, [pedro, juan, ana]).
1. {X2®pedro, Y2® [juan,ana]}ı EXITO (la contestación es si)
Un árbol (tree) es un tipo de dato abstracto (T.D.A.) que consta de un conjunto finito T de nodos y una relación R (paternidad) entre los nodos tal que: Hay un nodo, especialmente designado, llamado la raíz del árbol T.
A
D E F G
CB
A
D E F G
CB
Definición de Árbol
En Prolog seria:es_padre(B,D):- es_hijo(D,B).
es_nieto(D,A):- es_padre(B,D), es_padre(A,B).
A
D E F G
CB
A
D E F G
CB
Códigos de Árbol
Un grafo (en inglés graph) es un T.D.A. que representa un conjunto finito N de nodos, llamados vértices, relacionados entre sí por un conjunto R de arcos.
AB
DC
E
Grafo con 5 vértices y 6 arcos.
Vértices del Grafo
N ={ A, B, C, D, E }
Arcos del Grafo
R={(A, A), (A, B), (A, D), (A, C), (D, C), (C, E)}
Grafos
A B C D E
0 1 2 3 4
0 1 2 3 4
0 1 0 0 0
1 0 0 0 0
1 1 0 0 0
0 0 1 0 0
0 1 1 0 00
1
2
3
4
AB
DC
E
Vértices
Matriz de Adyacencia
Representación Matricial de Grafos
Sucesión de FibonacciEn matemática, la sucesión de Fibonacci es la siguiente sucesión infinita de números naturales:La sucesión inicia con 0 y 1, y a partir de ahí cada elemento es la suma de los dos anteriores.
0,1,1,2,3,5,8,13………..A cada elemento de esta sucesión se le llama número de Fibonacci. Esta sucesión fue descrita en Europa por Leonardo de Pisa, matemático italiano del siglo XIII también conocido como Fibonacci. Tiene numerosas aplicaciones en ciencias de la computación, matemáticas y teoría de juegos.La sucesión fue descrita por Fibonacci como la solución a un problema de la cría de conejos: "Cierto hombre tenía una pareja de conejos juntos en un lugar cerrado y uno desea saber cuántos son creados a partir de este par en un año cuando es su naturaleza parir otro par en un simple mes, y en el segundo mes los nacidos parir también".
Número de MesExplicación de la genealogía Parejas de conejos totales
Fin del mes 0 0 conejos vivos. 0 parejas en total.
Comienzo del mes 1Nace una pareja de conejos (pareja A). 1 pareja en total.
Fin del mes 1La pareja A tiene un mes de edad. Se cruza la pareja A.
1+0=1 pareja en total.
Fin del mes 2La pareja A da a luz a la pareja B. Se vuelve a cruzar la pareja A.
1+1=2 parejas en total.
Fin del mes 3
La pareja A da a luz a la pareja C. La pareja B cumple 1 mes. Se cruzan las parejas A y B.
2+1=3 parejas en total.
Fin del mes 4
Las parejas A y B dan a luz a D y E. La pareja C cumple 1 mes. Se cruzan las parejas A, B y C.
3+2=5 parejas en total.
Fin del mes 5A, B y C dan a luz a F, G y H. D y E cumplen un mes. Se cruzan A, B, C, D y E.
5+3=8 parejas en total.
Fin del mes 6
A, B, C, D y E dan a luz a I, J, K, L y M. F, G y H cumplen un mes. Se cruzan A, B, C, D, E, F, G y H.
8+5=13 parejas en total.
... ... ...
Fin del mes 12 ... ...
22
Ejemplo: Serie de FibonacciValores: 0, 1, 1, 2, 3, 5, 8... Cada término de la serie suma los 2 anteriores. Fórmula recursivafib(n) = fib (n - 1) + fib (n - 2)
Caso base: Fib (0)=0; Fib (1)=1 Caso recursivo: Fib (i) = Fib (i -1) + Fib(i -2)
public static int fib(int n){if (n <= 1) return n; //condición base
else return fib(n-1)+fib(n-2); //condición recursiva}
La razón de oro (el símbolo es la letra griega "phi" de la izquierda) es un número
especial que vale aproximadamente 1,618
Aparece muchas veces en geometría, arte, arquitectura y
otras áreas.
Razón de oro
Aplicaciones de Fibonacci
La idea
la parte larga dividida entre la corta
es igual que
el total dividido entre la parte larga
Si divides una línea en dos partes de manera que:entonces tienes la razón de oro.
Aplicaciones de Fibonacci
Y hay una sorpresa. Si tomas dos números de Fibonacci consecutivos (uno detrás del otro), su cociente está muy cerca de la razón aúrea "φ" que tiene el valor aproximado 1.618034...De hecho, cuanto más grandes los números de Fibonacci, más cerca está la aproximación. Probemos con algunos:
A B B / A
2 3 1.5
3 5 1.666666666...
5 8 1.6
8 13 1.625
... ... ...
144
233 1.61805
5556...
233
377 1.61802
5751...
... ... ...
FractalesUn fractal es un objeto o cantidad que muestra auto-semejanza en todas las escalas y cuya estructura básica se repite a diferentes escalas.
¿Por qué se llaman fractales?
El término fue propuesto por el matemático Benoît Mandelbrot en 1975 y deriva del Latín “fractus”, que significa quebrado o fracturado.
Aplicaciones
Fenómenos Naturales.Lingüística.Psicología.Aplicaciones electrónicas.
Teoría matemática encargada de realizar sistemas con comportamiento impredecibles y aparentemente aleatorios.
Teoría del Caos
Curva de Koch
Iniciador
Generador i=1
i=2
i=3
Se construye dividiendo un segmento en partes iguales.
Curva de Koch
Avanzar el primer tercio.Girar 60° a la izquierda.Avanzar otro tercio.Girar 60° a la derecha.Girar 60° a la derecha.Avanzar otro tercio.Girar 60° a la izquierda.Avanzar el último tercio.
Triangulo de Sierpinski
A
CB
Se construye dividiendo el triángulo en 3 triángulos más pequeños.
Triangulo de Sierpinski
Sierpinski = 0
Sierpinski = 1
Sierpinski = 2
Curva Hilbert
Se construye dividiendo un cuadrado en partes iguales uniendo sus centros.
Imágenes Fractales
Fin...
top related