estoy llevando un curso en udemy sobre programación en C y voy por el tema de la recursividad. Resulta que se me está tornando un poco complejo, pero es principalmente por el concepto o su función como tal por lo cual no puedo entenderlo, y para "poner la cerecita sobre el pastel" me pusieron un ejemplo de recursividad con la serie Fibonacci.. Así que si alguien puede por favor explicarme detalladamente cual es su función y un concepto simple, estaría perfecto.
-
1Hola Luis, te damos la bienvenida a Stack Overflow en español (completa el recorrido de bienvenida para aprender más sobre el sitio y ganar tu primera medalla). Stack Overflow no es un sustituto de Google, deberías agregar algo más de información, qué es lo que has investigado, qué concepto concreto no comprendes (la recursividad puede ser un tema complejo), un ejemplo de lo que hayas intentado y los problemas/dificultades que te estás encontrando... Lee Cómo preguntar y cómo crear un ejemplo mínimo verificable para más información.– Alvaro Montoro ♦Commented el 23 jun. 2018 a las 2:53
2 respuestas
Una función recursiva en general es (no sólo en C) una función que se llama a si misma (recurre a sí misma).
La primer llamada pone el estado inicial luego la función se llama a si misma con los datos cambiados (que dependen del estado anterior), es importante poner una condición de salida o sino se ejecutará ad infinitum (en términos prácticos hasta que se le acaba la memoria).
En el caso de la Sucesión de Fibonacci
La sucesión comienza con los números 0 y 1 y a partir de estos, «cada término es la suma de los dos anteriores», es la relación de recurrencia que la define.
Para calcular el n-ésimo elemento de la sucesión de Fibonacci, el algoritmo mas simple suele ser la "versión recursiva descendente"
en C:
int fibo(int num)
{
if (num == 0) // <- condición de salida #1
{
return 0;
}
else if (num == 1) // <- otra condición de salida #2
{
return 1;
}
else
{
return(fibo(num - 1) + fibo(num - 2)); // <- llamada recursiva #3
}
}
ejemplo : averiguar el 8vo número Fibonacci
fibo(8)
num vale 8
por el return fibo(8) va a ser igual a (fibo(7)+fibo(6))
fibo(7)
num vale 7
por el return fibo(7) va a ser igual a (fibo(6)+fibo(5))
fibo(6)
num vale 6
por el return fibo(6) va a ser igual a (fibo(5)+fibo(4))
fibo(5)
num vale 5
por el return fibo(5) va a ser igual a (fibo(4)+fibo(3))
fibo(4)
num vale 4
por el return fibo(4) va a ser igual a (fibo(3)+fibo(2))
fibo(3)
num vale 3
por el return fibo(3) va a ser igual a (fibo(2)+fibo(1))
fibo(2)
num vale 2
por el return fibo(2) va a ser igual a (fibo(1)+fibo(0))
fibo(1)
num vale 1
por el return (condición de salida #2) va a ser igual a 1
fibo(0)
num vale 0
por el return (condición de salida #1) va a ser igual a 0
Ahora vemos la cadena de returns
fibo(0) = 0
fibo(1) = 1
fibo(2) = 1 + 0 = 1
fibo(3) = 1 + 1 = 2
fibo(4) = 2 + 1 = 3
fibo(5) = 3 + 2 = 5
fibo(6) = 5 + 3 = 8
fibo(7) = 8 + 5 = 13
y finalmente retorna al main con
fibo(8) = 13 + 8 = 21
Dando por supuesto que conoces la teoría de la recursividad (básicamente es una función que se llama a si misma), su utilidad es múltiple, pero generalmente se usa para recorrer múltiples caminos ( otra manera de decirlo, seria recorrer datos ordenados en forma de árbol, con ramas que forman un numero indefinido de ramas). Por ejemplo, para acceder a todas las posiciones de una matriz de dimensiones desconocidas y variables.
Te pongo un ejemplo en javascript (si, no es C, para que veas aquí el resultado, y si, no es Fibonacci porque creo que no refleja su utilidad "practica"), de una función para buscar un valor (el primero que encuentre) de una matriz de dimensiones variables.
var datos=[1,2,[3,4,5,[6,7],8],9];
function busca(valor,matriz){
var posicion=[];
for (var i=0; i<matriz.length ; i++){
if (!Array.isArray(matriz[i])) { // Si el valor NO es otra matriz.
if (matriz[i]==valor) {
posicion.push(i);
break;
}
} else { // Si el valor es otra matriz.
posicion=busca(valor,matriz[i]);
if (posicion.length>0) {
posicion.unshift(i);
break;
}
}
}
return posicion;
}
for (var i=1; i<=9 ; i++) document.write("Posicion de ",i,": ",busca(i,datos),"<br>");
Nota: He decidido no usar Fibonacci como ejemplo, porque he entendido que tienes problemas para comprender en que casos se usa, y siendo cierto que Fibonacci es un ejemplo típico y fácil de la mecánica de la recursividad, no muestra su utilidad "practica" o "realista" ya que el problema es resoluble perfectamente con un simple bucle.
Por ejemplo, un bucle que calcula los 10 primeros numeros:
var resultado=0;
var resultadoAnterior=0;
var temp=0;
for (var i=0; i<=10; i++){
if (i<2) resultado=i; //fibo(0)=0, fibo(1)=1
else {
temp=resultado;
resultado+=resultadoAnterior;
resultadoAnterior=temp;
}
document.write(resultado,",");
}
En cambio el ejemplo que he expuesto, solo se puede resolver recursivamente, por lo que creo que es un ejemplo mas practico y realista.