Recursion

Recursion

Como Funciona la Recursion

Como Funcionan las Llamadas a una Funcion

Si tenemos un programa como el siguiente:

void
fun1 (int n)
{
  /* instruccion */
  /* instruccion */
  /* instruccion */
}

int
main (void)
{
  /* instruccion */
  /* instruccion */
  fun1 (x);
  /* instruccion */
  /* instruccion */
}

Cuando se ejecuta main, se van a ejecutar las instrucciones en orden (una despues de la otra), cuando llegue a la llamada de fun1, se van a ejecutar sus tres instrucciones, y el control del programa va a volver a main donde se van a ejecutar las dos instrucciones restantes (a menos que haya alguna otra operacion en esa linea, ya que se realizaria antes de pasar a la siguiente.)

A lo que se refiere con otra operacion, es por ejemplo si tenemos:

int a = fun1 (x) * 2;

La multiplicacion se va a realizar, una vez la ejecucion de fun1 haya terminado.

Recursion

Una funcion recursiva, es una funcion que se llama a si misma:

void
fun1 (/* parametros */)
{
  if (/* condicion base */)
    {
      fun1 (parametro);
    }
}

Algo importante sobre la recursion, es que siempre debe haber una condicion base que termine las llamadas recursivas, o se llamaria a si misma de forma infinita. Por eso, debe haber una condicion que haga que pare las llamadas recursivas.

Recursion tiene dos fases:

1. Calling phase: cuando la funcion se llama a si misma.
2. Returning phase: Cuando los resultados son pasados hacia arriba.

• Ejemplo 1

  void
  imprimir (int n)
  {
    if (n < 0)
      return;
  
    printf ("%d ", n);
    imprimir (n - 1);
  }
  

• Trazo 1 ATTACH

  

  Por eso tenemos como salida (3, 2, 1, 0).

• Ejemplo 2

  void
  imprimir2 (int n)
  {
    if (n < 0)
      return;
  
    imprimir2 (n - 1);
    printf ("%d ", n);
  }
  

• Trazo 2 ATTACH

  

  Por eso su salida es ahora (0, 1, 2, 3). Las impresiones se estan haciendo una vez terminen las llamadas recursivas, es decir, la ultima llamada va a ser la primera impresion.

Complejidad de Espacio: Recursion

La complejidad de espacio de la recursion es \(O(n)\), ya que por cada llamada se esta creando un record de activacion en el stack \(n + 1\) veces (mas la llamada donde no se cumple la condicion base.)

Complejidad de Tiempo: Recursion

La complejidad de tiempo de la recursion es \(O(n)\) ya que las unidades de tiempo que tomara finalizar una llamada recursiva, depende del numero de veces \(n\) que tenga que ser llamada.

Variables Globales y Estaticas en Recursion

Como las variables globales y estaticas estan almacenadas en una seccion especial de .code, no se creara por cada llamada recursiva, sino que su valor se mantendra.

Ejemplo

int
func (int n)
{
  static int x = 0;
  if (n <= 0)
    return 0;

  x++;
  return func (n - 1) + x;
}

Trazo ATTACH

Tail Recursion (Recursividad de Cola)

Una funcion con Recursividad de Cola, es aquella que se llama a si misma, y este llamado es la ultima instruccion de la funcion. Por ejemplo:

void
func (int n)
{
  if (n <= 0)
    return;

  printf ("%d ", n);
  func (n - 1);
}

Si la llamada recursiva fuese de la siguiente forma, no seria recursiva de cola:

func (n - 1) + n;

Porque aun tiene pendiente agregar n al resultado de la llamada recursiva.

Recursividad de Cola vs Bucles

Todas las funciones recursivas pueden ser escritas con bucles, y vice-versa. Convertir las funciones con recursividad de cola a bucles es mas facil:

void
fun_rec (int n)
{
  if (n <= 0)
    return;

  printf ("%d ", n);
  fun_rec (n - 1);
}

void
fun_buc (int n)
{
  while (n > 0)
    {
      printf ("%d ", n);
      n--;
    }
}

La complejidad de tiempo de ambas es de \(O(n)\).

La complejidad de espacio de la funcion recursiva es \(O(n)\) y la complejidad de espacio de la funcion con bucle es \(O(1)\).

Por eso, si se va a escribir una funcion con recursividad de cola, es mejor reescribirla como un bucle debido a la complejidad de espacio. Incluso, algunos compiladores detectan estas funciones, y las convierten a bucles como optimizacion.

Head Recursion (Recursion de Cabeza)

Cuando una funcion se llama a si misma, como primera instruccion de la funcion, decimos que es recursiva de cabeza:

void
func (int n)
{
  if (n <= 0)
    return;

  func (n - 1);
  printf ("%d ", n);
}

Si se debe realizar alguna operacion antes de la llamada recursiva, entonces no es una funcion con recursividad de cabeza. Dado este caso, la funcion seria unicamente recursiva, no se le daria ningun nombre especial.

Recursividad de Cabeza vs Bucles

Convertir una funcion de recursividad de cabeza a bucles es mas complicado que las funciones recursivas de cola. Si queremos que la salida del programa con bucles sea la misma a la del ultimo ejemplo recursivo (1, 2, 3), tendriamos la siguiente funcion:

void
func_rec (int n)
{
  if (n <= 0)
    return;

  func_rec (n - 1);
  printf ("%d ", n);
}

void
func_buc (int n)
{
  int i = 1;
  while (i <= n)
    {
      printf ("%d ", i);
      i++;
    }
}

Tree Recursion (Recursion de Arbol)

En la recursion tenemos dos posibilidades de hacer una llamada recursiva: de forma lineal, o por la recursion de arbol.

Recursion Lineal

Llamamos recursion lineal, a la funcion que se llama a si misma una unica vez:

void
fun (int n)
{
  if (n <= 0)
    return;

  /* instruccion */
  /* instruccion */
  fun (n - 1);
  /* instruccion */
}

Recursion de Arbol

Llamamos recursion de arbol, a la funcion que se llama a si misma mas de una vez:

void
fun (int n)
{
  if (n <= 0)
    return;

  /* instruccion */
  /* instruccion */
  fun (n - 1);
  /* instruccion */
  fun (n - 1);
  /* instruccion */
  /* instruccion */
}

Ahi la funcion fun esta siendo llamada en 2 ocasiones.

• Ejemplo

  void
  fun (int n)
  {
    if (n <= 0)
      return;
  
    printf ("%d ", n);
    fun (n - 1);
    fun (n - 1);
  }
  

• Trazo ATTACH

  

• Complejidad

  La complejidad de tiempo es \(O(2^n)\) y la complejidad de espacio es \(O(n)\).

Recursion Indirecta ATTACH

En la recursion indirecta, supongamos que tenemos 3 funciones: A, B y C:

En este ejemplo, A llama a B, B llama a C y C llama de nuevo a A.

Por ejemplo:

void A(int n);

void
B (int n)
{
  if (/* cond */)
    return;

  A (n - 1);
}

void
A (int n)
{
  if (/* cond */)
    return;

  B (n - 1);
}

Ejemplo

void fun2 (int n);

void
fun1 (int n)
{
  if (n <= 0)
    return;

  printf ("%d ", n);
  fun2 (n - 1);
}

void
fun2 (int n)
{
  if (n <= 1)
    return;

  printf ("%d ", n);
  fun1 (n / 2);
}

Trazo ATTACH

Recursion Anidada

En la recursion anidada, una llamada recursiva va a tomar otra llamada recursiva como parametro. Por ejemplo:

int
func (int n)
{
  if (/* condicion */)
    return;

  /* instruccion */
  /* instruccion */
  func (func (n - 1));
}

Ejemplo

int
func (int n)
{
  if (n > 100)
    return n - 10;
  return func (func (n + 11));
}

Trazo ATTACH

Ejemplos de Recursion

Suma de \(N\) Numeros Naturales Usando Recursion

Lo que queremos encontrar es \(1 + 2 + 3 + \cdots + n\).

Nosotros podemos definir esa funcion como:

\(\text{sum}(n) = 1 + 2 + 3 + \cdots + (n - 1) + n\)

Y recursivamente la podemos definir como:

\(\text{sum}(n) = \text{sum}(n - 1) + n\)

Y mas a fondo la podemos definir como:

\begin{equation} \text{sum}(n) = \begin{cases} 0 &\quad n = 0 \\ \text{sum}(n - 1) + n &\quad n > 0 \\ \end{cases} \end{equation}

• Funcion en C

  Desde que tengamos una definicion recursiva, facilmente podemos escribirlo en cualquier lenguaje que soporte recursion:

  int
  suma (int n)
  {
    if (n == 0)
      return 0;
    return suma (n - 1) + n;
  }
  

  Esta funcion tiene una complejidad de tiempo y de espacio \(O(n)\).

  Aunque para lograr lo mismo podemos utilizar la formula con complejidad de espacio y de tiempo \(O(1)\):

  \(\frac{n (n + 1)}{2}}\)

  Por lo que no es necesario utilizar la funcion recursiva.

  Tambien se puede hacer con un bucle con complejidad de tiempo \(O(n)\) y de espacio \(O(1)\):

  int
  suma (int n)
  {
    int s = 0;
    for (int i = 1; i <= n; i++)
      s += i;
    return s;
  }
  

• Trazo ATTACH

  

Factorial Usando Recursion

Un factorial (denotado por “!”) es definido como:

\(n! = 1 \times 2 \times 3 \times \cdots \times (n - 1) \times n\)

Entonces el factorial de 5:

\(5! = 1 \times 2 \times 3 \times 4 \times 5 = 120\)

Es importante tener en cuenta que \(0! = 1, 1! = 1\). Entonces, podemos definir esta funcion recursivamente como:

\begin{equation} \text{fact}(n) = \begin{cases} 1 &\quad n = 0\\ \text{fact}(n - 1) \times n &\quad n>0 \end{cases} \end{equation}

• Funcion en C

  La funcion que definimos anteriormente, la podemos escribir en codigo como:

  int
  fact (int n)
  {
    if (n == 0)
      return 1;
    return fact(n - 1) * n;
  }
  

  Escribir funciones recursivas es bastante sencillo una vez hayamos definido una formula.

  Similar a la suma de \(N\) numeros naturales, esta tiene una complejidad de tiempo y de espacio \(O(n)\) y puede ser escrita de forma iterativa para tener una complejidad de tiempo \(O(n)\) y de espacio \(O(1)\):

  int
  fact (int n)
  {
    int fac = 1;
    for (int i = 1; i <= n; i++)
      {
        fac *= i;
      }
    return fac;
  }
  

Funcion Exponencial \(m^n\) Usando Recursion

Nosotros podemos definir la funcion exponencial como:

\(m^n = m \times m \times m \times m \times \cdots \times \text{n veces}\)

Y la podemos definir recursivamente como:

\begin{equation} \text{exp}(m, n) = \begin{cases} 1 &\quad n = 0 \\ \text{exp}(m, n - 1) \times m &\quad n > 0 \end{cases} \end{equation}

• Funcion en C

  La funcion anteriormente definida la podemos escribir en C como:

  int
  exp (int m, int n)
  {
    if (n == 0)
      return 1;
    return exp(m, n - 1) * m;
  }
  

• Optimizaciones

  Esta funcion, esta realizando muchas multiplicaciones cuando podria ser simplificada, por ejemplo:

  \(2^8 = (2^2)^4 = (2 \times 2)^4\)

  Ahi pasaremos de usar 8 multiplicaciones a hacer 4 multiplicaciones.

  \(2^9 = 2 \times (2 \times 2)^4\)

  Si la potencia es un numero par podemos dividirla entre dos, si es impar tenemos que realizar una multiplicacion de mas. La nueva funcion quedaria como:

  int
  exp (int m, int n)
  {
    if (n == 0)
      return 1;
  
    /* si el exponente es par */
    if (n % 2 == 0)
      return exp (m * m, n / 2);
  
    /* restamos 1 para que el expontente sea par */
    return m * exp (m * m, (n - 1) / 2);
  }
  

• Trazo ATTACH

  Con la funcion exp original, hacer exp (2, 9) nos tomaria 9 multiplicaciones.

  

  En este trazado nos toma 6 multiplicaciones, en lugar de las 9 que nos tomaria con la otra funcion.

Sucesion de Fibonacci

La serie de fibonacci es la siguiente:

\(\text{0 1 1 2 3 5 8 13}\cdots\)

Cada uno de los terminos es obtenido con la suma de los dos terminos anteriores. Por ejemplo: \(1 + 1 = 2\), \(2 + 3 = 5\), \(5 + 8 = 13\), etc.

Los terminos iniciales son 0 y 1, mientras que los demas terminos son obtenidos con la suma de los dos terminos anteriores.

Matematicamente lo podemos definir como:

\begin{equation} \text{fib}(n) = \begin{cases} 0 &\quad n =0 \\ 1 &\quad n = 1\\ \text{fib}(n - 2) + \text{fib}(n - 1) &\quad n > 1 \end{cases} \end{equation}

• Funcion en C

  Para obtener el \(n\) termino de la sucesion de fibonacci, podemos usar nuestra definicion recursiva:

  int
  fib (int n)
  {
    if (n <= 1)
      return n; /* n = 0 || n = 1 */
    return fib (n - 2) + fib (n - 1);
  }
  

  La complejidad de tiempo de esta funcion es \(O(2^n)\).

• Funcion Iterativa

  Si queremos escribir esa funcion de forma iterativa, lo podemos hacer de la siguiente manera:

  int
  fib (int n)
  {
    int t0 = 0, t1 = 1, sum = 0;        /* termino 0, termino 1, suma */
    if (n <= 1)
      return n; /* n == 0 devuelva 0, n == 1 devuelva 1 */
  
    for (int i = 2; i <= n; i++)
      {
        sum = t0 + t1;
        t0 = t1;
        t1 = sum;
      }
  
    return sum;
  }
  

  Esta funcion iterative tiene una complejidad de espacio \(O(1)\) y de tiempo \(O(n)\).

• Trazo ATTACH

  Para fib(5) tendriamos:

  

• Optimizacion ATTACH

  Si revisamos el trazo, la funcion \(\text{fib}(3)\) es llamada en 2 ocasiones, de igual forma, \(\text{fib}(2)\) es llamada en 3 ocasiones, y tambien \(\text{fib}(0)\), \(\text{fib}(1)\) se llaman varias veces.

  Una funcion recursiva que se llama a si misma varias veces, por los mismos valores se llama recursion excesiva. Esta implementacion de la sucesion de fibonacci es una recursion excesiva.

  Para evitar esto podemos utilizar un array global, que todos sus valores se inicialicen a \(-1\). Y por cada llamada se haria array[n] = fib(n).

  El trazo seria el siguiente:

  

  Asi pasamos de 15 llamadas a 6. Pasando de una complejidad de tiempo \(O(2^n)\) a \(O(n)\).

  Esta tecnica, la de almacenar valores ya conocidos en un arreglo se llama Memoizacion.

• Implementacion en C

  int F[10];
  
  int
  fib (int n)
  {
    if (n <= 1)
      {
        F[n] = n;
        return n;
      }
  
    if (F[n - 2] == -1)
      F[n - 2] = fib (n - 2);
  
    if (F[n - 1] == -1)
      F[n - 1] = fib (n - 1);
  
    return F[n - 2] + F[n - 1];
  }
  

  Notese que el array no esta inicializado a -1, ese es solo un ejemplo.

La Torre de Hanoi ATTACH

El problema de la torre de hanoi es el siguiente:

Fuente: www.mathsisfun.com

Hay una cantidad \(n\) de discos en una torre A (de tres torres: A, B y C). El problema, es que debemos mover todos los discos de la torre A a la torre C y tenemos 2 reglas para hacerlo:

1. Unicamente podemos mover un disco a la vez.
2. No puede haber un disco mas grande sobre uno mas pequeno.

Siguiendo esas reglas tenemos que mover los \(n\) discos de torrea A a torre C.

• Algoritmo recursivo

  • 1 Disco ATTACH

    Si tenemos un unico disco:

    

    Podemos unicamente mover ese disco de A a C:

    

    Entonces si tenemos:

    \(\text{TOH}(1, A, B, C) = \text{Mover disco de A a C usando B}\)

    El orden de esa funcion es “Torre de Hanoi, usando 1 disco, movemos de la torre A a la torre C, usando la torre B”.

    El primer parametro son el numero de discos, el segundo es la torre inicial, el cuarto es la torre final, y el tercero es la torre intermedia.

  • 2 Discos ATTACH

    Si ahora tenemos dos discos:

    

    Podemos mover el disco mas pequeno a B:

    

    Movemos el disco de la torre A a la torre C:

    

    Y por ultimo movemos el disco de la torre B a la torre C.

    Tendriamos una funcion de 3 pasos:

    \(\text{TOH}(2, A, B, C):\)

    1. \(\text{TOH}(1, A, C, B)\): Movemos un disco de la torre A a la torre B, usando la torre C.
    2. Movemos un disco de la torre A a la torre C, usando la torre B (el mismo paso que hicimos al mover un solo disco.)
    3. \(\text{TOH} (1, B, A, C)\): Movemos un disco de la torre B a la torre C, usando la torre A.

  • 3 Discos

    Si tenemos \(\text{TOH}(3, A, B, C)\) podemos utilizar el paso anterior, para mover dos discos de A a B, mover el disco de A a C, y los dos discos restantes de B a C:

    \(\text{TOH}(3, A, B, C)\)

    1. \(\text{TOH}(2, A, C, B)\): movemos dos discos usando los 3 pasos anteriores.
    2. Movemos un disco de A a C
    3. \(\text{TOH}(2, B, A, C)\): movemos dos discos usando los 3 pasos anteriores.

  • Procedimiento

    Con el procedimiento de los 3 discos nos podemos hacer una idea para N cantidad de discos:

    \(\text{TOH}(n, A, B, C)\):

    1. \(\text{TOH}(n - 1, A, C, B)\)
    2. Mover un disco de A a C
    3. \(\text{TOH}(n - 1, B, A, C)\)

  • Funcion en C

    Este problema lo podemos escribir en C de la siguiente manera:

    void
    TOH (int n, int A, int B, int C)
    {
      if (n <= 0)
        return;
    
      TOH (n - 1, A, C, B);
      printf ("Mover de %d a %d usando %d\n", A, C, B);
      TOH (n - 1, B, A, C);
    }
    

  • Trazo ATTACH

    

    Segun ese trazo, los pasos son:

    1. Disco de 1 a 3
    2. Disco de 1 a 2
    3. Disco de 3 a 2
    4. Disco de 1 a 3
    5. Disco de 2 a 1
    6. Disco de 2 a 3
    7. Disco de 1 a 3

    En total, hizo 15 llamadas (hay 8 llamadas que no se realizaron porque \(n \le 0\)) para 3 discos.

    La complejidad de tiempo de esta funcion es \(O(2^n)\).