1 Recursividad Estructuras de datos
2 Definición Un algoritmo es recursivo cuando se define en términos de una versión más simple de si mismo. Características 1. Debe existir una salida en la que no se haga la llamada recursiva 2. La llamada recursiva debe ser versión más simple que la llamada que la invocó.
3 Multiplicación enteraEl producto de dos números enteros a y b se puede definir recursivamente como sigue: a * b = a si b == 1 a * b = a * (b – 1) + a si b>1 Ejemplo: 3*4 = 3*3+3 = 3*2+3+3=3* = = 12
4 Definición recursiva del Factorialn! = 1, si n = 0 n! = n (n – 1)!, si n > 0 5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1*0! = 5*4*3*2*1*1 = 5*4*3*2*1 = 5*4*3*2 = 5*4*6 = 5*24 = 120
5 Algoritmo Algoritmo para evaluar el factorial de un número.FUNCIÓN FACTORIAL(N:ENTERO) REGRESA ENTERO 1. SI N = 0 ENTONCES a. REGRESAR 1 2. SINO a. X = N – 1 b. Y = N * FACTORIAL(X) c. REGRESAR Y
6 SIMULACIÓN DEL FACTORIAL DE 4
7 Factorial en C float fact(int n){ if(n == 0) return 1; elsereturn n*fact(n-1); }
8 Números de Fibinacci La secuencia de Fibonacci se define de la siguiente manera. Los dos primeros elementos de la secuencia son 0 y 1. Cualquier otro número de Fibonacci se obtiene sumando los dos anteriores. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
9 DEFINICIÓN RECURSIVA DE LOS NÚMEROS DE FIBONACCIfib(n) = n , si n = 0 o n = 1 fib(n) = fib(n – 1) +fib(n – 2) , si n > 1 Algoritmo para calcular el n-ésimo número de Fibonacci. FUNCION FIB(N:ENTERO) REGRESA ENTERO 1. SI N = 0 OR N = 1 ENTONCES a. REGRESA N 2. SINO a. X ¬ FIB(N-1) b. Y ¬ FIB(N-2) c. REGRESA X + Y
10 SIMULACIÓN DE FIB DE 5
11 Número de Fibonacci en Cint fib(int n){ if(n == 0 || n == 1) return n; else return fib(n-1)+fib(n-2); }
12 Máximo Común Divisor Un algoritmo recursivo es el siguiente.El MCD de dos números x e y es y si y
13 Actividad Escriba el algoritmo para mcd en forma simbólica y defina una función que calcule el mcd en C.
14 VERSIONES NO RECURSIVASAlgoritmo no recursivo para evaluar el factorial FUNCION FACTORIAL(N: ENTERO) REGRESA ENTERO 1. SI N = 0 ENTONCES a. REGRESAR 1 2. SINO a. F ¬ 1 b. PARA I ¬ 1 HASTA N HACER 1. F ¬ F * I c. REGRESAR F Algoritmo no recursivo para calcular el n-ésimo número de Fibonacci. FUNCION FIB(N:ENTERO) REGRESA ENTERO 1. SI N = 0 OR N = 1 ENTONCES a. REGRESA N 2. SINO a. X ¬ 0 b. Y ¬ 1 c. PARA I ¬ 2 HASTA N HACER 1. F ¬ X + Y 2. X ¬ Y 3. Y ¬ F d. REGRESA F
15 Tarea 1. La función de Ackerman A está definida para todos los enteros positivos m y n como sigue: A(0, n) = n + 1 A(m, 0) = A(m – 1, 1) A(m, n)= A(m – 1, A(m, n – 1)) Escriba una función en C para calcular el valor de la función de Ackerman. Pruebe evaluando algunos valores de A(1, n), A(2, n) y A(3, n). Defina expresiones simples para estas funciones. La función tiene un crecimiento extremadamente grande para valores de m mayores que 3, por ejemplo A(4,2) = – 3, evalúe A(4,1). 2. Desarrolle la expansión de la función de Ackerman del problema anterior para los siguientes parámetros: A(1,2), A(1,3), A(2,1), A(2,2).
16 DEFINICIÓN RECURSIVA DE EXPRESIONES1. Una expresión es un término seguido por un signo más seguido por un término, o un solo término. 2. Un término es un factor seguido por un asterisco seguido por un factor, o un factor solo. 3. Un factor es una letra o una expresión encerrada entre paréntesis.
17 FUNCIONES EXPR Si no es un término, terminaFUNCION EXPR REGRESA BOOLEANO 1. SI NOT TERM ENTONCES a. REGRESA FALSO 2. SINO a. C ¬ SIGUIENTE SÍMBOLO b. SI C<>'+' ENTONCES 1. P ¬ P - 1 2. REGRESA VERDADERO c. SINO 1. REGRESA TERM Encontró un término, ve que hay más adelante Se encontró un solo término, p señala hasta donde es correcta la expresión. Encontró dos términos separados por +, verifica el segundo término. Encontró dos términos separados por +, verifica el segundo término.
18 FUNCION TERM REGRESA BOOLEANO1. SI NOT FACT ENTONCES a. REGRESA FALSO 2. SINO a. C ¬ SIGUIENTE SÍMBOLO b. SI C<>'*' ENTONCES 1. P ¬ P - 1 2. REGRESA VERDADERO c. SINO 1. REGRESA FACT Si no es un factor, termina Encontró un factor, ve que hay más adelante Se encontró un solo factor, p señala hasta donde es correcto el término. Encontró dos factores separados por *, verifica el segundo factor.
19 FUNCIÓN FACT Es el factor una letra?FUNCION FACT REGRESA BOOLEANO 1. C ¬ SIGUIENTE SÍMBOLO 2. SI C<>'(' ENTONCES a. IF C ES LETRA ENTONCES 1. REGRESA VERDADERO b. SINO 1. REGRESA FALSO 3. SINO a. SI NOT EXPR ENTONCES a. SI C=')' ENTONCES Es el factor una letra? Es el factor una expresión entre paréntesis? Si es una expresión entre paréntesis, términa con “)”?
20 DEFINICIÓN RECURSIVA DEL DETERMINANTESi a es una matriz de 1 x 1, entonces det(a) = x. Si a es de orden mayor que 1, calcule el determinante de a como sigue: Escoja cualquier fila o columna. para cada elemento a[i, j] en esa fila o columna, forme el producto (-1)(i+ j)*a[i, j]*det(menor(a[i, j])) Donde det(menor(a[i, j])) es el determinante del menor de a[i, j]. det(a) = suma de todos los productos para la columna o fila seleccionada.
21 ALGORITMO RECURSIVO PARA CALCULAR EL DETERMINANTEAlgoritmo recursivo para calcular el determinante de una matriz de orden n. FUNCION DET(N:ENTERO; A:MATRIZ) REGRESA REAL 1. SI N=1 ENTONCES a. REGRESA A[1,1] 2. SINO a. S ¬ 0 b. PARA I = 1 HASTA N HACER 1. MENOR(A,N,I,J,B) 2. S ¬ S + SIGNO(I,J) * A[I,J]*DET(N-1,B) c. REGRESA S
22 Calculadora recursivaEsta calculadora procesa expresiones algebraicas normales como: 3+4+5, 3*(6-2)*sin(3*atan(0.25)^7) Para esto definimos las siguientes funciones Expr – expresión algebraica Smplexpr – procesa una expresión simple: 3, 4*5, 8/6, 5/sin(2) Term – procesa términos: 3, 4^5. Sfact – factor simple: 4, -6 Fct – factor: (7+4.5), (sin(2)*8)
23 función expr (expresión) regresa real1. e = smplexpr 2. mientras el simbolo siguiente sea + o - 3. operador = simbolo siguiente 4. obtener siguiente símbolo 5. si operador es + e = e+smplexpr 7. si operador es - e = e-smplexpr 9. regresa e función smplexpr (expresión simple) regresa real 1. e = term 2. mientras el simbolo siguiente sea * o / 3. operador = simbolo siguiente 4. obtener siguiente símbolo 5. si operador es * e = e*smplexpr 7. si operador es / e = e/smplexpr 9. regresa e
24 función term (término) regresa real1. t = sfact //término es un factor simple 2. mientras siguiente símbolo=^ 3. obtener siguiente símbolo 4. t = t^sfact 5. regresar t función sfact (factor simple) 1. si simb='-' 2. obtener siguiente símbolo 3. regresar -fct //factor 4. sino 5. regresar fct función fct (factor) 1. if simbolo es un número 2. leer número y guardar en f 3. sino 4. si simbolo='(' procesar nueva expresión y guardar en f 6. sino procesar función estandar y guardar en f 8. regresar f
25 procesar nueva expresión1. obtener siguiente símbolo 2. f = expr 3. si simbolo=')' 4. obtener siguiente símbolo 5. sino 6. error procesar función estandar codigo para cada función 1. si se lee 'sin' 2. avansar 3 símbolos 3. f = sin(fct) Asi para cada función
26 Lectura de un real en C void processAsNumber(){ char t[80]; t[0] = ch;int i=0; nextp(); while(ch>='0'&&ch<='9'){ t[++i] = ch; } if(ch=='.') do{ }while(ch>='0'&&ch<='9');
27 Cont. if(ch=='E'){ t[++i] = ch; nextp(); do{}while(ch>='0'&&ch<='9'); } t[++i] = '\0'; f = atof(t);
28 ALGORITMO PARA CONVERTIR UNA CADENA EN PREFIJO A POSFIJO1. Si la hilera de prefijo es una sola variable, esta es equivalente a su expresión de posfijo. 2. Considere op el primer operador de la hilera de prefijo. 3. Encuentre el primer operando opnd1 de la hilera. Conviértalo a posfijo y llámelo post1. 4. Encuentre el segundo operando opnd2 de la hilera. Conviértalo a posfijo y llámelo post2. 5. Concatene post1, post2, y op.
29 ALGORITMO DE CONVERSIÓNSUBRUTINA CONVERT(PREFIX:CADENA; POSFIX:CADENA) 1 SI LONGIUD(PREFIX)=1 ENTONCES a. SI PREFIX[1] EN ['a'..'z','0'..'9','A'..'Z'] ENTONCES 1. POSFIX ¬ PREFIX b.SINO 1. ERROR('hilera de prefijo invalida') 2. SINO a. OP ¬ PREFIX[1] b. M ¬ FIND(PREFIX,2) c. N ¬ FIND(PREFIX,M+2) d. SI NOT(OP IN ['-', '+', '*', '/', '^']) OR (M=0) OR (N=0) OR (M+N+1<>LONGITUD(PREFIX)) ENTONCES e. SINO 1. OP1 ¬ COPY(PREFIX,2,M) 2. OP2 ¬ COPY(PREFIX,M+2,N) 3. CONVERT(OP1,P1) 4. CONVERT(OP2,P2) 5. POSFIX ¬ P1+P2+OP
30 ALGORITMO PARA ENCONTRAR CADENA DE PREFIJOAlgoritmo para encontrar la cadena de prefijo más larga a partir de la posición P. FUNCION FIND(S:CADENA, P:ENTERO) REGRESA ENTERO 1. SI P>LONGITUD(S) ENTONCES a. REGRESA 0 2. SINO a. FIRST ¬ S[P] b. SI FIRST EN ['a'..'z','0'..'9','A'..'Z'] ENTONCES 1. REGRESA 1 c. SINO 1. M ¬ FIND(S,P+1) 2. N ¬ FIND(S,P+M+1) 3. SI (M=0)OR(N=0) ENTONCES 4. SINO a. REGRESA M+N+1
31 PROBLEMA DEL RECORRIDO DEL CABALLOSe trata de recorrer un tablero de n x n utilizando un caballo de ajedrez visitando todas las casillas una sola vez.
32
33 ALGORITMO DE VUELTA ATRÁS backtrakingProcedimiento Ensayar nuevo movimiento 1. Iniciar el conjunto de movimientos posibles 2. REPETIR a. seleccionar el nuevo candidato de la lista de futuros movimientos b. SI aceptable ENTONCES 1. Anotar movimiento 2. SI tablero no lleno ENTONCES a. Ensayar nuevo movimiento b. SI no acertado ENTONCES 1. borrar la anotación anterior 3. HASTA (movimiento acertado) or (no hay mas posibilidades)
34 Representación Arreglo bidimensional h[][] de enteros de n x n para representar el tablero, h[x][y] = 0, la casilla no ha sido visitada, h[x][y] = m, la casilla fue visitada en el movimiento m. A partir de la posición x,y se selecciona u y v como las coordenadas de un posible movimiento, según las reglas del ajedrez. Anotar movimiento: h[u][v] = j Borrar movimiento: h[u][v] = 0 Movimiento aceptable: h[u][v] == 0 Tablero no lleno: j < n^2
35 Pseudo código void ensayar(i, x, y, *q) bool q1=false;Iniciar el conjunto de movimientos posibles do{ seleccionar el nuevo candidato de la lista de futuros movimientos if(coord u y v aceptables y h[u][v] == 0) h[u][v] = i; if(i
36 Estrategia de recorridoDado x ,y la primera coordenada puede ser x+2, y+1, luego x+1, y+2, x–1, y+2, etc. x–2 x–1 x x+1 x+2 6 7 y – 2 5 8 y – 1 y 4 1 y +1 3 2 y +2
37 Tarea Agregue las siguientes funciones a la calculadora recursiva.constantes p, e. variables a, b, c y d Escriba un programa para convertir de prefijo a posfijo utilizando el algoritmo recursivo estudiado. Escriba un programa para resolver el Sudoku utilizando el algoritmo de vuelta atrás.
38 Las torres de Hanoi Las torres de Hanoi constan de 3 postes A, B, C. Inicialmente se colocan un cierto número de discos en el poste A. El juego consiste en trasladar todos los discos al poste C utilizando el poste B como auxiliar. Las reglas son: Solo mover un disco a la vez. Nunca poner un disco mayor sobre otro menor. Posición inicial Posición final
39 Algoritmo Torres Algoritmo para mover n discos del poste A al poste C usando el poste B como auxiliar. 1. Si n == 1 mover el disco de A a C y parar 2. Mover n-1 discos de A a B usando C como auxiliar 3. Mover el disco restante de A a C 4. Mover n-1 discos de B a C usando A como auxiliar
40 Algoritmo en C A C B void moverDisco(int n, int desde, int hasta, int auxiliar){ if(n == 1) printf("Mover disco 1 de %d a %d\n“, desde, hasta); else{ moverDisco(n-1, desde, auxiliar, hasta); printf("Mover disco %d de %d a %d\n“, n, desde, hasta); moverDisco(n-1, auxiliar, hasta, desde); } } A B C B C A
41 Posible proyecto Modificar la calculadora para hacer operaciones con números complejos. Ayuda: utilice la biblioteca complex de c++, en ella se define una plantilla para definir complejos, ponga double como tipo base. Se definen todos los operadores y algunas funciones matemáticas.