La recursión es el proceso (más precisamente en informática) por el cual una función se llama a sí misma.
Para usar la técnica de recursión, dividimos un problema mayor en sus subproblemas similares más pequeños y luego los llamamos recursivamente.
En cualquier función recursiva, el problema se resuelve dividiéndolo en dos componentes: el caso base y el caso recursivo.
- ¿Cómo puede 100 determinar el número de comparaciones en 'Búsqueda binaria'?
- ¿Hay un libro que enseñe algoritmos del nivel 0 a los algoritmos de codificación?
- Cómo construir robots enjambre
- ¿Por qué son buenos los algoritmos de código abierto?
- ¿Cuál es un ejemplo de un buen algoritmo que se puede usar para unir a diferentes usuarios dentro de un determinado radio en cualquier ubicación según sus preferencias?
El caso base brinda la solución directa del problema que conocemos. Da las condiciones en que las llamadas recursivas se detendrán.
El caso recursivo simplifica un problema mayor en una serie de subproblemas más simples y luego los llama.
Todas las iteraciones se pueden cambiar a recursiones y viceversa.
Un programa recursivo simple
// esta función calcula el factorial de un número positivo de forma recursiva
int factorial (int n)
{
if (n == 1) devuelve 1; // caso base, como sabemos que el factorial de 1 es 1
de lo contrario, devuelve n * factorial (n-1); // caso recursivo
}
Tratemos ahora de resolver el problema de la serie de Fibonacci.
Sabemos que en una serie de Fibonacci, cualquier término es igual a la suma de los dos términos anteriores.
Por lo tanto, [matemática] T_n = T_ (n-1) + T_ (n-2) [/ matemática] donde [matemática] T_n, T_ (n-1) [/ matemática] y [matemática] T_ (n-2) [/ math] son [math] nth [/ math] term, [math] (n-1) th [/ math] term y [math] (n-2) th [/ math] términos respectivamente.
También sabemos que los términos primero y segundo de la serie son 0 y 1 respectivamente.
Por lo tanto, [matemática] T_1 = 0 [/ matemática] y [matemática] T_2 = 1 [/ matemática]
Escribamos ahora la función para calcular el enésimo término de una serie de Fibonacci de forma recursiva.
int fibonacci (int n)
{
if (n <1) devuelve -1; //error
/ * Las siguientes dos líneas son los casos base * /
if (n == 1) devuelve 0; // primer término de la serie fibonacci
if (n == 2) devuelve 1; // segundo término de la serie fibonacci
/ * La siguiente línea es el caso recursivo * /
retorno fibonacci (n-1) + fibonacci (n-2);
}
Usando la función anterior, podemos generar la serie de Fibonacci. Para imprimir la serie de Fibonacci de forma recursiva, implemente el siguiente algoritmo.
nulo printFibonacciSeries (int n)
{
if (n> = 1) printFibonacciSeries (n-1);
impresión (fibonacci (n));
}
