recursividad

Introduccion Algoritmos de tipo dividir para vencer Algoritmos de rastreo Inverso

Recursividad

Programacion Avanzada

15 de abril de 2013


Contenido

IntroduccionObjetivosDefinicion y PropiedadesCaso de analisis: factorial

Algoritmos de tipo dividir para vencerCaso de analisis: Torres de Hanoi

Algoritmos de rastreo InversoAlgoritmo del Pintor


Objetivos





Objetivos

Objetivos de la clase

Mostrar la utilidad de la recursividad a traves del analisisde casos.

Mostrar diferentes estrategias para resolver problemasutilizando recursividad.


Definicion y Propiedades






Definicion y propiedades

Definicion

Una funcion que se llama a si misma se dice que es recursiva.

Simbolicamente se representa como una composicion Pcompuesta de un conjunto de sentencias S (que puedencontener a P) y P.

P = [P, S] (1)

Esta sujetas a una condicion de salida B. En smbolos:

funcionP = Si B entonces P[S , P], sino finalizar (2)



Definicion y propiedades

DefinicionUna funcion que se llama a si misma se dice que es recursiva.

Simbolicamente se representa como una composicion Pcompuesta de un conjunto de sentencias S (que puedencontener a P) y P.

P = [P, S] (1)

Esta sujetas a una condicion de salida B. En smbolos:

funcionP = Si B entonces P[S , P], sino finalizar (2)



Propiedades

Se reserva espacio para almacenar el nuevo conjuntocompleto de las nuevas variables.

Hay variables con valores presentes y pendientes. La profundidad de la recursion debe ser finita, y ademas

pequena.



Propiedades


Hay variables con valores presentes y pendientes.

La profundidad de la recursion debe ser finita, y ademaspequena.



Propiedades


Hay variables con valores presentes y pendientes. La profundidad de la recursion debe ser finita, y ademas

pequena.



Recursividad directa

Recursividad directa: la funcion se llama directamente a simisma.



Recursividad IndirectaRecursividad indirecta: la funcion llama a otra funcion y esta asu vez llama a la primera.


Caso de analisis: factorial






Factorial

Definicion

El factorial para todo entero positivo n, es el producto de todoslos numeros enteros positivos desde 1 hasta n:

n! = 1 2 3 4 ... (n 1) nel factorial de n = 1 es 1! = 1



Factorial

DefinicionEl factorial para todo entero positivo n, es el producto de todoslos numeros enteros positivos desde 1 hasta n:

n! = 1 2 3 4 ... (n 1) nel factorial de n = 1 es 1! = 1



Uso de la recursividad Una solucion recursiva puede no ser la mejor manera de

resolver el problema.

Esquemas donde hay solo una llamada a la funcionrecursiva al final o al inicio de la composicion:funcionRecursiva(params){if (B) {S} // S conjunto de sentenciaselse {funcionRecursiva(params)}

}

se puede representar por:funcionRecursiva(params){incializar();while(B) {S // S conjunto de sentencias

}}




resolver el problema. Esquemas donde hay solo una llamada a la funcion

recursiva al final o al inicio de la composicion:

funcionRecursiva(params){if (B) {S} // S conjunto de sentenciaselse {funcionRecursiva(params)}

}


}}





recursiva al final o al inicio de la composicion:funcionRecursiva(params){

if (B) {S} // S conjunto de sentenciaselse {funcionRecursiva(params)}

}


}}







}

se puede representar por:

funcionRecursiva(params){incializar();while(B) {S // S conjunto de sentencias

}}







}

se puede representar por:funcionRecursiva(params){

incializar();while(B) {S // S conjunto de sentencias

}}


Caso de analisis: Torres de Hanoi






Torres de Hanoi

Dadas tres torres A, B y C, con una cantidad de N discosapilados en el torre A.

Los discos son de diferentes tamanos e inicialmente seencuentran apilados desde el mas grande hasta el maspequeno.

Se pide lograr que los N discos de la torre A pasen a la Csegun las reglas:

Solo se puede mover el disco superior de cualquier torre. Un disco mas grande no puede estar encima de uno mas

pequeno.



Torres de Hanoi




Solo se puede mover el disco superior de cualquier torre.

Un disco mas grande no puede estar encima de uno maspequeno.



Torres de Hanoi




Solo se puede mover el disco superior de cualquier torre. Un disco mas grande no puede estar encima de uno mas

pequeno.



Codigo torres de Hanoi

void Hanoi(unsigned int nd,char origen,char destino, charauxiliar,ostream& salida){

if (nd>0){Hanoi(nd-1,origen,auxiliar,destino,salida);salida



Complejidad

El analisis de la complejidad tambien se puede pensar enforma recursiva. Por ejemplo para 4 discos, si H(n) es lacantidad de movimientos:

H(4) = H(3) + 1 + H(3)H(3) = H(2) + 1 + H(2)H(2) = H(1) + 1 + H(1)

H(1) = 1

= 15= 7= 3= 1


Generalidades

Encontrar solucion a problemas sin seguir una reglaespecfica de calculo, sino por ensayo y error (Busquedaexhaustiva).

Descomposicion del tanteo: Tareas parciales que se puedan expresar recursivamente. Se explora un numero finito de subtareas: Es util donde hay muchas posibilidades iniciales, pero

quedan pocas tras aplicar reglas posteriores


Algoritmo del Pintor






Algoritmo del pintor Iconst int tamanio=300;const int vecinosC[]={-1,0,1,-1,1,-1,0,1};const int vecinosF[]={-1,-1,-1,0,0,1,1,1};

class figura {protected:vector matriz;int area;void cuenta(int f, int c, int color, vector &mb);public:figura();void CalcularArea(int f0, int c0);int superficie(){return area;}

};void figura::CalcularArea(int f0,int c0){ vector vb(tamanio,false);

vector mb(tamanio,vb);area=0;cuenta(f0,c0,matriz[f0][c0],mb);



Algoritmo del pintor II

}

void figura::cuenta(int f, int c, int color, vector &mb)

{ if ((f=0)&&(matriz[f][c]==color)&& !mb[f][c])

{ area++;int vecino=0;mb[f][c]=true;for (vecino=0;vecino

Documents

recursividad