Conceptos básicos de la programación: Recursividad
La recursividad, en el ámbito de la programación, puede definirse cómo la resolución de un problema en función del propio problema. Esto que, a primera vista, puede ser complejo de entender, es uno de los conceptos básicos que todo programador debe dominar si desea realizar algoritmos complejos.
El ejemplo básico que siempre se pone a la hora de explicar el uso de la recursividad en un algoritmo es el del cálculo del factorial de un numero entero positivo. Este ejemplo es el que voy a desgranar en esta primera entrada de Conceptos básicos de la programación.
Para ello lo primero que hay que explicar es que implica calcular el factorial de un número. Supongamos que queremos calcular el factorial de 5, que se denota como 5!. Esta operación se calcula como la multiplicación sucesiva de los números enteros del 1 al número del cual se desea calcular el factorial, es decir:
5! = 5 * 4 * 3 * 2 * 1
Como se intuye entonces se puede afirmar que 5! es el resultado de multiplicar el número 5 por el factorial de su inmediato antecesor, o lo que es lo mismo:
5! = 5 * 4!
Esto es generalizable para todo número entero salvo para el número 1, y se expresa de la siguiente manera:
N! = N * (N-1)! | N =/= 1
1! = 1
Por lo tanto, y retomando la definición que daba al inicio de esta entrada, el factorial es un problema que se puede resolver en función del propio problema.
También la “fórmula” que he apuntado antes nos da una pista sobre la condición más importante para resolver un problema de manera recursiva: Ha de existir un caso – que se llama base – en el cual la recursividad se detenga.
Desarrollando el ejemplo del cálculo de 5! se observa claramente cual es el caso base:
5! = 5 * 4!
Substituyendo el 4! por su fórmula se tiene:
5! = 5 * (4 * 3!)
Si aplicamos la substitución subsiguientemente:
5! = 5 * (4 * (3 * ( 2 * 1!) ) )
Como se sabe que – por definición – el factorial de 1 es igual a 1 se tiene que:
5! = 5 * 4 * 3 * 2 * 1
Que es precisamente el cálculo que buscábamos. Para conseguir esto en un algoritmo directamente programable tendríamos que seguir el siguiente pseudocódigo:
subrutina calcular_factorial parametro entero num
{
si num = 1
devolver 1;
sino
devolver num * llamar calcular_factorial num - 1;
}
Una vez visto el ejemplo más simple de recursividad conviene saber que existen dos tipos de la misma:
- Recursividad simple: Es aquella en la que la solución del problema depende una única vez del propio problema. El ejemplo anterior es un caso de recursividad simple.
- Recursividad múltiple o compuesta: Es aquella en la que la solución depende N veces del propio problema. El caso más básico de este tipo de recursividad es la solución recursiva a la sucesión de Fibonacci que se puede ver aquí
Espero que haya quedado más o menos claro el concepto de recursividad que he intentado explicar en esta entrada. Para cualquier duda/aclaración no dudéis en dejar vuestro comentario, intentaré contestar a la mayor brevedad posible.