La recursividad o recursión permite definir un objeto en términos de sí mismo. Ésta es una técnica en el cual un subprograma, en vez de llamar a otro subprograma, se llama a sí mismo.
Todo aquello que pueda resolverse con una estructura repetitiva se puede plantear con una recursión.
Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema a resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad. Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.
Recursividad directa vs indirecta
Cuando en una subrutina hay llamadas a ella misma se habla de recursividad directa, en contraposición, cuando se tienen varias subrutinas y éstas se llaman unas a otras formando ciclos se dice que la recursión es indirecta.
Directa:
Subrutina_A → Subrutina_A → Subrutina_A
Indirecta:
Subrutina_A → Subrutina_B → Subrutina_C → Subrutina_D → Subrutina_A
Definición de la Recursividad
Hay dos etapas en el proceso de definición recurrente:
- Identificar el estado Base o condición/es de salida del proceso recursivo, es decir la solución sin aplicar recurrencia.
- Encontrar una relación recurrente que exprese el modo de obtener un conjunto de valores genéricos representativos del proceso.
Características
- Se deben considerar dos componentes:
- Una o varias condiciones de salida
- Una o varias partes recursivas
- No debe generar una secuencia infinita de llamadas así mismo, dicho de otro modo ha de existir al menos un caso base.
- Siempre se deben detectar la/s condición/es de salida.
- Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).
Ejemplo: “Factorial de un Número”
El factorial de un número entero “n” se define como el producto de los números comprendidos entre 1 y n.
Examinaremos los elementos que permiten dar una solución recursiva. Antes que nada, puede reconocerse un gran número de casos distintos que se deben resolver. Es decir, quiere escribirse un programa para calcular 0!, 1!, 2! y así sucesivamente. Puede identificarse un caso “trivial” para el cual la solución no recursiva pueda obtenerse en forma directa. Es el caso de 0! y 1!, que se define como 1.
Por definición:
- 0! = 1
- 1! = 1
- 2! = 1 * 2 = 2 * 1
- 3! = 1 * 2 * 3 = 3 * 2 * 1
- 4! = 1 * 2 * 3 * 4 = 4 * 3 * 2 * 1
- n! = 1 * 2 * 3 * 4 * … * (n-1) * n = n * (n-1) * … * 4 * 3 * 2 * 1
El siguiente paso es encontrar un método para resolver un caso “complejo” en términos de uno más “simple”, lo cual permite la reducción de un problema complejo a uno más simple. La transformación del caso complejo al simple resultaría al final en el caso trivial. Esto significa que el caso complejo se define, en lo fundamental, en términos del más simple.
Al definir 4! = 1 * 2 * 3 * 4 estamos usando 4 * 3!, siendo 3! = 1 * 2 * 3; al igual que 3! = 3 * 2! y así sucesivamente hasta llegar al caso base. Con esto llegamos a definir n! en términos del factorial del número (n-1). Por lo cual encontramos que n! tiene condición de salida (0! y 1!) y recursividad de ser necesaria (para n > 1).
Algoritmo de la función:
int Factorial (int n) {
if (n < 0) {
//No hace nada, no existe el factorial de números negativos
} else if (n < 2) {
return 1 //Condición de salida o Base
} else {
return n * Factorial(n-1) //Llamada recursiva
}
}
Referencias:
“int” → Tipo entero (integer)
“//” → Comentario
Factorial de 4
¡Muchas gracias por llegar hasta acá! Esperamos que este post te haya servido y si fue así te invitamos a compartirlo en redes y dejarnos tu comentario para que podamos seguir compartiéndote todos nuestros conocimientos.