Universidad Carlos III de Madrid

Si no existe un caso base para una función recursiva, las sucesivas llamadas a la misma se ejecutarían de manera indefinida y nunca se devolvería el control al invocarse por primera vez. El caso base de un método recursivo es aquel que lo resuelve de forma no recursiva de manera más o menos trivial. Es una condición "necesaria pero no suficiente" para resolver cualquier función recursiva. En el caso de la función de la serie armónica sería el caso de n=1 para lo cual la función devolvería 1. A pesar de ello, el método provoca una excepción de tipo StackOverflowError por lo que hace falta algo más para resolverlo.

La existencia de un caso base "no garantiza" que se resuelva una función recursiva. Para resolverlo, cada llamada a la función recursiva tiene que tender al caso base, es decir, tiene que acercarse hasta llegar al caso base. El siguiente método recursivo que permite calcular el factorial de un número sí que cumple con los dos requisitos que hemos mencionado para resolverlo:

public long factorial(int n) {
 if (n == 1) return 1;
 return n * factorial(n-1);
}					

Para convertirlo, hay que sustituir la última llamada por las asignaciones correspondientes para que los parámetros actuales tengan los valores con los que se hacía esta llamada. La versión iterativa del método se muestra a continuación:

		
public void torresHanoi(int n, char de, char to, char ch){
 char temp;
 while (n>1) {
  torresHanoi(n-1, de, ch, to);
  System.out.println("Mover "+n+" de "+de+"hacia "+to);
  n=n-1; temp= de; d= ch; ch= temp;
 }
 if (n==1)
 System.out.println("Mover 1 en"+de+"hacia "+to);
}

El origen de esta ineficiencia es que la recursividad calcula una y otra vez los mismos valores, porque no guarda memoria de haberlos calculado antes. Ejemplos de cálculos del número de invocaciones con el anterior método recursivo:

Para fib(5) se realizan 15 invocaciones al método.
Para fib(10) se realizan 177 invocaciones al método.
Para fib(20) se realizan 21891 invocaciones al método.
Para fib(25) se realizan 242785 invocaciones al método.
...

Mediante el uso de métodos recursivos "por la cola", que no guardan ningún resultado parcial, se utilizan los resultados ya obtenidos para pasarlos en la siguiente llamada y, por lo tanto, no se calculan varias veces. El método Fibonnaci lineal se muesta a continuación:

public static long fibo (int n,x,y){
 if (n<=1)
  return x+y;
 else
  return fibo(n-1,y,x+y);
 }
 public static long fib (int n) {
  return fibo(n,0,1);
}

Aunque un algoritmo iterativo pueda ser más complicado que uno recursivo, nos permite tener un control total sobre la ejecución del mismo. Además, la limitación del tamaño de la pila del sistema hace que no se pueda prever cuándo puede sobrepasarse en la ejecución del método. La versión iterativa del método Fibonacci se muestra a continuación.

long fib(int n){
 if (n < 3) {
  return 1;
 else{ 
  int x = 1, y = 1, count = 2; int fib;
  do{ 
    count++; 
    fib = y + x; 
    y = x;
    x = fib;
  } while (n != count);
  return fib; } }

La complejidad de un algoritmo crece de acuerdo al orden cuando el tamaño (n) se hace muy grande. Los órdenes de complejidad se clasifican de acuerdo a su orden creciente en distintos tipos.

O(1)		orden constante
O(log n) 		orden logarítmico
O(n)	 	orden lineal
O(n·log n) 	orden lineal logarítmico
O(n^c)	 	orden potencial
O(c^n),n>1 	orden exponencial
O(n!)	 	orden factorial
O(n^n)	 	orden potencial exponencial

El orden de complejidad es una medida asintótica para cuando n crece mucho, pero para tamaños de valores pequeños puede incluso variar el resultado esperado de aplicar un algoritmo con un orden determinado. Imagina que el tiempo de un algoritmo "f" es 100n y, por consiguiente, es de orden lineal O(n). Imagina otro algoritmo "g" que tarda n^2 y, por consiguiente, de orden cuadrático O(n^2). Asintóticamente, "f" es mejor algoritmo que "g", pero eso es cierto a partir de n>100. Si no vamos a tratar jamás problemas de tamaño mayor que 100, resulta mejor solución usar el algoritmo "g".

La importancia del orden de complejidad en el diseño o elección de algoritmos se pone de manifiesto en los valores de la siguiente tabla en la que se aprecia la evolución del incremento del tiempo de proceso al multiplicar por 2 el tamaño del conjunto de datos que manipula el algoritmo (de n=100 a n=200). Como regla general, se puede establecer que debe elegir y desear el algoritmo de menor orden de complejidad computacional.

T(n) 		n=100	n=200
----------------------------------
c·log n		1h	1,20 h
c·n		1h	2h
c·n·log n		1h	2,30 h
c·n^2		1h	4h
c·n^3		1h	8h
c·2^n		1h	1,2·10^30 h

Estos algoritmos resuelven un problema mediante una búsqueda sistemática, aplicando la fuerza bruta hasta encontrar la solución o encontrar que no existe solución. Dividen la búsqueda en varias búsquedas parciales que, a su vez, suelen incluir más subtareas, por lo que suelen resolverse de manera recursiva:

procedimiento ensayar (paso : TipoPaso){
  repetir
    seleccionar_candidato
    if aceptable then { 
      anotar_candidato
      if solucion_incompleta then {      
        ensayar(paso_siguiente)
        if no acertado then borrar_candidato}      
      else {
        anotar_solucion
        acertado = cierto; }}
  hasta que (acertado = cierto) o (candidatos_agotados)}

Método de las tres preguntas: • La pregunta Caso-Base: ¿Existe una salida no recursiva o caso base del subalgoritmo? Además, ¿el subalgoritmo funciona correctamente para ella? • La pregunta Más-pequeño: ¿Cada llamada recursiva se refiere a un caso más pequeño del problema original? • La pregunta Caso-General: ¿es correcta la solución en aquellos casos no base?

Esta técnica consiste en descomponer el problema original en varios sub-problemas más sencillos, para luego resolver éstos mediante un cálculo sencillo. Un ejemplo es la ordenación rápida, "quicksort", utilizada para ordenar arrays. En ella, se divide el array en dos sub-arrays, para luego resolver cada uno por separado y unirlos. El tiempo necesario para ordenarlo es de orden cuadrático O(n^2). Si aplicamos recursivamente el mismo proceso, el tiempo se reduce hasta ser de orden logarítmico O(log n).

funcion divide_y_venceras(problema) { 
  si el problema es trivial entonces 
    resolver el problema;
  si no es trivial {
    descomponer el problema en n subproblemas 
           más pequeños;
    para i=1 hasta n hacer
      divide_y_venceras(subproblema_k);
    combinar las n soluciones;} }

Esta técnica se utiliza en algunos casos en los que la recursión no es eficiente porque realiza cálculos redundantes. Es un método ascendente generalmente que resuelve los problemas más pequeños almacenando los valores en una tabla para combinarlos y resolver los más grandes. Para la serie de Fibonacci se puede obtener un algoritmo de orden n O(n) con esta técnica:

FUNC Fibonacci (n: NATURAL): NATURAL {
 tabla: ARRAY [0..n] DE NATURAL
 i: NATURAL
 if n <= 1 then 
  devolver 1
 else {
  tabla[0] = 1
  tabla[1] = 1
  for i = 2 HASTA n HACER {
   tabla[i] = tabla[i-1] + tabla[i-2] }  
  devolver tabla[n]}}

El bucle exterior se realiza n veces, mientras que el interior se realiza 1, 2, 3, ... n veces respectivamente. En total:

1 + 2 + 3 + ... + N = N*(1+N)/2  -> O(n^2)