8. Recursión

Práctica 03

Encuentra el último elemento de una lista.

* (my-last '(a b c d))
(D)

Teoría

La recursión es una técnica fundamental en programación funcional donde una función se llama a sí misma para resolver un problema dividiéndolo en subproblemas más pequeños.

Una función recursiva típicamente tiene dos partes:

1. Caso base: la condición que detiene la recursión.
2. Caso recursivo: la llamada a sí misma con un problema más pequeño.

Ejemplo simple, calcular el factorial de un número:

(defun factorial (n)
  (if (<= n 1)
      1                          ; Caso base
      (* n (factorial (- n 1))))) ; Caso recursivo

* (factorial 5)
120

* (factorial 0)
1

Veamos cómo funciona paso a paso:

(factorial 5)
→ (* 5 (factorial 4))
→ (* 5 (* 4 (factorial 3)))
→ (* 5 (* 4 (* 3 (factorial 2))))
→ (* 5 (* 4 (* 3 (* 2 (factorial 1)))))
→ (* 5 (* 4 (* 3 (* 2 1))))
→ (* 5 (* 4 (* 3 2)))
→ (* 5 (* 4 6))
→ (* 5 24)
→ 120

Otro ejemplo, sumar todos los números de una lista:

(defun sumar-lista (lst)
  (if (null lst)
      0                                    ; Caso base: lista vacía
      (+ (car lst) (sumar-lista (cdr lst))))) ; Caso recursivo

* (sumar-lista '(1 2 3 4 5))
15

El flujo sería:

(sumar-lista '(1 2 3 4 5))
→ (+ 1 (sumar-lista '(2 3 4 5)))
→ (+ 1 (+ 2 (sumar-lista '(3 4 5))))
→ (+ 1 (+ 2 (+ 3 (sumar-lista '(4 5)))))
→ (+ 1 (+ 2 (+ 3 (+ 4 (sumar-lista '(5))))))
→ (+ 1 (+ 2 (+ 3 (+ 4 (+ 5 (sumar-lista '()))))))
→ (+ 1 (+ 2 (+ 3 (+ 4 (+ 5 0)))))
→ (+ 1 (+ 2 (+ 3 (+ 4 5))))
→ (+ 1 (+ 2 (+ 3 9)))
→ (+ 1 (+ 2 12))
→ (+ 1 14)
→ 15

Puntos clave para escribir funciones recursivas:

1. Identifica el caso base: ¿cuándo debe detenerse la recursión? Normalmente cuando la lista está vacía (null), un número llega a cero, etc.

2. Define el caso recursivo: ¿cómo reducir el problema? Típicamente procesando el primer elemento (car) y llamando recursivamente con el resto (cdr).

3. Asegúrate de avanzar hacia el caso base: cada llamada recursiva debe acercarse al caso base, o tendrás recursión infinita.

Ejemplo de contar elementos en una lista:

(defun contar (lst)
  (if (null lst)
      0
      (+ 1 (contar (cdr lst)))))

* (contar '(a b c d e))
5

La recursión puede ser más elegante que los bucles iterativos, especialmente cuando trabajas con estructuras recursivas como listas o árboles. En lecciones posteriores veremos optimizaciones como la recursión de cola (tail recursion).