Computación I

Lunes 7 de Junio

Recursividad

Objetivos: Explicar qué son las funciones o procedimientos recursivos.

Temas:

Funciones recursivas.
Patrón recursivo.

Funciones Recursivas

Motivación: plantee una estrategia para calcular 3 elevado a 8 realizando sólo 3 multiplicaciones. ¿Cuántas multiplicaciones necesitaría para calcular 3.14 elevado a 16? ¿Y 3.14 elevado a 9?

El siguiente programa calcula la función potencia:

    double potencia(double x, int n) {
      double p= 1.0;
      int i= 1;
      while (i<=n) {
        p= p*x;
        i= i+1;
      }
      return p;
    }

¿Cuantas multiplicaciones realiza esta función cuando se invoca potencia(3.0, 8)? El siguiente programa calcula recursivamente la misma función:

    double potencia2(double x, int n) {
      if (n==0)
        return 1.0;
      else
        return x * potencia2(x, n-1);
    }

Para entender como funciona esta función, veamos cómo se calcula potencia(5.0,2):

    potencia(5.0,3)             -> 125.0
       |
    5.0*potencia(5.0,2)         -> 125.0
            |
        5.0*potencia(5.0,1)     -> 25.0
                |
            5.0*potencia(5.0,0) -> 5.0
                    |
                   1.0

Una función es recursiva cuando se invoca a sí misma. Típicamente posee:

Una condición de salida no recursiva (el caso base).
Llamadas recursivas (a sí misma) que reducen el tamaño del problema (convergen al caso base).

Las llamadas recursivas van quedando pendientes hasta llegar al caso base. Al llegar a la condición de salida (el caso base) se desencadena el cálculo de los resultados pendientes.

¿Cuantas multiplicaciones realiza esta función cuando se invoca potencia2(3.0, 8)? Se puede deducir que potencia2 realiza el mismo número de multiplicaciones que la versión previa.

La siguiente estrategia permite reducir drásticamente el número de multiplicaciones:

x elevado a n es:

1.0 si n es 0
(x elevado a n/2) * idem si n es par
x * (x elevado a (n-1)/2) * idem si n es impar

Esta estrategia se puede expresar mediante la siguiente función recursiva:

    double potencia3(double x, int n) {
      if (n==0)
        return 1.0;
      else if (n%2==0) {
        double p= potencia(x, n/2);
        return p*p;
      }
      else {
        double p= potencia(x, (n-1)/2);
        return x*p*p;
      }
    }

Ejercicio 1: función recursiva que recibe un string como argumento y lo entrega invertido.

Ejemplo: inverso("hola") -> "aloh".

Solución:

Caso base: el string vacío.
```
    inverso("") -> "".
```
Caso recursivo: el string tiene al menos un string.
```
    inverso(s) -> inverso(substring(s, 1, length(s)-1))+ substring(s,0,1)
```
Esto se puede ver más claramente en la siguiente figura:

    String inverso(String s) {
      if (compare(s,"")==0)
        return "";
      else
        return inverso(substring(s, 1, length(s)-1)) + substring(s, 0, 1);

La cadena de llamadas recursivas para invertir "hola" se aprecia en la siguiente figura:

Ejercicio 2: procedimiento recursivo que despliega un número entero en binario.

Ejemplo: printBin(13) despliega 1101

    13 / 2 --> 6 / 2 --> 3 / 2 --> 1 / 2 --> 0
     1         0         1         1

Solución incorrecta:

    void printBin(int n) {
      while (n>0) {
        print(n%2);
        n= n/2;
      }
    }

Esta solución es incorrecta porque printBin(13) despliega 1011.

Solución correcta:

    (0) void printBin(int n) {
    (1)   if (n==0)
    (2)     return; // retorno anticipado de un procedimiento
          else {
    (3)     printBin(n/2);
    (4)     print(n%2);
          }
        }

(Cuando se desea retornar anticipadamente en un procedimiento, basta escribir return, sin especificar una expresión para el valor retornado.)

En cada invocación recursiva de printBin se crea una nueva variable n para almacenar el parámetro que recibe printBin. Esta variable será visible sólo en esa invocación. Si se invoca recursivamente printBin, esa invocación usará su propio variable n.

Ejecución paso a paso de printBin(13):

    (0) n= 13
    (1) falso
    (3) printBin(6) ->
         (0) n= 6
         (1) falso
         (3) printBin(3) ->
              (0) n= 3
              (1) falso
              (3) printBin(1) ->
                   (0) n= 1
                   (1) falso
                   (3) printBin(0) ->
                        (0) n= 0
                        (1) verdadero
                        (2) return
                       <-
                   (4) print(1%2)
                  <-
              (4) print(3%2)
             <-
         (4) print(6%2)
        <-
    (4) print(13%2)

En general, las variables y parámetros declarados en un procedimiento (o función) son independientes para cada una de las invocaciones recursivas de ese procedimiento (o función).