Se han estudiado diferentes métodos que se pueden implementar fácilmente, bien de modo recursivo, o bien de modo iterativo. En esta sección se comparan los dos enfoques y se examinan las razones por las que el programador puede elegir un enfoque u otro según la situación específica.
Tanto la iteración como la recursión se basan en una estructura de control: la iteración utiliza una estructura repetitiva mientras que la recursión utiliza una estructura de selección. Tanto la iteración como la recursión implican repetición: la iteración utiliza explícitamente una estructura repetitiva mientras que la recursión consigue la repetición mediante llamadas repetidas al método.
La iteración y la recursión implican cada una un test de terminación (condición de parada). La iteración termina cuando la condición del bucle no se cumple, mientras que la recursión termina cuando se reconoce un caso base o alcanza la condición de parada. La recursión tiene muchas desventajas. Se invoca repetidamente al mecanismo de llamadas a métodos y, en consecuencia, se necesita un tiempo suplementario para realizar cada llamada.
Esta característica puede resultar cara en tiempo de procesador y espacio de memoria. Cada llamada recursiva produce una nueva creación y copia de las variables de la función, esto consume más memoria e incrementa el tiempo de ejecución. Por el contrario, la iteración se produce dentro de un método, de modo que las operaciones suplementarias en la llamada al método y en la asignación de memoria adicional son omitidas.
Entonces, ¿Cuáles son las razones para elegir la recursión?. La razón fundamental es que existen numerosos problemas complejos que poseen naturaleza recursiva y, en consecuencia, son más fáciles de implementar con algoritmos de este tipo. Sin embargo, en condiciones críticas de tiempo y de memoria; es decir, cuando el consumo de tiempo y memoria sean decisivos o concluyentes para la resolución del problema, la solución a elegir debe ser, normalmente, la iterativa.
A tener en cuenta
Cualquier problema que se pueda resolver recursivamente tiene, al menos, una solución iterativa utilizando una pila. Un enfoque recursivo se elige, normalmente, con preferencia a un enfoque iterativo cuando resulta más natural para la resolución del problema y produce un programa más fácil de comprender y de depurar. Otra razón para elegir una solución recursiva es que una solución iterativa puede no ser clara ni evidente.
Consejo de programación
Se ha de evitar utilizar recursividad en situaciones de rendimiento crítico o exigencia de altas prestaciones en tiempo y en memoria, ya que las llamadas recursivas emplean tiempo y consumen memoria adicional. No es conveniente el uso de una llamada recursiva para sustituir un simple bucle.
Ejemplo
Dado un número natural n, obtener la suma de los dígitos de que consta. Presentar un algoritmo recursivo y otro recursivo.
El ejemplo ofrece una muestra clara de comparación entre la resolución de modo iterativo y de modo recursivo. Se asume que el número es natural y que, por tanto, no tiene signo. La suma de los dígitos se puede expresar:
suma = modulo(n,10) + suma(n/10) para n>10
suma = n para n<10, caso base
Para, por ejemplo: n = 259
suma = modulo(259,10) + suma(259/10) → 2 + 5 + 9 = 16
↓
suma = modulo(25,10) + suma(25/10) → 2 + 5 ↑
↓
suma = modulo(2,10) + suma(2/10) → 2 ↑
El caso base, el que se resuelve directamente, es n<10 y, a su vez, es la condición de parada.
Solución recursiva
public static int sumaRecursiva(int n){
if(n<10)
return n;
else
return (n%10)+sumaRecursiva(n/10);
}
Solución iterativa
La solución iterativa se construye con un bucle mientras, repitiendo la acumulación del resto de dividir n por 10 y actualizando n en el cociente. La condición de salida del bucle es que n sea igual a 0.
public static int sumaIterativa(int n){
int suma = 0, digito;
while(n!=0)
{
digito = n % 10;
suma = suma + digito;
n = n /10;
}
return suma;
}
Directrices en la toma de decisión iteración/recursión
- Considérese una solución recursiva sólo cuando una solución iterativa sencilla no sea posible.
- Utilícese una solución recursiva sólo cuando la ejecución y eficiencia de la memoria de la solución esté dentro de límites aceptables, considerando las limitaciones del sistema.
- Si son posibles las dos soluciones, iterativa y recursiva, la solución recursiva siempre requerirá más tiempo y espacio debido a las llamadas adicionales a los métodos.
- En ciertos problemas, la recursión conduce a soluciones que son mucho más fáciles de leer y de comprender que su alternativa iterativa. En estos casos, los beneficios obtenidos con la claridad de la solución suelen compensar el coste extra (en tiempo y memoria) de la ejecución de un programa recursivo.
Consejo de programación
Un método recursivo que tiene la llamada recursiva como última sentencia (recursión final) puede transformarse fácilmente en iterativa reemplazando la llamada mediante un bucle condicional que chequee el caso base.