Menu Principal | VIM | Clase 1 | Clase 2 | Clase 3 | Clase 4

Recursividad en las funciones

La serie de fibonacci

Uno de los primeros ejemplos utilizados en el uso de las funciones en C es la serie de fibonacci.

Es una sucesión infinita de números naturales que comienza con 0 y 1, donde el siguiente número es la suma de los dos previos.

 0,1,1,2,3,5,8,13,21,...

Esta sucesión fue descrita en Europa por Leonardo de Pisa (conocido como Fibonacci). Nuestra intención es ahora escribir un programa que nos devuelva cuál es el número de fibonacci, indicando cualquier elemento de la serie.

Es decir, si a nuestro programa le preguntamos qué numero es el elemento 4 de la seria nos diga 2 o bien si le preguntamos cuál es el elemento 9 de la serie nos diga 21

Para eso vamos a utilizar la recursividad en la función.

Notemos algunas características de la función :

 E_n = E_(n-1) + E_(n-2)

Es decir el elemento n es igual a la suma de los dos anteriores, por ejemplo si le preguntamos por el elemento 6, entonces

 E_6 = E_5 + E_4

Pero el elemento E_5 y el E_4

 E_5 = E_4 + E_3

 E_4 = E_3 + E_2

Pero el elemento 2 y el 1 ya lo conocemos (0 y 1) ya que son la base de la serie, note entonces el carácter recursivo de la serie.

Entonces nuestra función

 int fibo(int n)
 {
   if(n==2) return 1;
   else if(n<=1) return 0;
   else return (fibo(n-1) + fibo(n-2)); 
 }

NOTE que para cada caso de if, se omiten las { (llaves) de apertura y cierre, esto es posible aprovechando que para cada uno existe solo una acción

Veamos el código completo.

 #include <stdio.h>

 int fibo(int n)
 {
  if(n==2) return 1;
  else if(n<=1) return 0;
  else return fibo(n-1)+fibo(n-2);
 }

 int main()
 {
  int f=0;
  while(1)
  {
   printf("numero de la lista >> " );
   scanf("%d",&f);
   printf("El valor es = %d\n", fibo(f));
  }
  return 0;
 }

Notemos que el código presenta un while(1) eso quiere decir que siempre se está cumpliendo la acción (1=true 0=false). Entonces la forma de terminar el programa es presionando control-c.

Buscando las raíces de una ecuación

Supongamos que tenemos una función f(x), y queremos encontrar para qué valores de x se cumple que f(x) = 0. Para ésto existen variados métodos, de Newton, Bisección, de la Secante (hint : Estúdienlos para la prueba), etc.

Ahora veremos cómo podemos encontrar la raíz utilizando el método de bisección.

La idea es tomar un intervalo [a,b] en donde buscaremos la raíz, sabiendo que f(a) y f(b) tienen distinto signo. El algoritmo toma un valor intermedio c = (a+b)/2 y con eso sólo quedan las posibilidades f(a) y f(c) o f(c) y f(b) pueden tener el mismo signo o cambiar, en el par que cambia el signo se busca nuevamente.

¿Qué condición tenemos cuando se ha llegado a 'arrinconar el punto donde se corta el eje?

- EL INTERVALO SE HACE TAN PEQUEÑO COMO CIERTA TOLERANCIA -

Entonces necesitamos

 #include <stdio.h>
 #include <math.h>

 double funcion(double x)
 {
  return log(x)*exp(x) - x*x;
 }

 int main()
 {
   double a=1,b=2,tol=1E-8,c=1.5;
   double range = b-a;
   ....

Ahora viene la parte fundamental, lo que haremos es, si el rango sigue siendo mayor que la tolerancia, entonces seguimos en la búsqueda de la raíz. Y para cada punto vemos donde se cumple que el signo de la función evaluada entre los puntos cambia de signo.

  while(fabs(range)>tol)
  {
   c = (a+b)/2;
   if(funcion(a)*funcion(c) < 0 )
   {
    b = c;
    range = b-a;
   }
   else if(funcion(c)*funcion(b) < 0)
   {
    a=c;
    range = b-a;
   }
  }

Finalmente imprimimos la información en pantalla.

  printf("El valor de la raiz es =%lf \n", c);
  return 0;
 }

Listo!!, ahora podemos hacer algunas variaciones, por ejemplo cambiar la tolerancia y poner un contador para ver cuántas iteraciones tuvo que realizar el programa para encontrar el mínimo.

 #include <stdio.h>
 #include <math.h>

 double funcion(double x)
 {
  return log(x)*exp(x) - x*x;
 }

 int main()
 {
  double a=1,b=2,tol=1E-8,c=1.5;
  double range = b-a;
  int counter = 0;
  while(fabs(range)>tol)
  {
   c = (a+b)/2;
   if(funcion(a)*funcion(c) < 0 )
   {
    b = c;
    range = b-a;
   }
   else
   {
    a=c;
    range = b-a;
   }
  counter = counter + 1;
  }
  printf("El valor de la raiz es =%lf \n", c);
  printf("Se neceistaron %d iteraciones \n", counter);
  return 0;
 }