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
