Funciones recursivas


Ya he escrito un artículo muy, muy básico sobre este tipo de funciones.

Ahora quiero discutir un aspecto de cómo llevar a cabo algunos cálculos para ahorrar tiempo de ejecución. Todo lo que he hecho aquí lo he hecho con la función de fibonacci f.

f_0 = 0\\    f_1 = 1\\    f_n = f_{n-1}+f_{n-2} .

Los primeros términos son: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.

Una función recursiva definida sobre elementos anteriores, si no depende del índice n se puede expresar en función de ese índice de la siguiente manera:

Si tenemos una función recursiva del tipo: f_n = a_1f_{n-1} + a_2f_{n-2} + ... a_kf_{n-k}, esta la podemos reordenar para igualarla a 0: f_n - a_1f_{n-1} - a_2f_{n-2} - ... a_kf_{n-k} = 0. Y a esto le podemos asignar una ecuación característica del tipo: x^{n-1} - a_1x^{n-2} - a_2x^{n-3} - ... a_kx^{n-n} = 0.

Si encontramos las soluciones de esta ecuación, sean estas a lo más n-1 raíces llamadas r_1, r_2... r_{n-1}, podemos expresar la función recursiva como:

c_1r_1^n + c_2r_2^n + ... + c_{n-1}r_{n-1}^n

Esos coeficientes c_i deben ser tales que la función coincida con las condiciones iniciales dadas. Más tarde lo veremos con un ejemplo con una más sencilla que la de Fibonacci. Baste saber que al hacer todo este proceso con la función de Fibonacci llegamos a la siguiente función:

fib(n) = \frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2} \right)^n - \frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2} \right)^n.

Nótese la aparición del número áureo, al que llamaremos, para simplificar la ecuación \varphi = \frac{1+\sqrt{5}}{2}. La ecuación simplificada queda:

fib(n) = \frac{\varphi^n-(1-\varphi)^n}{\sqrt{5}}.

El cometido de este artículo es claro, ¿es computacionalmente aceptable usar esta expresión para hallar los números de la sucesión, o es más fiable hacer la sucesión elemento a elemento?

La diferencia es clara, al hacer la sucesión elemento a elemento trabajamos con números enteros, sólo hacemos sumas de enteros, y por lo tanto, mientras la memoria lo permita, tendremos números exactos guardados en la memoria. Al trabajar con la fórmula anterior entran en juego números reales no racionales \sqrt{5}, y cometemos irremediablemente errores de redondeo. Usar la fórmula nos ahorra, sin embargo, el tener que generar todos los elementos anteriores cada vez que queramos uno, o el tener que guardar previamente una lista de n elementos en la memoria.

He programado un sencillo programa que produjera dos listas con los primeros 1001 números de la sucesión de fibonacci, para ver cómo de grande era el error. Aquí están: http://neowriter.eshost.es/ en un enlace al final de la web (recuerda hacer click en la publi). No recuerdo cuál de las dos listas es cuál, pero da lo mismo, lo importante es la diferencia. Como podéis ver, en la columna 13 aproximadamente empieza a aparecer el error. El error aparece muy pronto, sin embargo, se mantiene hasta el final de la lista, cuando llegamos a números de 200 cifras. Esto hace que el error relativo sea bastante pequeño, del orden de 10^{-13}. Bastante aceptable.

Mi veredicto es que, a no ser que necesitemos una exactitud maravillosamente buena, es mucho más rápido usar directamente la función sin tener por qué perder calidad.

Veámoslo con otra función recursiva, cuya ecuación tiene soluciones racionales.

f_n = -2f_{n-1}+3f_{n-2}\\    f_0 = 1\\    f_1 = 3.

Su ecuación característica es: x^2+2x-3, cuyas soluciones son 1 y -3: x^2+2x-3 = (x-1)(x+3). La función será del tipo f_n = c_11^n +c_2(-3)^n = c_1 +c_2(-3)^n. Si sustituimos con las condiciones iniciales, tenemos que si n=0, entonces f_n = 1, y si n=1, entonces f_n = 3. Sistituimos y nos queda el sistema:

c_1+c_2 =1\\    c_1-3c_2 = 3.

Las soluciones son c_1 = \frac{3}{2} y c_2 = -\frac{1}{2}, de modo que la función recursiva descrita arriba es de la forma:

f_n = \frac{3}{2}-\frac{(-3)^n}{2}

Vemos que coincide tanto con las condiciones iniciales como con los siguientes elementos de la sucesión. Sería fácil demostrar por inducción la validez de tal fórmula. Si hacemos las listas de elementos con ambos métodos, colgadas en la misma web que arriba, archivo rec.zip.

Vemos lo mismo, curiosamente, el error aparece pronto, sin embargo se mantiene en la misma cifra, en este entre la 14 y 16, consiguiendo así un error relativo del orden de 10^{-14} \quad 10^{-16}, esto antes de que nos quedemos sin espacio en el IE³ 754 para tanto número 😉

Hasta aquí este artículo, espero que haya resultado interesante.

Anuncios
Esta entrada fue publicada en Manuales, Tutoriales y etiquetada , , , , , , , , , . Guarda el enlace permanente.

8 respuestas a Funciones recursivas

  1. D555 dijo:

    Tengo una pregunta para ti, porque puede asignarle un polinomio característico (?), y la otra en que lenguage escribiste los programas (?)

    • theneowriter dijo:

      El lenguaje de los programas, la verdad no me acuerdo porque borro estos programas pequeños conforme los voy usando. Sería o C o matlab, alguno de los dos. Me parece que Matlab, dado el número de cifras a las que llegan las listas de números.

      A lo del polinomio, sinceramente, no lo se. Es como yo lo he estudiado. Supongo que lo que son las soluciones del polinomio podrían sacarse directamente de la función a pelo, pero hacer el polinomio lo hace más simple y es más fácil verlo.
      Acabo de leer en mi teoría que los he llamado mal, ya que no son polinomios, no son funciones, sino que son ecuaciones de una variable que igualas a 0 desde el principio.
      ¿Por qué funciona? No lo se, aunque todos los resultados se pueden probar fácilmente por inducción.

      Un saludo y gracias por leerme.

  2. Pingback: Funciones recursivas | White-Hat Hacking

  3. pikixtlaniman dijo:

    Es posible que hagas un programa que genere los primeros 1001 digitos como lista, pero vertical? (es decir, los numeros seguidos no, sino que por cada fila sea un numero, espero darme a entender…). De antemano, gracias.

    • theneowriter dijo:

      Me da la impresión de que son deberes… Para eso ni siquiera necesitas una función recursiva: con un simple for recorres los 1001 primeros números o los vas imprimiendo a un archivo poniendo “\n” al final de cada uno para que te salte de línea.

      • pikixtlaniman dijo:

        El inconveniente por mi parte es no saber programación, menos el uso de cada símbolo, motivo por el cual hago esta solicitud. Por ello, solicito como favor o petición formal el listado, para un trabajo personal. Espero respuesta.

    • theneowriter dijo:

      #include
      int main(){
      int i;
      FILE *f=fopen(“archivo.txt”,”w”);
      for (i=0;i<=1001;i++) {
      fprintf(f,"%i\n",i);
      }
      fclose(f);
      return 0;
      }

      Ahí lo tienes. Era muy sencillo, yo que tú me informaría un poco porque este tipo de peticiones suele cabrear mucho a programadores aficionados de internet.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s