Recursividad

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

Temas:

Semántica de variables y parámetros

Cuando se declara una variable como la siguiente:

    int n= 123;
podemos distinguir 3 conceptos: la variable, el identificador y el valor. Estos conceptos se visualizan mejor en la siguiente figura.

A continuación presentaremos algunas nociones importantes para comprender el concepto de recursividad.

Tiempo de vida de una variable:

El tiempo de vida se refiere al intervalo de tiempo que trascurre desde que se crea la variable hasta que se destruye. En Java, una variable se crea en el momento que se ejecuta su declaración y se destruye cuando finaliza el bloque de instrucciones en donde fue declarada. Por ejemplo:

    if ( ... ) {
      println( ... );
      int n= 123; // (A)
      ...
      n= ...; // (B)
      ...
    } // (C)
La variable n se crea en el momento de ejecutar la instrucción (A) y se destruye al encontrar el final del bloque de instrucciones en (C). En (B) se asigna un nuevo valor a la variable n, que ya existía.

Un mismo identificador se puede usar para nombrar varias variables distintas. Por ejemplo en el siguiente código:

    {
      int x= a+b;
      ... x ...
    }
    {
      int x= fun(a,b);
      ... x ...
    }
En el código anterior, la variable x del primer bloque no tiene ninguna relación con la variable x del segundo bloque. Se trata de dos variables que se identifican por el mismo nombre. Se podría renombrar la variable x del segundo bloque por y, sin cambiar en nada la ejecución del programa.

Incluso, la declaración de una variable puede aparecer una sola vez en el programa, pero aún así servir para identificar varias variables durante la ejecución del programa. Esto se aprecia en el siguiente ciclo:

    while ( ... ) {
      ...
      double x= 3.14; // (A)
      ...
      x= ...;
      ...
    } // (C)
En cada iteración, en (A) se crea una nueva variable x que se destruye en (C), pero todas se llaman con el mismo nombre (x).

Los parámetros de una función también son variables. Se crean en el momento que la función es invocada y se destruyen al finalizar la ejecución de la función. Por ejemplo, la siguiente función calcula el máximo común divisor:

    int mcd(int x, int y) {
      while (x!=y) {
        if (x>y)
          x= x-y;
        else
          y= y-x;
      }
      return x;
    }
Considere las siguientes invocaciones de esta función (por ejemplo en el procedimiento run):

    int a= 15;
    println( mcd(a, 21) );
    println( mcd(25, a) );
En cada invocación de mcd se crean nuevas variables x e y (sus parámetros) que se inicializan con los valores de los argumentos. Esto se visualiza mejor en la siguiente figura:

Observe en la figura que durante la ejecución del programa se crean dos variables con nombre x. Esto no constituye ninguna confusión en el momento de accesar la variable x, puesto que ambas variables tienen tiempo de vista disjuntos.

Observe también, que la función mcd modifica los parámetros x e y sin modificar el valor de la variable a en ninguna de las invocaciones. Una función no puede producir efectos laterales sobre las variables que se especifiquen como argumentos durante la invocación. Sin embargo, una función sí puede producir efectos laterales sobre los objetos que se pasen como argumentos en la invocación (como por ejemplo un arreglo).

Existen casos que sí existen varias variables con el mismo nombre en un mismo instante. Por ejemplo, consideremos el siguiente programa:

    int x= 105;
    println( mcd(210, x) );
Mientras se ejecuta la función mcd existen dos variables x. ¿Qué variable se modifica al ejecutar x= x-y;? Intuitivamente la respuesta es ``la variable de mcd''. Esto es cierto, pero para aclarar mejor este concepto definiremos el alcance de una variable.

Alcance de una variable:

El alcance de una variable es el conjunto de instrucciones en la que esa variable es visible por medio de su identificador. En Java, el alcance de una variables está delimitado por la primera instrucción que sigue a su declaración en el programa, hasta el final del bloque en donde fue declarada. Por ejemplo en:

    void run() {
      int x= 105; // (A)
      println( mcd(210, x) );
    } // (B)
La variable x es conocida desde (A) hasta (B). En particular esa variable no es conocida en la definición de mcd, ni en la definición de ningún otro procedimiento porque esas definiciones no se encuentran entre (A) y (B).

Es importante entender la diferencia entre alcance y tiempo de vida de una variable. En el ejemplo anterior, mientras se ejecuta la función mcd, la variable x del procedimiento run continúa existiendo, a pesar de que no es visible desde mcd. Si una variable no es visible, no necesariamente ha sido destruida. En cambio, si una variable fue destruida, esa variable no es visible.

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:

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:

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:

    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).