Algoritmos recursivos

Un algoritmo recursivo es un método donde un problema se resuelve haciendo referencia a una versión más pequeña de sí mismo. La idea corresponde a las definiciones recursivas en matemáticas: empezamos con una base, y luego sigue un paso recursivo, que repite el algoritmo en una parte más simple del problema.

 

 

De la definición al código

Cuando tenemos una definición recursiva, a menudo puede traducirse directamente en un algoritmo. Solo es necesario traducir:

 

• Base: cuándo puede detenerse el algoritmo.
• Paso recursivo: cómo se reduce el problema y el algoritmo se llama a sí mismo.

 

 

Ejemplo: Factorial

La función factorial se define recursivamente como

 

$$ \large 0! = 1 $$

$$ \large n! = n \cdot (n-1)!, \quad n \geq 1 $$

 

Esto puede escribirse como un algoritmo en pseudocódigo:

 

function factorial(n):
    if n = 0:
        return 1        // base
    else:
        return n * factorial(n - 1)   // paso recursivo

 

 

El algoritmo se detiene cuando \( \large n = 0 \); de lo contrario, se llama a sí mismo con un número más pequeño. Finalmente, todas las llamadas se combinan en el resultado.

 

 

Ejemplo: Máximo en una lista

También podemos definir un algoritmo recursivo para encontrar el número más grande en una lista:

 

• Base: Si la lista solo tiene un elemento, este elemento es el máximo.
• Paso recursivo: Comparar el primer elemento con el máximo del resto de la lista.

 

 

function max(list):
    if list has length 1:
        return list[0]            // base
    else:
        m = max(rest of list)     // paso recursivo
        return the larger of list[0] and m

 

 

Ejemplo en la práctica

 

Si tenemos la lista \( \large [7, 2, 9, 4] \):

max([7,2,9,4])

= mayor de 7 y max([2,9,4])

= mayor de 7 y mayor de 2 y max([9,4])

= mayor de 7 y mayor de 2 y mayor de 9 y max([4])

= mayor de 7 y mayor de 2 y mayor de 9 y 4

= mayor de 7 y mayor de 2 y 9

= mayor de 7 y 9

= 9

 

 

Resumen

Un algoritmo recursivo traduce la idea detrás de una definición recursiva en código. Primero se especifica un caso base donde el algoritmo se detiene. Luego se describe un paso recursivo, donde el algoritmo se llama a sí mismo sobre un problema más simple. Este patrón aparece en muchos algoritmos conocidos, como la ordenación, la búsqueda y el procesamiento de estructuras de datos.