Recursividad
Concepto Clave en Computación

Recursividad en Ciencias Computacionales

La recursividad es un método que permite resolver problemas complejos dividiéndolos en versiones más simples de sí mismos, mediante funciones que se llaman a sí mismas. Es fundamental para algoritmos elegantes y eficientes en programación y matemáticas.

Empezar Lectura →

Importancia

La recursividad es esencial para la programación, pues facilita la resolución de problemas complejos como estructuras jerárquicas, series matemáticas, y algoritmos divide y vencerás. Permite modelar soluciones claras y reutilizables.

Algoritmo Factorial

El factorial de un número entero positivo n! es el producto de todos los enteros positivos desde 1 hasta n. Matemáticamente se define así:

n!=n×(n−1)×(n−2)×…×3×2×1

Por convenio, \(0! = 1\).

Este algoritmo es un clásico ejemplo de recursividad donde el caso base es \(n=0\).

Diagrama

Ejemplo práctico en JavaScript

function factorial(n) {
    if (n === 0) return 1; // Caso base
    return n * factorial(n - 1);
}

Aplicaciones:

Algoritmo Fibonacci

La sucesión de Fibonacci es una serie matemática donde cada término es la suma de los dos anteriores, comenzando con 0 y 1:

0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597

Este algoritmo se implementa recursivamente sumando los dos valores previos hasta llegar a los casos base.

Árbol recursivo para calcular Fibonacci(4)

Diagrama Fibonacci

Ejemplo en JavaScript

function fibonacci(n) {
    if (n === 0) return 0;      // Caso base 1
    if (n === 1) return 1;      // Caso base 2
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Aplicaciones:

Torres de Hanói

Las Torres de Hanói es un rompecabezas que consiste en mover una pila de discos de diferentes tamaños desde un poste inicial a uno destino usando un poste auxiliar, siguiendo dos reglas:

Este problema es famoso por su solución recursiva basada en mover n-1 discos al poste auxiliar, luego el disco más grande, y finalizando con los n-1 discos al poste destino.

Visualización gráfica de Torres de Hanói con 3 discos

Secuencia visual del movimiento de 3 discos en Torres de Hanói

Ejemplo recursivo en JavaScript

function hanoi(n, origen, destino, auxiliar) {
    if (n === 1) {
        console.log(`Mover disco 1 de ${origen} a ${destino}`);
        return;
    }
    hanoi(n - 1, origen, auxiliar, destino);
    console.log(`Mover disco ${n} de ${origen} a ${destino}`);
    hanoi(n - 1, auxiliar, destino, origen);
}

Aplicaciones:

Fractales

Los fractales son figuras geométricas que muestran auto-similitud y estructuras repetitivas a diferentes escalas. Se producen con algoritmos recursivos infinitos o con profundidad limitada.

Un ejemplo clásico es el Triángulo de Sierpinski, que se construye dividiendo un triángulo en cuatro pequeños y eliminando el central iterativamente.

Triángulo de Sierpinski generado recursivamente

Triángulo de Sierpinski, fractal generado de forma recursiva

Ejemplo de función recursiva sencilla en JavaScript

function sierpinski(depth) {
    if(depth === 0) {
        // Dibujar triángulo base
        return;
    }
    // Llamadas recursivas para subdividir
    sierpinski(depth - 1);
    sierpinski(depth - 1);
    sierpinski(depth - 1);
}

Aplicaciones:

Conclusión

La recursividad es una técnica esencial en ciencias computacionales por su capacidad para dividir problemas complejos en subproblemas manejables, facilitando soluciones elegantes y estructuradas.

Los ejemplos presentados, desde factoriales y Fibonacci hasta las Torres de Hanói y fractales, demuestran cómo la recursividad es aplicable para resolver problemas matemáticos, estructurales y gráficos, siendo una herramienta fundamental para el desarrollo de algoritmos eficientes y comprensibles.

Referencias IEEE