La recursividad es aquella propiedad que posee un método por la cual puede llamarse a si mismo. Aunque se puede utilizar la recursividad como una alternativa a la iteración, una solución recursiva es, normalmente, menos eficiente en términos de tiempo de computadora que una solución iterativa, debido a las operaciones auxiliares que llevan consigo las invocaciones suplementarias a los métodos.
Los programas examinados hasta ahora, generalmente estructurados, se componen de una serie de métodos que se llaman de modo disciplinado. En algunos problemas es útil disponer de métodos que se llamen a sí mismos. Un método recursivo es aquel que se llama a sí mismo, bien directamente o bien indirectamente, a través de otro método. La recursividad es un tópico importante examinado frecuentemente en cursos que estudian la resolución de algoritmos y en cursos relativos a estructuras de datos.
Sin embargo, un método que tiene sentencias entre las que se encuentra al menos una que llama al propio método se dice que es recursivo. Así, supongamos que se dispone de dos métodos metodo1 y metodo2. La organización de una aplicación no recursiva adoptaría una forma similar a esta:
metodo1(. . .){
. . .
}
metodo2(. . .){
. . .
metodo1(); // llamada al metodo1
. . .
}
Con una organización recursiva, se tendría esta situación:
metodo1(. . .){
. . .
metodo1();
. . .
}
Ejemplo
Algoritmo recursivo de la función matemática que suma los N primero números enteros positivos.
Como punto de partida, se puede afirmar que para n = 1 se tiene que la suma S(1) = 1. Para n = 2 se puede escribir S(2) = S(1) + 2; en general, y aplicando la inducción matemática, se tiene:
S(N) = S(N-1) + N
Se está definiendo la función suma S() respecto de sí misma, eso sí, siempre para un caso más pequeño. S(2) respecto a S(1), S(3) respecto a S(2) y, en general S(N) respecto a S(N-1).
El algoritmo que determina la suma de modo recursivo ha de tener presente una condición de salida o una condición de parada. Así, en el caso del cálculo de S(6); la definición es S(6) = 6 + S(5), a su vez S(5) es 5 + S(4), este proceso continúa hasta S(1) = 1 por definición. En matemáticas la definición de una función en términos de sí misma se denomina definición inductiva y, de forma natural, conduce a una implementación recursiva. El caso base S(1) = 1 es esencial dado que se detiene, potencialmente, una cadena de llamadas recursivas. Este caso base o condición de salida debe fijarse en cada solución recursiva. La implementación del algoritmo es:
int sumaEnteros(int n){
if(n==1) // caso base
return 1;
else
return n+sumaEnteros(n-1);
}
A tener en cuenta
La formulación recursiva de una función matemática puede ser muy ineficiente sobre todo si se repiten cálculos realizados anteriormente. En estos casos el algoritmo iterativo, aunque no sea tan evidente, es notablemente más eficiente.
Métodos recursivos
Un método recursivo es un método que se invoca a sí mismo de forma directa o indirecta. En recursión directa, el código del método f() contiene una sentencia que invoca a f(), mientras que en recursión indirecta, el método f() invoca a un método g() que a su vez invoca al método p(), y así sucesivamente hasta que se invoca de nuevo al método f().
Un requisito para que un algoritmo recursivo sea correcto es que no genere una secuencia infinita de llamadas sobre sí mismo. Cualquier algoritmo que genere una secuencia de este tipo no puede terminar nunca. En consecuencia la definición recursiva debe incluir una condición de salida, que se denomina componente base, en el que f(N) se defina directamente (es decir, no recursivamente) para uno o más valores de N.
En definitiva, debe existir una «forma de salir» de la secuencia de llamadas recursivas. Así, en el algoritmo que calcula la suma de los N primeros números enteros:
la condición de salida o componente base es S(N) = 1 para N = 1. Un método recursivo correcto debe incluir un componente base o condición de salida ya que, en caso contrario se produce una recursión infinita.
A tener en cuenta
Un método es recursivo si se llama a sí mismo, directamente o bien indirectamente a través de otro método. Es necesario contemplar un caso base que determina la salida de las llamadas recursivas.
Ejemplo
Hacer un método recursivo que calcule el factorial de un número y un programa que pida un número entero y reportar su factorial.
La componente base del método recursivo que calcula el factorial es que n = 0 o incluso n = 1, ya que en ambos caso el factorial es 1. El problema se resuelve recordando la definición expuesta anteriormente del factorial:
n! = 1 si n = 0 o n = 1 (componente o caso base)
n! = n(n-1) si n>1
En la implementación no se realiza tratamiento de error, que puede darse en el caso de calcular el factorial de un número negativo.
import java.io.IOException;
import java.util.Scanner;
public class FactorialRecursivo {
public static int Factorial(int n){
if(n<=1)
return 1;
else
return n*Factorial(n-1);
}
public static void main(String[] args) throws IOException {
Scanner entrada = new Scanner(System.in);
int numero;
do{
System.out.print(«Ingresar numero: «);
numero = entrada.nextInt();
}while(numero<0);
System.out.println(«\t» +numero+ «!: » + Factorial(numero));
}
}
Recursividad indirecta
La recursividad indirecta se produce cuando un método llama a otro, que eventualmente terminará llamando de nuevo al primer método.
Ejemplo
Mostrar por pantalla el alfabeto, utilizando recursión indirecta.
El método main() llama a metodoA() con el argumento ‘Z’ (la última letra del alfabeto). Este examina su parámetro c, si c está en orden alfabético después que ‘A’, llama a metodoB(), que inmediatamente invoca a metodoA() pasándole un parámetro predecesor de c. Esta acción hace que metodoA() vuelva a examinar c, y nuevamente llame a metodoB(). Las llamadas continúan hasta que c sea igual a ‘A’. En este momento, la recursión termina ejecutando System.out.println() veintiséis veces y visualiza el alfabeto, carácter a carácter.
public class AlfabetoRecursivo {
public static void metodoA(char c){
if(c>’A’)
metodoB(c);
System.out.println(c);
}
public static void metodoB(char c){
metodoA(––c);
}
public static void main(String[] args) {
System.out.println();
metodoA(‘Z’);
System.out.println();
}
}