martes, 30 de agosto de 2016

Capítulo 68: Funciones recursivas en C


Diario de un programador.- Día 167

Funciones recursivas en C

Una función recursiva es una función que se llama a si misma, ya sea en forma directa (que la función se llame a si misma) o en forma indirecta,(que otra función la llame, por ejemplo, que la función 1 llame a la función 2 y la función 2 llame a la 1)
Por lo que estuve leyendo, la finalidad de una función recursiva es crear un ciclo, que en términos computacionales (hablándose de rendimiento) es menos eficiente que si se programa el mismo ciclo utilizando instrucciones for, while o do. ¿Entonces por qué utilizar la recursividad?. La recursividad es útil para representar modelos matemáticos, en otras palabras, un problema matemático (según los entendidos) es más fácil de implementar y leer si se usa la recursividad que su equivalente utilizando la iteración. Un ejemplo clásico (o al menos eso dicen en la web) es calcular el factorial de un número utilizando la recursividad.
Un factorial de un número se representa con un signo de exclamación !. Por ejemplo 5! se lee factorial de 5. Un factorial de un número N, se calcula n * (n - 1) hasta que n sea igual a 1. En nuestro idioma esto significa que si quiero calcular el factorial de 5, entonces se debe calcular 5 * 4 * 3 * 2 * 1. Si quiero calcular el factorial de 3, entonces se multiplica 3 * 2 * 1 etc.

Ejemplo en un código:

#include<stdio.h>

int factorial(int numero);
int factorial(int numero){
  if(numero == 1){
    return 1;
  }
  else{
    return numero * factorial(numero - 1);
  }
}//fin funcion

int main(void){
  int numero;

  printf("Ingresa un numero: ");
  scanf("%d", &numero);

  printf("El factorial de %d es %d\n", numero, factorial(numero));

return 0;

}


La función es la siguiente:

int factorial(int numero){
  if(numero == 1){
    return 1;
  }
  else{
    return numero * factorial(numero - 1);
  }
}

La primera línea de la función:

int factorial(int numero)

Muestra que esta función tiene un tipo de retorno int y que además en su parámetro, solicita un argumento de tipo int.

En las siguientes tres líneas tenemos una instrucción if:

  if(numero == 1){
    return 1;
  }

Esto nos dice que si la variable "numero" (la que recibe de argumento) es igual a 1, entonces retornará un 1 como valor. Esta es la condición que permite que el ciclo finalice, si esta condición está mal planteada, se podría producir un ciclo infinito. Esta condición es conocida como el caso base

En las próximas tres líneas tenemos una instrucción else:

  else{
    return numero * factorial(numero - 1);
  }

Esta instrucción siempre se ejecutará a menos que la variable "numero" sea igual a 1. Esta instrucción devuelve como resultado el valor de la variable multiplicado por un llamado a la función con argumento de la variable "numero" menos 1.

La siguiente modificación al programa anterior, mostrará la secuencia:

#include<stdio.h>

int factorial(int numero);

int factorial(int numero){
  if(numero == 1){
    printf("%d\n", numero);
    return 1;
  }
  else{
    printf("%d * ", numero);
    return numero * factorial(numero - 1);
  }
}//fin funcion

int main(void){
  int numero;

  printf("Ingresa un numero: ");
  scanf("%d", &numero);

  printf("El factorial de %d es %d\n", numero, factorial(numero));

return 0;
}


Otro ejemplo. La serie Fibonacci:

La Serie Fibonacci, tiene la siguiente secuencia: 0,1,1,2,3,5,8,13,21...N.

Empieza con cero y uno. Los números siguientes son el resultado de la suma de los dos números anteriores. Por ejemplo. Después del cero y el uno le sigue un uno, que es el resultado de 0 + 1, luego sigue el 2, que es el resultado de 1 + 1, luego sigue el 3 que es el resultado de 1 + 2, luego 5 que es el resultado de 2 + 3 y así sucesivamente.
La serie fibonacci puede ser definida en forma recursiva como sigue a continuación:
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)

Si implementamos esa fórmula en un código, quedaría de la siguiente forma:

#include<stdio.h>

int fibonacci(int numero);

int fibonacci(int numero){
  if(numero == 0 || numero == 1){//caso base
    return numero;
  }
  else{
    return  fibonacci(numero - 1) + fibonacci(numero - 2);
  }
}//fin funcion

int main(void){
  int numero;

  printf("Ingresa un numero: ");
  scanf("%d", &numero);

  printf("Fibonacci %d es: %d",numero, fibonacci(numero));

return 0;
}



Esto muestra que 55, se encuentra en la posición 10 de la secuencia. Ejemplo:
0,1,1,2,3,5,8,13,21,34,55

Los números fibonacci rápidamente se hacen grandes. Cada nivel de recursión en la función tiene un efecto duplicador sobre el número de llamadas a las funciones. Esto sería de un orden de 2n Por ejemplo, para calcular la posición número 20 de la secuencia 220, se requieren aproximadamente un millón de llamadas a las funciones, para la posición número 30 se requieren unas mil millones de llamadas. Hacer tantos millones de llamadas a las funciones hace que el resultado demore mucho en llegar (Quizás hasta se cuelgue el programa antes de mostrar algo). Este es un ejemplo que muestra que las soluciones recursivas son menos eficientes que las iterativas. En mi caso particular, hice pruebas con 20 y 30, mostrándome resultados inmediatos. Al hacerlo con 40, se demoró unos 5 segundos en mostrar el resultado. Al hacer la prueba con 50, me aburrí de esperar el resultado. Para tener una idea, con el shell de python hice unos cálculos para tener una idea de cuantas llamadas se requieren para las funciones.   

Lo anterior es conocido como la "complejidad exponencial".

Algo a tener presente es que cualquier problema que puede ser resuelto en forma recursiva, también puede ser resuelto en forma iterativa, por lo tanto se debe evitar la recursión si lo que se busca es rendimiento. Normalmente se escogen soluciones recursivas por un asunto de que es más natural al problema y resulta más fácil de comprender y depurar.
Esto es todo por ahora. Saludos

Gustavo J. Cerda Nilo
Abril 2016, Agosto 2016


http://codigogx.blogspot.cl/2016/08/capitulo-62-numeros-aleatorios-en-c.html http://codigogx.blogspot.cl/2016/10/capitulo-74-busqueda-lineal-en-c.html



No hay comentarios:

Publicar un comentario

C++ El apuntador This

El apuntador This En C++, cada objeto tiene acceso a su propia dirección a través de un puntero o apuntador denominado This. Lo...