Nociones básicas

Imagina que tienes una función \(f\) que resuelve un problema de esta manera:

Por ejemplo:

\[f(n) = 1 * 2 * 3 * \dots * n\]

Queremos calcular \(f(n)\) de una manera recursiva. Entonces necesitamos:

Si \(n = 0 \to f(0) = 1\).

\[f(n) = \underbrace{1 * 2 * 3 * \dots * (n - 1)}_{\text{f(n - 1)}} * n\] \[f(n) = n * f(n - 1)\]

Entonces, básicamente estamos diciendo que si \(n = 0\) sabemos como resolver el problema, sino si sabemos la respuesta de \(f(n - 1)\) podemos resolver \(f(n)\).

En código esto es así:

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

Lo que es agradable sobre recursión es que podemos llegar a las soluciones pensando de manera recursiva. Pensar de esta manera puede facilitar una gran variedad de problemas. Para ello puedes decir:

Sea \(f\) la función que resuelva el problema que estoy intentando resolver. Entonces, podemos decir: No tengo idea como resolver \(f(state)\), pero si de alguna manera tuviera el resultado de \(f(state'), f(state''), f(state'''), \dots\) entonces yo podría resolver \(f(state)\) y yo se como resolver el problema en casos específicos a los que siempre termino llegando.

Así, en código, soluciones recursivas suelen tener esta forma:

T f(state):
  if (state tiene alguna propiedad en específico):
    resuelve el problema para este estado y retorna algo
  else:
    obten la respuesta de f(state'), f(state''), f(state'''), ...
    y usa estos resultados para calcular f(state) y retorna algo
Las torres de Hanoi

Veamos como podemos resolver un problema aparentemente difícil usando recursión.

La imagen fue extraída de Wikipedia.

Problema: Tienes 3 postes fijos y una pila de \(n\) discos en un poste. Cada disco tiene diferente diámetro, los discos están en orden puestos uno encima de otro, el más gran en el fondo y el más pequeño en la cima. Queremos mover todos los discos de un poste a otro. Solo podemos mover el disco que está primero en un poste a otro poste que este vacío o a uno donde el diámetro del disco que está en su cima es mayor del diámetro del disco que estamos moviendo.

Digamos que tenemos la función \(f\) tal que \(f(source, target, pivot, n)\) mueve los \(n\) discos que están en el poste source al poste target. Entoces, podemos decir:

Si yo quiero mover los \(n\) discos del poste source al poste target, primero yo necesito mover \(n - 1\) discos de source a pivot, después moveré el último disco de source a target. Tras ese movimiento moveré los \(n - 1\) discos de pivot a target y así ya tendremos el problema resuelto. Además, si solo hay un disco en un poste podemos moverlo directamente a target. De este modo, podemos escribir \(f\) de esta manera:

void f(source, target, pivot, n):
  if n == 1:
    mueve el disco de source a target
    return
  # mueve los primeros n - 1 discos de source a pivot
  f(source, pivot, target, n - 1)
  # mueve el último disco de source a target  
  f(source, target, pivot, 1)
  # mueve los n - 1 discos de pivot a target
  f(pivot, target, source, n - 1)

Y eso es todo, esto resuelve el problema.

Ejercicios

Implementa soluciones recursivas para los siguientes ejercicios:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

int main () {
  int n = 40;
  cout << fib(n) << '\n';
  return (0);
}

#include <bits/stdc++.h>

using namespace std;

int sumOfDigits (int n) {
  if (n == 0) return 0;
  return (n % 10) + sumOfDigits(n / 10);
}

int main () {
  int n = 999;
  cout << sumOfDigits(n) << endl;
  return (0);
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll comb (int n, int m) {
  if (m == 0) return 1;
  if (n == m) return 1;
  return comb(n - 1, m - 1) + comb(n - 1, m);
}

int main () {
  cout << comb(4, 2) << '\n';
  return (0);
}

// TAREA

Aritmética y recursión

Hay cierto tipo de problema donde nos darán una propiedad matemática y nos pedirán encontrar cuántos números en un rango \([l, r]\) la cumplen o variaciones de esta idea. Para atacar este tipo de problemas suele ser útil utilizar propiedades básicas de Aritmética y conseguir recursión que nos resuelva el problema. Veamos un ejemplo.

Problema: CPCRC1C - Sum of Digits

Básicamente nos piden:

\[\sum_{k = a}^{b}sumaDeDigitos(k)\] \[0 \leq a \leq b \leq 1e9\]

Luego, la solucion trivial de iterar en el rango \([a, b]\) nos daría una complejidad \((b \log b)\) lo cual daría TLE. Entonces, busquemos una solución más eficiente.

Primero, definamos:

\[S(x) = \sum_{k = 0}^{x}sumaDeDigitos(k)\]

Luego, nuestro problema se reduce a calcular \(S(b) - S(a - 1)\)

Ahora, centrémonos en calcular eficientemente \(S\).

Sea \(x = \overline{x_nx_{n-1} \dots x_k \dots x_2x_1}\)

Definamos \[cnt(x, k) = \sum_{i = 0}^{x} \text{el k-esimo dígito de } i\]

Luego \[S(x) = \sum_{k = 0} ^ {n} cnt(x, k)\]

Así, como n es \(O(log x)\), todo se reduce a calcular eficientemente \(cnt(x, k)\)

Ahora, para calcular \(cnt(x, k)\) notemos que estaremos sumando los k-esimos dígitos de los números \(num \in [0, x]\).

Sea \(p = \overline{p_np_{n-1}\dots p_{k +1}p_{k}p_{k -1}\dots p_{1}}\) (podemos considerar que \(num\) siempre tiene n dígitos por simplicidad - si tiene menos de n dígitos simplemente podemos agregarle ceros al inicio y no afectará la respuesta -)

Ahora analicemos por casos:

Notamos que ya no hay mas casos para analizar, luego \(cnt(x, k)\) sería la suma de los resultados obtenidos en cada caso, obteniendo:

\[cnt(x, k) = 10 ^ {k - 1} \times (\overline{x_nx_{n-1}\dots x_{k+1}}) \times 45 + 10 ^ {k - 1} \times max(0, x_k - 1) \times (max(0, x_k - 1) + 1) / 2 + p_k \times (\overline{x_{k + 1} \dots x_1} + 1)\]

Ahora, con ello ya podemos calcular eficientemente \(S(x)\), lo cual nos permitirá resolver nuestro problema original.

Esta es la implementación:

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
ll s (ll num) { return num * (num + 1) / 2; }
 
ll sum (ll num, ll power = 1, ll r = 0) {
  if (num == 0) return 0;
  int d = num % 10;
  return (num / 10) * 45 * power + s(max(0, d - 1)) * power + d * (r + 1) + sum(num / 10, power * 10, r + d * power);
}
 
int main () {
  int a, b;
  while (cin >> a >> b, a != -1 and b != -1) cout << sum(b) - sum(max(0, a - 1)) << endl;
  return (0);
}
Fractales

En las competencias, hay ocasiones donde ponen problemas para dibujar un patrón, generalmente algún fractal. Para resolver este tipo de problemas suele ser muy útil pensar en términos recursivos. Veamos un ejemplo.

Problema: Fractal

Notemos como el problema se reduce a definir bien una función recursiva, hacer las transiciones apropiadas y definir como comenzar la recursión.

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

vector <string> grid;
int DR[] = {-1, -1, 1, 1, 0};
int DC[] = {1, -1, 1, -1, 0};

void print () {
  for (int i = 0; i < grid.size(); i++) {
    string& row = grid[i];
    int j = row.size() - 1;
    while (row[j] == ' ') row.erase(row.begin() + j);
    cout << row << endl;
  }
  cout << '-' << endl;
}

void rec (int r, int c, int step) {
  if (step == 0) {
    grid[r][c] = 'X';
    return;
  }
  for (int d = 0; d < 5; d++) {
    rec(r + DR[d] * step, c + DC[d] * step, step / 3);
  }
}

int main () {
  int n;
  while (cin >> n, n != -1) {
    int gridSize = int(pow(3, n - 1));
    grid = vector <string> (gridSize, string(gridSize, ' '));
    int initial = (n == 1) ? 0 : gridSize / 3 + gridSize / 6; 
    int step = gridSize / 3;
    rec(initial, initial, step);
    print();
  }
  return (0);
}

Lecturas recomendadas:

Contest

El contest lo puedes encontrar aquí.