Diseño de algoritmos

Unidad 2  Diseño de Algoritmos 

•Bibliografía:“Algoritmos y Estructuras de datos” de Aguilar y Martinez.Unidad 5y6  •Autor: Ing Rolando Simon Titiosky.

Naturaleza de la Recursividad 
• Los programas Estructurados se  componen de funciones que se llaman  unas a otras de manera organizada.  •  Los programas RECURSIVOS se  componen de Funciones que se llaman a  si mismas. 
–Necesita la definición del CASO BASE o  condición de salida, que evitará que la  función se llame a si misma infinitamente.

Naturaleza de la Recursividad 
•  Hay muchos fenómenos recursivos: 
–Matemáticas: Fibonacci, Factorial, etc.  – Realidad: Árboles, plantas,  etc 

•  Ejemplo de Organización Recursiva:  Directa  Indirecta 
void funcion1(…)  {  … funcion1();  }  Void funcion2(…) {       funcion3()    }  Void funcion3(…)  {       funcion2()    } 

n •  Eficiencia F(n)= k   Se invoca “K” veces a 

si mismo con un lote inicial “n”

Factorial 
n!=n*(n–1)*(n–2)*…*1 0!=1;  1!=1;  2!=2*1; 
•  Iterativamente, n! se resuelve: 

3!=3*2*1
–  Condición de Salida: 
•  si n=0 => n!=1 

•  Recursiva: n!=n*(n–1)! 
–  Si n>0 => n!=n*(n–1)! long factorial(int n)  {  long f=1;  int i=n; 
While (i>0)  {  f*=i;  i= i–1;  }  return f; 

long factorial(int n)  {  if (n==0) return 1;  else  return n*factorial(n–1);  } 

}  F(n)@n  C @sizeof(long)+sizeof(int)  esp
n  F(n)@(n–1)  C  @sizeof(int)*(n–1)  esp

RESOLVER Ejemplos 
1.  Deducir la definición recursiva del producto de  números naturales usando solamente la  operación SUMA.  2. Definir la serie de Fibbonacci de manera  recursiva e iterativa. 
•  •  Serie Fibbonacci: 0,1,1,2,3,5,8….  F(n)=F(n–1)+F(n–2) 

(*)Indicar Eficiencia F(N) y Complejidad  Espacial

Respuesta 1 Condición de Salida: Cuando b=1 el producto de  a*b=a;  int prod(int a, int b)  {  if (b==1) return a;  else return a+prod(a, b–1);  }  C  = 2*sizeof(int)*b; {se invoca b veces y se deben  esp ...