CP-UPV Bootcamp - Capítulo 6

Capítulo 6: Recursión

Introducción

La recursión es uno de los conceptos fundamentales y más poderosos en la programación. Se trata de una técnica donde una función se llama a sí misma para resolver un problema dividiéndolo en subproblemas más pequeños y manejables. Entender y dominar la recursión no solo te permitirá resolver problemas de forma más elegante, sino que también te abrirá la puerta a una amplia gama de algoritmos y soluciones, desde la exploración de grafos hasta la optimización de cadenas.

Además, introduciremos otros conceptos que, aparte de ser utilizados en otros contextos, también son relevantes para entender mejor la recursión y aplicarla de manera correcta.

Índice de contenidos

• Punteros
  • Operadores
  • Ventajas
• Funciones
  • Call stack
  • Parametros por valor
  • Parametros por referencia
  • Return
• Recursión básica
  • Imprimir del 1 a N
  • Fibonnaci
  • Factorial
• DFS

Punteros

Los punteros son unas variables especiales que nos sirven para almacenar la dirección en memoria de otra variable. De esta forma, podemos manejar y manipular los datos de una forma más eficiente.

Operadores

Para manejar punteros, tenemos a nuestra disposición dos operadores especiales:

• &: Utilizado para obtener la referencia en memoria de una variable
• *: Utilizado para obtener los datos bajo una dirección de memoria(también llamado dereferenciar)

int a = 10;
int* puntero = &a; // Se utiliza '*' en la declaración para indicar que es puntero de un int
// & obtiene la dirección de memoria y la asigna a la variable `puntero`

cout << puntero << endl;
// 0x7ffc12345678  -  Una dirección 'aleatoria'

cout << *puntero << endl;
// 10  -  Devuelve el valor que hay en esa dirección, tratado como un int

*puntero = 20; // Usando punteros, podemos modificar esos datos, que son persistentes
// "Valor en 'puntero'" = 20
cout << *puntero << endl;
// 20

cout << a << endl;
// 20
// Como modificamos usando el puntero, su valor es diferente ahora

La utilidad de los punteros viene del hecho de que nos pueden servir para realizar diferentes operaciones de manera más eficiente, más directa, como podremos ver más adelante pasando argumentos por referencia.

Ventajas

• Eficiencia: Cuando pasamos una variable por referencia mediante un puntero, evitamos hacer copias innecesarias de la variable en cada llamada recursiva. Esto es particularmente útil cuando trabajamos con grandes estructuras de datos o cuando queremos modificar el estado de un objeto o variable fuera del alcance local de la función.
• Manipulación directa de estructuras de datos: En estructuras como árboles binarios o listas enlazadas, los punteros permiten que una función modifique directamente los nodos del árbol o los elementos de la lista. Esto es esencial para operaciones como la inserción, eliminación, o recorrido de estas estructuras, ya que al apuntar directamente a los nodos del arbol, nos ahorra el tener que sustituir toda la estructura de datos por la copia modificada cada vez que se quiere realizar un cambio persistente.

Funciones

Call Stack

Antes de pasar a la recursión debemos tener claro qué es el Call Stack.

El Call Stack es, como su nombre indica, un stack, pero este se diferencia de los que creamos nosotros en que es usado para almacenar información sobre las variables y funciones que son usadas en un programa. Esto lo hace añadiendo al stack una entrada, o stack frame, por cada recurso que se utiliza, por ejemplo:

int funcion(int a, int b) {
    int c = a + b;
    // (2)
    return c;
}

void main() {
    int a = 10, b = 20;
    // (1)
    cout << funcion(b, a) << endl;
    // (3)
}

• En la situación (1):

  TOP
  b	20
  a	10
  main()
  BOTTOM

• En la situación (2)

  TOP
  c	30
  b (argumento)	10
  a (argumento)	20
  funcion()
  b	20
  a	10
  main()
  BOTTOM

• En la situación (3):

  TOP
  b	20
  a	10
  main()
  BOTTOM

Como podemos observar, saltandonos bastantes detalles, se va añadiendo una entrada por cada llamada a una función, alojando información sobre las variables y argumentos que son usados en esta función. Con esta información guardada, es que podemos mantener o pasar información con cada instrucción de nuestro código con la seguridad de que tendremos esa información de manera accesible.

Argumentos por valor

Cuando pasamos argumentos por valor, lo que hacemos es darle una copia del valor de la variable que pasamos como argumento, es decir, si por ejemplo tenemos este código:

void cambio(int a, int b) {
    int aux = a;
    a = b;
    b = aux;
}

void main() {
    int num = 3, num1 = 8;
    cambio(num, num1);
    cout << num << ", " << num1 << endl;
}

> 3, 8

La función recibirá como argumentos los valores 3 y 8, y en las variables locales que se crean(a y b), asignará los valores correspondientes. De esta forma, podemos usar los valores iniciales de unas variables y modificarlos pero después mantener esos valores iniciales. Sin embargo, hay ocasiones en las que sí que queremos modificar el valor de las variables iniciales, esto lo podemos hacer pasando los argumentos por referencia.

Argumentos por referencia

Al pasar argumentos por referencia, lo que hacemos es proveer a la función de la dirección en memoria donde empiezan los datos de la variable que hemos pasado, esto nos permite poder realizar cambios en esta variable inicial, y que estos se apliquen cuando ejecutamos la función.

void cambio(int &a, int &b) {
    int aux = a;
    a = b;
    b = aux;
}

void main() {
    int num = 3, num1 = 8;
    cambio(num, num1);
    cout << num << ", " << num1 << endl;
}

> 8, 3

Con este ejemplo, vemos como el valor de las variables num y num1 sí que se han intercambiado, al contrario que en el ejemplo anterior.

En muchas ocasiones, no habrá mucha diferencia entre usar o no una técnica u otra, pero shay aspectos que debemos tener en cuenta, ya que nos permitirán decidir si utilizar una o la otra.

• TAMAÑO: Un puntero ocupa un espacio en memoria de 4 u 8 Bytes, dependiendo de la arquitectura del procesador, un tamaño muy similar al de los tipos de datos más comunes, como int o char, pero si por ejemplo estamos pasando como argumento un objeto como un vector<int> de tamaño 1000x1000, la diferencia de memoria utilizada será notable.

  void func(vector<int> &a) {...}
  
  void funcion(vector<int> a) {...}
  // En el call stack, el frame de 'func' ocupará menos ya que usa una referencia
  // en vez de alojar espacio para una copia del vector

  SUPER IMPORTANTE

  Por defecto se pasan por valor, o como una copia:

  • variables de tipos fundamentales (como int, float, bool, long long)
  • objetos o structs (como string, vector, MiObjetoCustom), por ejemplo:

  #include <bits/stdc++.h>
  using namespace std;
  
  void modify(vector<int> a) {
      cout << "2: " << a.size() << endl;
      a.push_back(3);
      cout << "3: " << a.size() << endl;
  }
  
  int main() {
      vector<int> a; a.push_back(2);
      cout << "1: " << a.size() << endl;
  
      modify(a);
      cout << "4: " << a.size() << endl;
      return 0;
  }
  
  // Output
  1: 1
  2: 1
  3: 2
  4: 1

  #include <bits/stdc++.h>
  using namespace std;
  
  void modify(string a) {
      cout << "2: " << a << endl;
      a += "Hola";
      cout << "3: " << a << endl;
  }
  
  int main() {
      string a = "Hello"
      cout << "1: " << a << endl;
  
      modify(a);
      cout << "4: " << a << endl;
      return 0;
  }
  
  // Output
  1: Hello
  2: Hello
  3: HelloHola
  4: Hello

  Pero al pasar un array (1D, 2D...) como argumento, se pasa el puntero al primer elemento de ese array y por tanto no se hace una copia de ese array

  #include <bits/stdc++.h>
  using namespace std;
  
  // SI SE PASA UN ARRAY A UNA FUNCIÓN, HAY QUE PASAR TAMBIÉN SU TAMAÑO!!!
  void modify(int a[], int tamanoDelArray) {
      cout << "2: " << a[0] << endl;
      a[0] = 100;
      cout << "3: " << a[0] << endl;
  }
  
  int main() {
      int a[4] = {0, 0, 0, 0};
      cout << "1: " << a[0] << endl;
  
      modify(a, 4);
      cout << "4: " << a[0] << endl;
      return 0;
  }
  
  // Output
  1: 0
  2: 0
  3: 100
  4: 100

• MODIFICACIÓN DEL VALOR: Debemos tener en cuenta si necesitamos modificar el valor de la variable original o no, ya que los cambios realizados mediante punteros son persistentes, mientras que las variables pasados por valor no son modificadas en memoria, si no que se modifican las copias locales de estas.

  // Ineficiente, porque se hace una copia
  void buscarMax(vector<int> a) {
      int max = INT_MIN;
      for(int i = 0; i < a.size(); ++i) {
          if(a[i] > max) max = a[i];
      }
      
      cout << max;
  }
  
  // Al no cambiar nada en el array, podemos utilizar mejor la función en la que
  // el argumento se pasa por referencia, ya que de esta forma nos ahorramos 
  // el tener que crear una copia del array
  void buscarMaxConPuntero(vector<int> &a) {...}
                      

Return

return es una instrucción especial que no solo nos sirve para devolver el resultado de una función. Habrás visto que en la sintáxis de una función, lo primero que se indica es un tipo de dato. Este tipo de dato es lo que se espera que devuelva obligatoriamente la función:

// La función main devuelve un 'int', como se indica aquí
int main() {
    // OBLIGATORIAMENTE debe haber una instrucción 'return' que devuelva un 'int' en alguna parte de la función
    ...

    return 0;  // <-- 0 es de tipo `int`
}

// Caso excepcional, si no se va a devolver ningún valor, se utiliza 'void' como tipo de dato
void diHola() {
    cout << "Hola" << endl;

    // Se puede escribir 'return;' sin ningún dato para parar la ejecución de una función, pero como no se espera devolver un valor de la función ('void'), esta instrucción es opcional
}

En el caso de la recursión, la instrucción return se puede utilizar para propagar resultados hacia atrás en el call stack hasta la llamada inicial del método, esto nos será útil para diseñar funciones que vayan calculando el resultado final realizando varias llamadas a si mismo, como ya veremos más adelante con el DFS y otras funciones básicas.

Además, otra de las ventajas de utilizar return correctamente es el tener seguridad de que la recursión tiene un límite y se alcanzará un resultado antes de llegar a un stack overflow, uno de los errores más comunes en cuanto a recursión respecta, producido cuando se crean demasiadas entradas en el call stack, dando lugar a un desborde.

Algunos ejemplos de uso de la instrucción return, son:

• Acabar la ejecución en los casos base y propagar resultados hacia atrás en el call stack.

  int countZero(vector<int> vec, int pos) {
      if(pos >= vec.size()) return 0;
      if(vec[pos] != 0) {
          return countZero(vec, pos + 1);
      } else {
          return 1 + countZero(vec, pos + 1);
      }
  }

• Combinar resultados obtenidos por diferentes llamadas

  int fibonacci(int n) {
      if (n <= 1) return n;
      return fibonacci(n-1) + fibonacci(n-2); 
  }

• Terminación temprana de la ejecución. Por ejemplo, con el siguiente código, que resuelve un problema bastante conocido, el de las N-reinas, basado en tener N reinas y tratar de encontrar un conjunto de posiciones para estas tal que ninguna amenace a otra.

  bool solveNQueens(int row, int n, vector<int>& positions) {
      if (row == n) return true; // Posición valida, termina antes
      for (int col = 0; col < n; ++col) {
          if (isValid(row, col, positions)) {
              positions[row] = col;
              if (solveNQueens(row + 1, n, positions)) return true; 
          }
      }
      return false; // No hay posición válida
  }

Recursión básica

1 a N

Queremos enumerar todos los números desde el 1 hasta N, para ello, podemos diseñar una función recursiva de la siguiente forma:

• Caso base: Hemos llegado a N
• Caso general: Número diferente a N
• Relación: En cada llamada vamos incrementando nuestro número por 1

void funcion(int n) {
    if(n == 1) {
        cout << 1 << ' ';
    } else if (n > 1){
        funcion(n - 1);
        cout << n << ' ';
    }
}

Por ejemplo, con la llamada funcion(3), una posible traza del call stack sería:

Fibonacci

Queremos obtener el numero en la posición n dentro la secuencia de Fibonacci, esto lo podemos conseguir teniendo en cuenta lo siguiente:

• Caso base: $fib(0) = 0, fib(1) = 1$
• Caso general: $fib(n)1, n >= 2$
• Relación: Aplicamos la regla de fibonacci a n, es decir, $fib(n) = fib(n - 1) + fib(n - 2)$

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2); 
}

Por ejemplo, con la llamada fibonacci(4);, obtenemos el siguiente call stack:

Factorial

Para calcular el factorial de un número debemos considerar:

• Casos base: $0!=1, 1!=1$
• Relación: $n! = n * (n - 1) * ...$

long long fac(long long a) {
    if(a == 0) return 1;
    return a * fac(a - 1);
}

Por ejemplo, con la llamada fac(4);, podemos obtener una traza del call stack similar a esta:

DFS

Depth-First Search es un algoritmo de exploración recursivo de grafos basado en llegar hasta el final del camino, para después explorar el resto de ramas que se han ido encontrando. Veamos el ejemplo:

Dado el grafo:

 0
/ \
1  2 - 4
|   
3   
|
5

Y el código:

void DFS(int node, vector<vector<int>>& adj, vector<bool>& visited) {
    // Marcar nodo como visitado
    visited[node] = true;
    doSomething(node);
    
    // Visitar recursivamente los nodos adyacentes a este
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            DFS(neighbor, adj, visited);
        }
    }
}

// node: nodo actual del grafo
// adj: Lista de adyacencia, utilizada para representar el grafo, se verá más en el capítulo de grafos
// visited: Array auxiliar para marcar los caminos visitados

Podemos obtener la siguiente traza con la llamada DFS(0, adj, visited):

Nodo actual: 0 - Llamada #0
    - visited[0] = true;
    - adj[0] = 1, 2
    
Nodo: 1 - #1
    - visited[1] = true;
    - adj[1] = 3
    
Nodo: 3 - #2
    - visited[3] = true;
    - adj[3] = 5
    
Nodo: 5 - #3
    - visited[5] = true;
    - adj[5] = none
Ahora volvemos atrás, a la llamada 0, ya que nos queda por visitar 2,
que se ha quedado en el call stack esperando a ser usado
    
Nodo: 2 - #4
- visited[2] = true;
- adj[2] = 4

Nodo: 4 - #5
    - visited[4] = true;
    - adj[4] = none;
Como ya hemos acabado todo, el call stack se vacía y todos los nodos han sido
visitados.