3. Recursividad y ordenamiento

La recursión aparece en árboles, divide y vencerás y muchos algoritmos de ordenamiento. Dominar el caso base y el caso recursivo es clave antes de BST o merges en listas.

Patrón recursivo

Factorial — caso base + paso recursivo

JAVA

  public static long factorial(int n) { 
      if (n <= 1) { 
          return 1;           // caso base 
      } 
      return n * factorial(n - 1); // hacia el base 
  } 

Pila de llamadas: cada invocación consume marco de pila; si n es enorme, podés desbordar la pila (StackOverflowError). Por eso algunos algoritmos se reescriben iterativos o con cola explícita.

Merge Sort — divide y vencerás

Partís el arreglo por la mitad, ordenás recursivamente cada mitad y fusionás dos secuencias ordenadas en O(n). Tiempo típico O(n log n), espacio extra O(n) para el buffer de fusión.

        [ 3, 1, 4, 2 ]
              │
       ┌──────┴──────┐
    [3, 1]          [4, 2]
      │                │
   ┌──┴──┐          ┌──┴──┐
  [3]  [1]        [4]  [2]
      merge           merge
        │                │
     [1,3]            [2,4]
           merge
              │
         [1, 2, 3, 4]

Quick Sort — pivote y partición

Elegís un pivote, particionás «menores» y «mayores», y ordenás recursivamente los subarreglos. Promedio O(n log n); peor caso O(n²) si el pivote es siempre el mínimo o el máximo (arreglo ya ordenado con pivote malo).

Esquema de partición (Lomuto, idea)

JAVA

  // Después de particionar, el pivote queda en su posición final 
  // quickSort(arr, lo, pi - 1); 
  // quickSort(arr, pi + 1, hi); 

Propuesta de laboratorio

Implementá merge sort sobre int[] y contá comparaciones.
Medí tiempos con n = 10_000, 100_000 vs un O(n²) simple (solo para contrastar).
Anotá Big O de tu partición y de la fusión en comentarios.

Contenido

📚 Elige un curso