Clase de Recursividad

#include <bits/stdc++.h>

namespace {
using namespace std;

template<typename T>
void Imprimir(const T& arreglo, string separador = " ") {
  for (const auto& a : arreglo) {
    cout << a << separador;
  }
  cout << endl;
}

void ImprimirEnBinario(int N) {
  //if (N >= 2) {
    ImprimirEnBinario(N / 2);
  //}
  cout << N % 2;
}

void PruebaPila(int N) {
  if (N == 0) {
    return;
  }
  cout << N << " ";
  if (N % 2 == 0) {
    PruebaPila(N - 1);
    cout << "P";
  } else {
    PruebaPila(N - 1);
    cout << "I";
  }
  cout << N << " ";
}

using Imagen = vector<string>;
Imagen SierpinskyCuadrado(int niveles) {
  if (niveles == 1) {
    return {
      "##",
      "# "
      };
  }
  auto cuarto_de_imagen = SierpinskyCuadrado(niveles - 1);
  Imagen salida;
  for (const string& linea : cuarto_de_imagen) {
    salida.push_back(linea + linea);
  }
  for (const string& linea : cuarto_de_imagen) {
    salida.push_back(linea + string(linea.size(), ' '));
  }
  return salida;
}

// 1 + 2 + 3 + 4 + 5 + 6 + ... + N
int Sum(int N) {
  if (N == 0) {
    return 0;
  }
  if (N % 2) {
    return N + Sum(N-1);
  }
  int sum_mitad = Sum(N / 2);
  return 2*sum_mitad + (N / 2) * (N / 2);
}

double AreaSector(double x, double y, int niveles) {
  double xmedio = x + (1.0 - x) / 2;
  double ymedio = y / 2;
  if (niveles == 1) {
    return ymedio;
  }
  double norma = sqrt(xmedio*xmedio + ymedio*ymedio);
  double area_mitad = AreaSector(xmedio / norma, ymedio / norma, niveles - 1);
  return area_mitad * 2.0;
}

vector<string> GeneraCadenas(const string& alfabeto, int longitud) {
  if (longitud == 0) {
    return {""};
  }
  vector<string> prefijos = GeneraCadenas(alfabeto, longitud - 1);
  vector<string> salida;
  salida.reserve(prefijos.size() * alfabeto.size());
  for (const string& p : prefijos) {
    for (char c : alfabeto) {
      salida.push_back(p + c);
    }
  }
  return salida;
}

void ImprimePermutaciones(string& cadena, int indice = 0) {
  if (indice == cadena.size()) {
    cout << cadena << endl;
    return;
  }
  for (int i = indice; i < cadena.size(); ++i) {
    swap(cadena[i], cadena[indice]);
    ImprimePermutaciones(cadena, indice + 1);
    swap(cadena[i], cadena[indice]);
  }
}

void MergeSortLegacy(vector<int>& arreglo) {
  int N = arreglo.size();
  if (N < 2) {
    return;
  }
  vector<int> izq(arreglo.begin(), arreglo.begin() + N / 2);
  vector<int> der(arreglo.begin() + N / 2, arreglo.end());
  MergeSortLegacy(izq);
  MergeSortLegacy(der);
  int i = 0, d = 0;
  arreglo.clear();
  while (i < izq.size() || d < der.size()) {
    if (i < izq.size() && (d == der.size() || izq[i] < der[d])) {
      arreglo.push_back(izq[i]);
      ++i;
      continue;
    }
    arreglo.push_back(der[d]);
    ++d;
  }
}
// Ordena los números desde inicio hasta fin, sin incluir fin
void MergeSort(int* inicio, int* fin) {
  if (fin - inicio < 2) {
    return;
  }
  int* centro = inicio + (fin - inicio) / 2;
  MergeSort(inicio, centro);
  MergeSort(centro, fin);
  vector<int> izq(inicio, centro);
  vector<int> der(centro, fin);
  int* salida = fin - 1;
  while (!izq.empty() || !der.empty()) {
    if (!izq.empty() && (der.empty() || izq.back() > der.back())) {
      *salida = izq.back();
      izq.pop_back();
    } else {
      *salida = der.back();
      der.pop_back();
    }
    --salida;
  }
}

void ProbarMergeSort(int N) {
  vector<int> prueba;
  for (int i = 1; i <= N; ++i) {
    prueba.push_back(i);
  }
  random_shuffle(prueba.begin(), prueba.end());
  Imprimir(prueba);
  MergeSort(&prueba[0], &prueba[0] + N);
  Imprimir(prueba);
}

}

int main() {
  ProbarMergeSort(100);
  //printf("%.50lf\n", AreaSector(0, 1.0, 100) * 4.0);
  //Imprimir(SierpinskyCuadrado(6), "\n");
  //ImprimirEnBinario(1024 + 128 + 64 + 2 + 1);

  //PruebaPila(10);
  //cout << endl;

  /*ImprimirEnBinario(1024 + 128 + 64 + 2 + 1);
  cout << endl;
  cout << Sum(1023) << std::endl;
  cout << AreaSector(0, 1.0, 20) * 4.0 << std::endl;
  ProbarMergeSort(100);
  Imprimir(GeneraCadenas("axz", 3));
  Imprimir(SierpinskyCuadrado(6), "\n");
  string cadena = "abc";
  ImprimePermutaciones(cadena, 0);*/
  return 0;
}