RECURSIVIDAD

RECURSIVIDAD

Recursividad: Es una técnica de programación que consiste en subdividir un algoritmo en la respuesta final y la resolución del resto de los datos con el mismo algoritmo. Aunque no es muy elegante, también se puede decir que la recursividad consiste en implementar una solución que se llama a símisma. Sin embargo lo importante es tener claro que esto se utiliza para descomponer los datos de entrada del problema e implementarlos como subproblemas del mismo.

Implementación: Básicamente la implementación consta de un borde o condición de término y la implementación de la solución para el resto de los datos.

Pseudocódigo:

funcion recursiva (parámetros){
      si (borde) termina;
      si no recursiva (nuevos parámetros);
}

Ej: La función factorial se define como:

... ¿No se entiende?... ¡Qué vergüenza!

Ok. Lo explico menos engorrosamente:

En palabras, se expresa como: “El factorial de un número es el resultado de la multiplicación de dicho número con la multiplicación de todos sus antecesores naturales”.

Se supone que la función factorial es una función para números naturales, sin embargo por varias razones se llegó a la convención de que el factorial de cero es uno, por lo que podemos redefinir la función como:

En esta última expresión vemos cómo el problema se subdivide en forma recursiva.



Ahora vamos a implementarla en java.

public int factorial (int n){

      if (n==0) return 1;
      return n * factorial(n-1);
}

Este ejemplo es bastante sencillo, y puede que hasta poco útil, pero es un ejemplo pequeño para ir calentando motores con la implementación de algoritmos recursivos.

Nota: recordemos que una vez ejecutado un return ya no se siguen ejecutando las siguientes instrucciones.

Ejercicio propuesto: Hacer la traza de la función anterior para cualquier número mayor que 5 (sólo para que tenga una dificultad moderada).

Ejercicios Resueltos:

Implementar en Java los siguientes algoritmos en forma recursiva:

1.- Calcular la división entera: Se define división entera como “Contar las veces que se puede restar un número natural con otro hasta que el sustraendo sea mayor que el minuendo”.

Ejemplo práctico: División entera de 48 y 11:

En este caso el resultado es 4, es decir, 4 veces se pudo realizar la resta. No confundir con el 4 que aparece como resultado de la última resta ya que ese es el resto de la división.

Comprobación:

Ahora la implementación en Java:

public int divisionEntera (int a, int b){
      if (b > a) return 0;
      return divisionEntera(a – b,b)+1;
}

Ejercicio propuesto: Hacer la traza de la función anterior.

2.- Convertir un entero a binario: Para convertir un entero decimal a cualquier base, éste se divide con la base consecutivamente hasta que el divisor es cero; una vez terminada esta operación se deben concatenar todos los restos de las operaciones desde el último hasta el primero. Debido a esto la salida de nuestra función será un string.

Ejemplo práctico: Convertir a string binario el número 777.

Una vez terminadas las divisiones se concatenan los restos de atrás hacia adelante (o de abajo hacia arriba en este caso).

Resultado = “1100001001”

Implementación en Java:

public String binario (int n){
      if (n == 0) return “”;
      if (n%2 == 0) return binario(n/2)+”0”;
      return binario(n/2)+”1”;
}

















3.- Multiplicación rusa: Los rusos multiplican de una manera muy peculiar. Se ponen los múltiplos como cabeceras de dos columnas. Simultáneamente a uno de los números lo multiplican por 2 y al otro lo dividen por 2. Esto se repite hasta que el número que está siendo dividido llega a 1. Luego se toman los valores de la columna multiplicada y se suman sólo aquellos que en su contra parte tengan un número impar.

Implementación en Java:

public int rusa (int a, int b){
      if (b == 1) return a;
      if (b%2 == 0) return rusa(a*2,b/2);
      return a+rusa(a*2,b/2);
}