\chapter{Programación estructurada con funciones}

\section{Introducción.}

En C existen un conjunto de funciones matemáticas de biblioteca las que permiten al programador ciertos cálculos comunes. Algunos ejemplos de estas funciones son:

\begin{flushleft}
\begin{tabular}{|l|l|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  función & descripción  \\
  \hline
  double acos(double x) & arco coseno de x. \\
  double asin(double x) & arco seno de x. \\
  double atan(double x) & arco tangente en radianes. \\
  double atan2(double y, double x) & arco tangente de las dos variables x e y. \\
  double ceil(double x) & Redondea x hacia arriba al entero más cercano. \\
  double cos(double x) & coseno de x. \\
  double cosh(double x) & coseno hiperbólico de x. \\
  double exp(double x)  & Devuelve el valor de e  \\
  double fabs(double x) & valor absoluto \\
  double floor(double x) & Redondea x hacia abajo al entero más cercano. \\
  double fmod(double x, double y) & Calcula el resto de la divisiÛn de x entre
  y.\\
  double log(double x) & Devuelve el logaritmo neperiano de x. \\
  double log10(double x) & Devuelve el logaritmo decimal de x. \\
  double pow(double x, double y) & Devuelve el valor de x elevado a y.\\
  double sin(double x) & Devuelve el seno de x. \\
  double sinh(double x) & Regresa el seno hiperbólico de x.\\
  double sqrt(double x) & Devuelve la raÌz cuadrada no negativa de x. \\
  double tan(double x) & Devuelve la tangente de x. \\
  double tanh(double x) & Devuelve la tangente hiperbólica de x.
  \\
  \hline
\end{tabular}
\end{flushleft}

Las funciones permiten al programador modularizar un programa. Todas las variables declaradas en las definiciones de funciones son variable locales, son conocidas solo en la función en la cual están definidas. La mayor parte de las funciones tienen una lista de parámetros. Los parámetros proporcionan la forma de comunicar información entre funciones. Los parámetros de una función también son variable locales.

\section{Definición de una función}

El formato para definir una función es

\begin{verbatim}
tipo_de_valor_de_regreso nombre_de_la_función (lista de parametros)
{

declaraciones;

enunciados;

}
\end{verbatim}

El nombre de la función comienza con una letra y continua con letra numero o el carácter ``\_'', nunca debe dejarse espacios en blanco. El tipo de valor de regreso es el tipo de los datos del resultado que una función devolverá por valor. Un tipo de valor de regreso no especificado será siempre supuesto por el compilador cono int (en el caso de C).

La manera de regresar un valor es utilizando la sentencia

\begin{verbatim}

return expresion;

\end{verbatim}

\subsection{Ejemplo de la función cuadrado}

A continuación se presenta la implementación de una simple función que calcula el cuadrado de un numero flotante.

\begin{verbatim}
/* 
 * File:   cuadrado.c
 * Author: felix
 *
 * Created on 28 de marzo de 2012, 13:54
 */

#include <stdio.h>

float cuadrado(float y) {
  return y*y;
}

int main() {
  int x;

  for(x=1; x<=10; x++)
    printf("%f \n", cuadrado(x));

  return 0;
}

\end{verbatim}

\section{Estructura de una función y alcance de una variable} 
El objetivo de dividir un programa en funciones es controlar las variables internas usadas. Así por ejemplo el siguiente código presenta la variable x y los valores que esta tendrá son totalmente diferentes.

\begin{verbatim}
uno() {
   int x = 2;
   ----
   ----
 }  

dos() {
   int x = 4;
   -----
   -----
 }  

\end{verbatim}

En el caso de la función uno(), la variable x se iniciativa con 2 y esta solamente existirá en dicha función. Por otro lado en la función dos() la variable x tendrá un 4 y no interfieren una variable con la otra. Podemos decir que la primer x pertenece a la función uno y la segunda a la función dos.

\subsection{Prototipos de función}
Un prototipo de función le indica al compilador el tipo de dato regresado por la función, el número de parámetros que la función espera recibir, los tipos de dichos parámetros y el orden en que se esperan dichos parámetros.

\subsection{Ejemplo de la función máximo}

Realizar un programa que permita calcular para tres números enteros cual es el mayor y cual es el menor. La implementación en C y Java se muestra a continuación, note que solamente en C, es necesario declarar los prototipos de función.

\begin{verbatim}
/* 
 * File:   maximo_minimo.c
 * Author: felix
 *
 * Created on 28 de marzo de 2012, 13:57
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * 
 */

// Prototipo de Funcion

int maximo(int x, int y, int z);  

// funcion principal

int main() {
  int a, b, c, max;
    
  printf("Dar tres numeros enteros ");
  scanf("%d%d%d", &a, &b, &c);
    
  max = maximo(a,b,c);
    
  printf("El maximo es %d\n", max);

  return 0;
}

// definicion de la funcion

int maximo(int x, int y, int z)
{
  int max = x;
  
  if(y > max) max = y;
  if(z > max) max = z;
  
  return max;
}

\end{verbatim}

\section{Paso de argumentos a una función y tipo de dato devuelto} 

La definición matemática de una función es $f: \mathbb{R}^N \rightarrow \mathbb{R}$. Esto significa que la función $f$ recibe  un vector de números reales de tamaño $N$ (variable independientes) y regresa un número real resultado de la evaluación. En el caso de las funciones en C tenemos que los valores independientes se ponen entre los paréntesis indicando el tipo de variable de cada una y el tipo de la variable que devuelve se pone al comienzo de la función 

Así por ejemplo cuando escribimos la función $f(x) = x^2$ en C tenemos que escribir

\begin{verbatim}

float f(float x)
{
   return x*x;
}
\end{verbatim}

Al igual que la definición la función se llama $f$ y recibe un número real $x$ y regresa un número real que el el cuadrado $x^2$. 

Otro ejemplo es calcular la suma de dos variables $a$ y $b$ la función en este caso recibe dos argumentos $a$ y $b$ y regresa el valor de $a+b$. La codificación en C es:

\begin{verbatim}

int suma (int a, int b)
{
   return (a+b);
}
\end{verbatim}
 
\subsection{Argumentos de main}

En general la declaración de la función main esta dada como

\begin{verbatim}
    int main (int argc, char **argv);
\end{verbatim}

Lo cual indica que la función main regresa un entero. En algunos sistemas operativos como Windows o Unix, este valor es regresado por la linea de comando dando instrucciones de que el código se ejecuto sin error, para ello enviamos el código EXIT\_SUCCESS o simplemente un cero

\begin{verbatim}
    int main (int argc, char **argv){
       return 0;
     }
\end{verbatim}

Existen al menos dos argumentos de main: argc y argv. El primero de estos es un contador de los argumentos enviados al programa y el segundo un arreglo de cadenas de caracteres con estos argumentos. Estos argumentos son pasados al programa por el sistema operativo en la linea de comando al ejecutar el programa. Así por ejemplo cuando generamos un programa al que llamaremos argumentos\_main, al ejecutarlo tendremos

\begin{verbatim}
    ./argumentos_main Hola Mundo Cruel
\end{verbatim}

Las variable argc tendrá un 4 como valor y argv será un arreglo de caracteres con las palabras argumentos\_main, Hola, Mundo y Cruel. El siguiente código es un ejemplo de como visualizar los argumentos de main.

\begin{verbatim}
/* 
 * File:   argumentos_main.c
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * 
 */
int main(int argc, char** argv) {
    int i;
    printf("El numero de argumentos es %d\n", argc);
   
    for(i=0; i<argc; i++) {
      printf("%d. %s\n", i, argv[i]);  
    }
    
    return (EXIT_SUCCESS);
}
\end{verbatim}


\noindent
y la ejecución luce como:

\begin{verbatim}
	$ ./argumentos_main Hola Mundo Cruel
	El numero de argumentos es 4
	0. ./argumentos_main
	1. Hola
	2. Mundo
	3. Cruel
\end{verbatim}

\section{Diseño top--down}

Como ejemplo del diseño top--down haremos la implementación de la función seno utilizando serie de Taylor. La función seno puede ser calculada utilizando la serie de Taylor como

$$
seno(x) = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} +
\frac{x^9}{9!} - ....
$$


Para llevar a cabo la implementación necesitamos de dos funciones mas, la función factorial y la función potencia. Comenzaremos por escribir la función factorial. El factorial de un número se define como

$$
1! = 1
$$
$$
2! = 1*2
$$
$$
3! = 1*2*3
$$
$$
4! = 1*2*3*4
$$
$$
\\
$$

$$
n! = 1*2*3*4*5*...*n-1*n
$$

y la implementación queda como

\begin{verbatim}
  double factorial(int x)
  {
    int i;
    double fact = 1;

    for(i=1; i<=x; i++)
      fact *= i;

    return fact;
  }
\end{verbatim}

Tenemos que elevar un número real a una potencia entera, así pues, si x es el número real para elevarlo a cualquier potencia hacemos:

$$
x^2 = x*x
$$
$$
x^3 = x*x*x
$$
$$
\\
$$
$$
x^n = x*x*x*...*x\\
$$

La implementación de esta función es:

\begin{verbatim}
  double pow(double x, int n)
  {
    int i;
    double pow =1;

    if(x==0) return 0;

    for(i=1; i<=n; i++)
      pow = pow*x;

    return pow;
  }
\end{verbatim}


En este caso escribiremos dos archivos, el primero Mat\_fun.c y uno segundo ejemplo\_uso\_Mat\_fun.c. El código del primero es

\begin{verbatim}
//Ejemplo de Mat_fun.c
/**
 * <p>Title: Funciones Trigonometricas</p>
 *
 * <p>Description: Implementa la función seno utilizando series de Taylor</p>
 *
 * <p>Copyright: Copyright (c) 2003</p>
 *
 * <p>Company: UMSNH</p>
 *
 * @author Dr. Felix Calderon Solorio
 * @version 1.0
 */

double seno(double x);
double factorial(int x);
double pow(double x, int n);


double seno(double x) {
  int i;
  double s = 0;
  int signo = 1;

  for (i = 1; i < 10; i += 2) {
    s += signo * pow(x, i) / factorial(i);
    signo *= -1;
  }
  return s;
}

double factorial(int x) {
  int i;
  double fact = 1;

  for (i = 1; i <= x; i++)
    fact *= i;

  return fact;
}

double pow(double x, int n) {
  int i;
  double pow = 1;

  if (x == 0)return 0;

  for (i = 1; i <= n; i++)
    pow = pow * x;

  return pow;
}
\end{verbatim}

Para probar el archivo tenemos que escribir el código:

\begin{verbatim}
//ejemplo_uso_Mat_fun.c
/**
 * <p>Title: Uso de la funciones Mat_fun</p>
 *
 * <p>Description: Utiliza las funciones creadas </p>
 *
 * <p>Copyright: Copyright (c) 2003</p>
 *
 * <p>Company: UMSNH</p>
 *
 * @author Dr. Felix Calderon Solorio
 * @version 1.0
 */

#include <stdio.h>
#include "Mat_fun.c"

int main()
{
  int i,N;

  double inicio = -3.1416, fin = 3.1416, incremento = 0.1;

  N = (int)((fin - inicio)/incremento) + 1;

  double x, y;

  for(i=0;  i<N; i++)
  {
    x = inicio + incremento *i;
    y = seno(x);

	printf("%f %f \n", x, y);
  }

  return 0;
}
\end{verbatim}

Note que para incluir las funciones en C se utiliza la instrucción

\begin{verbatim}
#include "Mat_fun.c"
\end{verbatim}
la cual da a conocer al
compilador en donde se localizan las funciones.


\subsection{Ceros de una función}

En el caso de una función lineal el calcular los ceros de una función, es una tarea relativamente fácil donde despejando la variable en cuestión podemos calcular el valor para el cual la función se hace cero. En el caso de una función no lineal el problema es mas complejo y es común utilizar el método de Newton Raphson.

Dado que la función que queremos resolver es no lineal el Método de Newton Raphson hace una linealización por medio de la serie de Taylor así

\begin{equation*}
f(x) = f(x_0) + \frac{df(x_0)}{dx} (x -x_0) + \frac{1}{2} \frac{d^2 f(x_0)}{dx^2} (x- x_0)^2 + \cdots
\end{equation*}

\noindent
Si despreciamos los términos de orden mayor a dos  podemos hacer una aproximación lineal para nuestra función

\begin{equation*}
f(x_0) + f'(x_0) (x -x_0) =0
\end{equation*}

\noindent
y despejamos el valor de $x$ tenemos que

\begin{equation*}
x = x_0 - \frac{f(x_0)} {f'(x_0)}
\end{equation*}

Si el valor calculado de $x$ lo llamamos $x_1$ tenemos un procedimiento iterativo para calcular la solución. A este procedimiento se le conoce como el algoritmo de Newton Raphson para el calculo de ceros de una función. La iteración del método se muestra en la siguiente ecuación

\begin{equation*}
x_{k+1} = x_k - \frac{f(x_k)} {f'(x_k)}
\end{equation*}

\noindent
Así dado un valor inicial $x_0$ lo suficientemente cerca, podemos calcular las raíces de la función. El siguiente código muestra los ceros de la función coseno calculados a partir de un punto inicial $x_0 = 0.5$

\begin{verbatim}
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/*
 * Newton_Raphson.c
 */
float f(float x);
float df(float x);
float Newton_Raphson(float x0);
/**
 * Funcion a calcular sus raices
 */

float f(float x) {
    return cos(x);    
}

/**
 * Derivada de la funcion
 */

float df(float x){
    return -sin(x);
}

/**
 * Esta funcion calcula los ceros de una funcion por el metodo de
 * Newton Raphson
 */

float Newton_Raphson(float x0){
    float x = x0, diferencia;
    
    do {
        diferencia = f(x)/df(x);
        printf("%f %f\n", x, diferencia);
        x = x - diferencia;
    } while(diferencia*diferencia > 0.0000001);
    
    return x;
}

int main(int argc, char** argv) {
    printf("%f\n", Newton_Raphson(0.5));

    return (0);
}
\end{verbatim}

\noindent
Al ejecutar el código se produce la siguiente sucesión y la solución es 1.570796

\begin{verbatim}
0.500000 -1.830488
2.330488 0.949864
1.380623 -0.192499
1.573123 0.002326
1.570796 0.000000
1.570796
\end{verbatim}

\subsection{Raiz Cuadrada}

Podemos utilizar el método de Newton Raphson para realizar el calculo de la raíz cuadrada si planteamos el problema como calcular los ceros de la función $f(x) = x^2 - R$. En este caso la solución utilizando el método de Newton Raphson es

\[
f(x) = x^2 -R \\
\]
\[
f'(x) = 2x
\]

Sustituyendo tenemos
\[
x_{k+1} = x_k - \frac{x_k^2-R} {2x_k}
\]
\[
x_{k+1} = \frac{2x_k^2 - x_k^2+R} {2x_k}
\]
\[
x_{k+1} = \frac{x_k^2 +R} {2x_k}
\]

Como valor inicial supondremos $x_0 = R$ y el código en C para esta implementación se muestra a continuación

\begin{verbatim}
/* 
 * File:   raiz_cuadrada.c
 * Author: felix
 *
 * Created on 12 de octubre de 2011, 11:53
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * 
 */

float Raiz(float R){
    float x0 = R, x1 = R;
    
    do {
        x0 = x1;
        x1 = (x0 *x0  + R)/(2.0*x0);
        
        printf("%f \n", x1 );
    } while((x1-x0)*(x1-x0) > 0.0000001);
    
    return x1;
}


int main(int argc, char** argv) {
    printf("%f\n", Raiz(144));
    
    
    return (0);
}
\end{verbatim}

\noindent
Cuando corremos el código calculamos la raíz cuadrada de 144 y el resultado en la siguiente sucesión donde podemos notar que el valor final es 12, el cual corresponde a la raíz cuadrada de 144.

\begin{verbatim}
72.500000 
37.243103 
20.554794 
13.780230 
12.114991 
12.000546 
12.000000 
12.000000 
12.000000
\end{verbatim}

\subsection{Máximo Común Divisor}
En matemáticas, se define el máximo común divisor (abreviado MCD) de dos o más números enteros al mayor número que los divide sin dejar resto. Por ejemplo, el MCD de 42 y 56 es 14. En efecto, $\frac {42} {14}=3$, $ \frac {56} {14} = 4$ , y 3 y 4 son primos entre sí (no existe ningún número natural aparte de 1 que divida a la vez al 3 y al 4).

Al dividir $a$ entre $b$ (números enteros), se obtiene un cociente $q$ y un residuo $r$. Es posible demostrar que el máximo común divisor de $a$ y $b$ es el mismo que el de $b$ y $r$ (Sea $c$ el máximo común divisor de $a$ y $b$. Como $a=bq+r$ y $c$ divide a $a$ y a $b$ divide también a $r$. Si existiera otro número mayor que $c$ que divide a $b$ y a $q$, también dividiría a $a$ , por lo que $c$ no sería el $\mathrm{mcd}$ de $a$ y $b$, lo que contradice la hipótesis). éste es el fundamento principal del algoritmo. También es importante tener en cuenta que el máximo común divisor de cualquier número $a$ y $0$ es precisamente $a$. Para fines prácticos, la notación $\mathrm{mcd}(a,b)$ significa máximo común divisor de $a$ y $b$.

Según lo antes mencionado, para calcular el máximo común divisor de 2366 y 273 se puede proseguir de la siguiente manera:

\begin{center}
\begin{tabular}{|c|c|c|}
\hline
Paso 	& Operación &	Significado \\
\hline
1 	& 2366 dividido entre 273 es 8 y sobran 182 &	$\mathrm{mcd}(2366,273)=\mathrm{mcd}(273,182)$ \\
2 	& 273 dividido entre 182 es 1 y sobran 91 	& $\mathrm{mcd}(273,182)=\mathrm{mcd}(182,91)$ \\ 
3 	& 182 dividido entre 91 es 2 y sobra 0 	& $\mathrm{mcd}(182,91)=\mathrm{mcd}(91,0)$\\
\hline
\end{tabular}
\end{center}

La codificación del algoritmo de Euclides es:

\begin{verbatim}
/* 
 * File:   MCD_MCM.c
 * Author: felix
 *
 * Created on 19 de septiembre de 2011, 17:05
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * 
 */

int EuclidesMCD(int a, int b){

    int aux;
    int mayor = a > b ? a : b;
    int menor = a < b ? a : b;
    
    do{
        aux = menor;
        menor = mayor % menor;
        mayor = aux;  
    } while(menor!=0);
    return mayor;
}

int EuclidesMCM(int a, int b) {
    return(a/EuclidesMCD(a,b))*b;
}

int main(int argc, char** argv) {
    //int a = 10, b = 25;
    int a = 48, b= 60;
    printf("El Maximo comum Divisior de %d y %d es %d\n", a, b, EuclidesMCD(a, b));
    printf("El Minimo comum multiplo de %d y %d es %d\n", a, b, EuclidesMCM(a, b));
    
    return (EXIT_SUCCESS);
}
\end{verbatim}

La manera en que calcularemos el MCD es utilizando el algoritmo de Euclides el cual se describe como:
\noindent
Entrada: Valores $a$ y $b$ pertenecientes a un dominio euclídeo \\
Salida: Un máximo común divisor de $a$ y $b$ \\
    $r_0 \gets a, r_1\gets b$ \\
    $i\gets1$\\
    Mientras $r_i\neq 0$ haga lo siguiente: \{\\
        $r_{i+1}\gets r_{i-1}\;\bmod\; r_i$\\
        $i\gets i+1$\\
     \} \\   
    El resultado es: $r_{i-1}$\\

\section{Recursividad}

Un método recursivo es un método que se llama a si mismo directa o indirectamente o a través de otro método. Un ejemplo interesante de recursion es la función factorial. La definición de factorial esta dada por el producto: 

$$
n! = n*(n-1)*(n-2)*...*3*2*1
$$

Note que esta definición la podemos escribir de manera recursiva como:
\[
n! = n*(n-1)!
\]

En común representar a las funciones recursivas en dos pasos. El primero de ellos es conocido como Paso Base y Paso Recursivo. El primero es la condición más sencilla de la definición y normalmente es trivial hacer el cálculo y el segundo es el paso recursivo. Para el caso del Factorial tenemos

\noindent
$factorial(N)$

\noindent
Base

Si $N=1$ el factorial es 1

\noindent
Paso Recusivo

Si no $n \times factorial(N-1)$
 

Este método lo podemos escribir  C queda como

\begin{verbatim}
// factorial.c

/**
 * <p>Title: factorial</p>
 *
 * <p>Description: Calcula el factorial de un numero usando recursividad</p>
 *
 * <p>Copyright: Copyright (c) 2003</p>
 *
 * <p>Company: UMSNH</p>
 *
 * @author Dr. Felix Calderon Solorio
 * @version 1.0
 */

#include <stdio.h>
double factorial(int N) ;

int main() 
{
  int i; 
  for (i = 0; i < 10; i++)
    printf("%d! = %f\n", i, factorial(i));

  return 0;
}

double factorial(int N) 
{
  if (N == 0)return 1;
  else return (N * factorial(N - 1));
}
\end{verbatim}

Otro ejemplo de definición recursiva es la multiplicación de números naturales. El producto a*b, donde a y b son enteros positivos, puede definirse como

\noindent
$Multiplica (x, y)$

\noindent
Base

Si $y=1$  el producto es y

\noindent
Paso Recusivo

Si no el resultado es $x + Multiplica(x, y-1)$

\begin{verbatim}
// Ejemplo multiplica.c

/**
 * <p>Title: Multiplicación</p>
 *
 * <p>Description: Multiplica dos numeros utilizando recursividad</p>
 *
 * <p>Copyright: Copyright (c) 2003</p>
 *
 * <p>Company: UMSNH</p>
 *
 * @author Dr. Felix Calderon Solorio
 * @version 1.0
 */

#include <stdio.h>

double multiplica(int x, int y);

int main()
{
  int x=4, y=5;
  printf("%f\n", multiplica(4,5));
  return 0;
}
  
double multiplica(int x, int y)
{
   if(y == 1) return x;
   else return (x + multiplica(x,y-1));
}
\end{verbatim}



\subsection{Método de Bisecciones}

Este método es conocido también como de corte binario. de partición en dos intervalos iguales o método de Bolzano. Es un método de búsqueda incremental donde el intervalo de búsqueda se divide en dos. Si la función cambia de signo sobre un intervalo, se calcula el valor en el punto medio. El nuevo intervalo de búsqueda será aquel donde el producto de la función cambie de signo.

La definición recursiva para este algoritmos es:

Dada una función $f(x)$ y un intervalo $[inicio,fin]$ de búsqueda donde existe un cruce por cero, podemos notar que $f(a) \times f(b) < 0$ porque la función en el intervalo pasa de menos a mas o de mas a menos debido a que cruza por cero. Así tenemos:

\noindent
$Biseccion(inicio, fin)$

\noindent
Base

Si $b-a < \epsilon$ la solución es $(a+b)/2$

\noindent
Paso Recusivo

Calcular $mitad =\frac{inicio+fin}{2}$ 

Si  $f(inicio)\times f(mitad) <0$ entonces $Biseccion(inicio,mitad)$

Si no $Biseccion(mitad,fin)$

\noindent
Ejemplo

Considere la función f(x) = x-cosx, a priori sabemos que la función tiene un cruce por cero en el intervalo [0,1], asÌ que nuestra búsqueda se concentrará en este.

\begin{flushleft}
\begin{tabular}{|c|c|c|c|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
iter & inicio & mitad & fin &  f(ini) &  f(mitad) & f(fin) \\
  \hline
0 &  0.0 &  0.5 &  1.0 & -1.0 & -0.3775 & 0.4596 \\
1 & 0.5 & 0.75 & 1.0 & -0.3775 & 0.0183 & 0.4596 \\
2 &  0.5 & 0.625 & 0.75 & -0.3775 & -0.1859 & 0.0183 \\
3 & 0.625 & 0.6875 & 0.75 & -0.1859 & -0.0853 & 0.0183 \\
4 & 0.6875 & 0.71875 &  0.75 & -0.0853 & -0.0338 & 0.0183 \\
5 & 0.71875 & 0.734375 & 0.75 & -0.0338 & -0.0078 & 0.0183 \\
6 &  0.734375 & 0.7421875 & 0.75 & -0.0078 & 0.0051 & 0.0183 \\
7 & 0.734375 & 0.73828125 & 0.7421875 & -0.0078 & -0.0013 & 0.0051\\
8 & 0.73828125 & 0.740234375 & 0.7421875 & -0.0013 & 0.0019 &
0.0051 \\
9 & 0.73828125 & 0.7392578125 & 0.740234375 & -0.0013 & 0.0002 &
0.0019\\
  \hline
\end{tabular}
\end{flushleft}


La implementación recursiva de este algoritmo en C es:

\begin{verbatim}
//Ejemplo bisecciones.c

/**
 * <p>Title: Metodo de Bisecciones</p>
 *
 * <p>Description: Calcula el cruce por cero de una función utlizando el
 * metodo de bisecciones</p>
 *
 * <p>Copyright: Copyright (c) 2003</p>
 *
 * <p>Company: UMSNH</p>
 *
 * @author Dr. Felix Calderon Solorio
 * @version 1.0
 */

#include <stdio.h>
#include <Math.h>

double Biseccion(double ini, double fin);
double funcion(double x);

int main()
{
  printf("La solucion esta en %f\n", Biseccion(0,1));
  return 0;
}
  
double Biseccion(double ini, double fin)
{
  double mitad;    mitad = (fin + ini)/2.0;
  printf("f_1(%f) = %f f_m(%f) = %f f_2(%f) = %f\n", ini, funcion(ini),
          mitad, funcion(mitad), fin, funcion(fin));
  if((fin - ini) > 1e-12)
  {
    if(funcion(ini)*funcion(mitad) < 0)
      return Biseccion(ini, mitad);
    else return Biseccion(mitad, fin);
  }
  else return (mitad);
}

double funcion(double x)
{
  return (x - cos(x));
}
\end{verbatim}


\subsection{Torres de Hanoi}

El ejemplo más conocido, de recursividad entre los programadores, es el problema de las torres de Hanoi. Para este juego, se tienen tres postes (A, B, C) y un conjunto n de discos colocados de mayor a menor diámetro en alguno de los postes, por ejemplo el poste A. La meta es mover todos los discos del poste A al poste C con las siguientes restricciones: en cada movimiento solo se puede tomar un disco y colocarlo en cualquier poste y no se debe colocar, un en un poste,  un disco de diámetro mayor sobre un disco de diámetro menor.

La definición recursiva de las torres de Hanoi es:

\noindent
$mover\_discos(origen, auxiliar, destino, discos)$

\noindent
Base

Si $discos=1$ Mover un disco de $origen$ a $destino$

\noindent
Paso recursivo

Mover $n-1$ discos de $origen$ a $auxiliar$ 

Mover 1 disco de $origen$ a $destino$

Mover $n-1$ discos de $auxiliar$ a $destino$

\noindent
La implementación en C queda

\begin{verbatim}
/* 
 * File:   torres_hanoi.c
 * Author: felix
 *
 * Created on 18 de octubre de 2011, 10:38
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * Torres de Hanoi
 */

int movtos ;
void mover_discos(char a, char b, char c, int n);

int main()
{
    movtos = 1;
   mover_discos('A', 'B', 'C', 4);
   return 0;
}

void mover_discos(char a, char b, char c, int n)
{
    if (n > 0) {
        mover_discos(a, c, b, n - 1);
        printf("%d Mover un disco del poste %c al poste %c\n", movtos++, a, c);
        mover_discos(b, a, c, n - 1);
    }
}
\end{verbatim}


La solución con tres discos es:

\begin{verbatim}
Mover un disco del poste A al poste B

Mover un disco del poste A al poste C

Mover un disco del poste B al poste C

Mover un disco del poste A al poste B

Mover un disco del poste C al poste A

Mover un disco del poste C al poste B

Mover un disco del poste A al poste B
\end{verbatim}



\subsection{Algoritmo de quicksort}

Sea x un arreglo y n el número de elementos en arreglo que se debe ordenar. Elegir un elemento a de una posición especifica en el arreglo (por ejemplo, a puede elegirse como el primer elemento del arreglo. Suponer que los elemento de x están separados de manera que a está colocado en la posición j y se cumplen las siguientes condiciones.

\begin{enumerate}
    \item Cada uno de los elementos en las posiciones de 0 a j-1 es
menor o igual que a.
    \item Cada uno de los elementos en las posiciones j+1 a n-1 es
mayor o igual que a.
\end{enumerate}

Observe que si se cumplen esas dos condiciones para una a y j particulares, a es el j-ésimo menor elemento de x, de manera que a se mantiene en su posición j cuando el arreglo está ordenado en su totalidad. Si se repite este procedimiento con los subarreglos que van de x[0] a x[j-1] y de x[j+1] a x[n-1] y con todos los subarreglos creados mediante este proceso, el resultado final será un archivo ordenado.

Ilustremos el quicksort con un ejemplo. Si un arreglo esta dado por:

x = [25 57 48 37 12 92 86 33]

y el primer elemento se coloca en su posición correcta, el arreglo
resultante es:

x = [12 25 57 48 37 92 86 33]

En este punto 25 esta en su posición correcta por lo cual podemos
dividir el arreglo en

x = [12] 25 [57 48 37 92 86 33]

Ahora repetimos el procedimiento con los dos subarreglos

x = 12  25  [48 37 33] 57 [92 86]

x = 12  25  33 [37 48]  57 [86] [92]

x = 12  25  33 [37 48]  57  86 92

x = 12  25  33 37 48  57  86 92

El procedimiento es entonces.

Buscar la partición del arreglo j. Ordenar el sub-arreglo x[0] a x[j-1] Ordenar el sub-arreglo x[j+1] a x[n-1]

Su implementación en Java es:

\begin{verbatim}
  public void quiksort(int x[],int lo,int ho)
  {
    int t, l=lo, h=ho, mid;

    if(ho>lo)
    {
      mid=x[(lo+ho)/2];
      while(l<=h)
      {
        while((l<ho)&&(x[l]<mid))  ++l;
        while((h>lo)&&(x[h]>mid))  --h;
        if(l<=h)
        {
          t    = x[l];
          x[l] = x[h];
          x[h] = t;
          ++l;
          --h;
        }
      }

      if(lo<h) quiksort(x,lo,h);
      if(l<ho) quiksort(x,l,ho);
    }
  }
\end{verbatim}