Ingeniero en Informática


Informática. Funciones Recursivas


Funciones recursivas

He sido estudiante de programación y entiendo la complejidad que entraña diseñar y tratar de entender las funciones recursivas, por ello voy a realizar un compendio de algunas funciones, que utilice o diseñé durante mis años de estudiante de programación, para ello os pongo una pequeña definición y/o explicación de lo que definen los libros e internet como función recursiva y seguidamente algunas funciones recursivas a modo de ejemplo:


Tipo de función de programación más compleja. Una función común es llamada desde otra función; pero es posible crear funciones que puedan llamarse a sí mismas, las funciones recursivas.
Una función puede ser recursiva tanto de forma directa (si es llamada a sí misma) o de forma indirecta (si llama a una función que luego la llama).
Existen algunos problemas que pueden ser resueltos de forma más eficiente (o su resolución puede ser más naturalmente pensada) utilizando funciones recursivas.
Una función recursiva puede dar origen a un típico problema en programación, la recursión infinita ,que es cuando una función se llama a sí misma infinitas veces. Esto detiene el normal funcionamiento de un programa.
Para que esto no suceda una función recursiva debe ser muy bien pensada. Principalmente una función recursiva debe saber resolver el caso más simple, llamado caso base. Si la función es llamada con el caso base, inmediatamente retorna el resultado (no necesita volver a llamarse a sí misma para poder resolverlo).
Si la función es llamada con un caso más complejo, las sucesivas llamadas a sí mismas irán virtualmente descomponiendo ese caso hasta llegar a un caso base, para luego determinar el resultado final de la función

  • Función que calcula el factorial de un número (en Java)

  • static int factorial(int número){
    if ( número <= 1 ) {
    return 1;
    } else {
    return número*factorial(número-1);
    }
    }

  • Función que calcula la serie de Fibonacci (en C)

  • int fib(int n){
      if ((n == 0) || (n == 1)) return 1;
      else return fib(n-1) + fib(n-2);
    }

  • Algorítmo que realiza la curva de Koch

  • Iniciar_Koch( Punto_Inicial, Longitud, Número_Iteraciones )
    1. Declarar Cursor como un punto y un ángulo
    2. Inicializar Cursor:
    3. Cursor.punto <- Punto_Inicial
    4. Cursor.angulo <- 0
    5. Dibujar_Koch( Cursor, Longitud, Número_Iteraciones )
    6. Terminar

    Dibujar_Koch( Cursor, Dist, N )
    1. Si N = 0 entonces, // A(vanzar)
    2. Cursor.punto <- Avanzar( Cursor, Dist )
    3. Terminar
    4. Si no, entonces, // Recursividad: A->AIADDAIA
    5. Dibujar_Koch( Cursor, Dist/3, N-1 ) // A
    6. Cursor.angulo <- Cursor.angulo + π/3 // I
    7. Dibujar_Koch( Cursor, Dist/3, N-1 ) // A
    8. Cursor.angulo <- Cursor.angulo - π*2/3 // DD
    9. Dibujar_Koch( Cursor, Dist/3, N-1 ) // A
    10. Cursor.angulo <- Cursor.angulo + π/3 // I
    11. Dibujar_Koch( Cursor, Dist/3, N-1 ) // A
    12. Terminar

  • Función que calcula el número de unos necesarios para representar un número en base 2 (en C)

  • int recursivaUnos (int numero){
    int res=0;
    if (numero/2 == 0){
    if (n % 2 == 1) res++;
    } else if (n/2 >0){
    if (n % 2 == 1) res++; }
    recursivaUnos(n/2);
    }
    return res;
    }

  • Función de Ackerman

  • int Ackermann(int p, int q)

    {

    if(p==0) return q+1;

    if(q==0) return Ackermann(p-1,1);

    return Ackermann(p-1,Ackermann(p,q-1));

    }

  • Funciones recursivas, una en C y otra en Pascal, que calculan el número de combinaciones de m objetos en n.


  • int comb(int n, int m)
    {
      if ((n == 0) || (n == m)) return 1;
      else return comb(n-1,m-1) + comb(n-1,m);
    }

    function comb(n, m : integer) : integer
    begin
      if (n = 0) or (n = m) then comb := 1
      else comb := comb(n-1,m-1) + comb(n-1,m)
    end

    16-2-2007




    Descargar
    Enviado por:El remitente no desea revelar su nombre
    Idioma: castellano
    País: Puerto Rico

    Te va a interesar