Algoritmos y programación RecursiónTema 1

Pensar en recursivo sin perderse

Una función recursiva no se entiende siguiendo cien llamadas. Se diseña con un contrato, un caso base y una reducción que siempre acerca el problema a ese caso.

Para este tema conviene tener claro:Funciones, parámetros y alcance

7 min de lectura4 bloques para tocar13 de sept de 2026

La recursión parece un truco: una función se llama a sí misma y, de algún modo, termina. Pero no hay magia, y tampoco hace falta seguir cien llamadas en la cabeza para escribirla. Toda solución recursiva se arma con tres piezas: qué promete resolver, cuándo deja de llamar y cómo achica el problema. Si las tres están bien, la función anda.

Empezá por el contrato

Antes de escribir código, decí qué promete la función. Para total(values): devuelve la suma de todos los números de values. Nada más.

El paso clave es confiar en ese contrato para una entrada más chica. Si la lista no está vacía, la suma es el primer elemento más la suma del resto, y “la suma del resto” es exactamente lo que promete total:

S([x_0, x_1, \ldots, x_n]) = x_0 + S([x_1, \ldots, x_n])

Pensar en recursivo es tratar esa llamada más chica como una caja negra que ya funciona. No se expande mentalmente: se usa.

El caso base

La caja negra necesita un punto donde ya conozcamos la respuesta sin preguntarle a nadie:

def total(values):
    if not values:
        return 0
    return values[0] + total(values[1:])

Antes de seguir, predecí

¿Qué devuelve total([])?

Sin caso base, las llamadas no terminan. Y si el caso base existe pero no cubre todas las rutas, el problema sigue ahí: cada ejecución posible tiene que llegar a una respuesta sin crear otra llamada.

Una medida que siempre baja

Tener caso base no alcanza: cada llamada tiene que acercarse a él. En total, la longitud de la lista baja de $n$ a $n - 1$ en cada llamada, así que después de $n$ pasos llega a cero.

Esa es la forma práctica de demostrar que una recursión termina: elegí una medida entera no negativa y mostrá que baja estrictamente en cada llamada. Puede ser la longitud de una lista, la altura de un árbol o la distancia entre dos índices. Si la medida queda igual o a veces sube, la recursión merece sospecha.

Más a fondo · formalPor qué total es correcta: inducción sobre la longitud

Queremos probar $P(k)$ : para toda lista de longitud $k$ , total devuelve la suma de sus elementos.

Caso base, $k = 0$ . La lista está vacía, la función entra en el if y devuelve $0$ , que es la suma de una lista vacía. $P(0)$ vale.

Paso inductivo. Supongamos $P(k)$ y tomemos una lista de longitud $k + 1$ . No está vacía, así que la función devuelve values[0] + total(values[1:]). El resto tiene longitud $k$ , y por hipótesis inductiva total(values[1:]) es su suma. Entonces el resultado es el primer elemento más la suma del resto, que es la suma de toda la lista. $P(k + 1)$ vale.

Terminación. La longitud es un entero no negativo que baja en exactamente 1 por llamada, así que no puede haber más de $n + 1$ llamadas.

Fijate que la demostración no sigue ninguna ejecución concreta: usa el contrato para la entrada más chica, igual que cuando diseñamos la función.

La ida y la vuelta

Para escribir una función recursiva no hace falta seguir sus llamadas. Para depurarla, sí conviene haberlas visto alguna vez. Cada llamada tiene una fase de ida, donde achica el problema, y otra de vuelta, donde combina resultados.

Antes de seguir, predecí

Al calcular total([4, 7, 2]), ¿cuál es la primera suma que realmente se hace?

Escena 1 — La ida achica, la vuelta suma

paso a paso

Cargando la escena…

Cambiá la cantidad de elementos: la pila siempre llega a un marco por elemento, más el de la lista vacía.

Separar las dos fases ayuda cuando el trabajo tiene que hacerse antes o después de la llamada recursiva. En los recorridos de árboles, esa decisión es la diferencia entre preorden y postorden.

Cuando los datos ya son recursivos

La recursión se vuelve natural cuando los datos también lo son. Un árbol es un nodo con subárboles; una carpeta contiene archivos y otras carpetas; una expresión tiene subexpresiones. El código puede copiar esa forma:

def tree_sum(node):
    return node["value"] + sum(tree_sum(child) for child in node["children"])

Acá ni siquiera hace falta un if para el caso base: una hoja no tiene hijos, sum de nada da 0, y la recursión se corta sola.

Los tres errores posibles

Casi todo bug en una función recursiva es una de las tres piezas rota, y cada una deja un síntoma distinto:

Pieza rota	Síntoma	Cómo encontrarlo
Caso base incompleto	RecursionError sólo con algunas entradas	Probá la entrada más chica y las que se pasan de largo: negativos, vacíos, None
Reducción que no progresa	RecursionError con cualquier entrada	Verificá que la medida baje en cada llamada
Combinación incorrecta	Termina, pero el resultado está mal	Probá el caso que necesita exactamente una llamada

Un orden de pruebas que encuentra la pieza rota rápido: el caso base, después el ejemplo más chico que exige una llamada, y recién entonces uno con varias.

Error común

values[1:] copia la lista en cada llamada

El slice crea una lista nueva de $n - 1$ elementos, después una de $n - 2$ , y así. El tiempo total pasa de $O(n)$ a $O(n^2)$ . Peor: todas esas copias siguen vivas mientras sus marcos esperan, así que la memoria pico también es $O(n^2)$ . La versión con un índice hace el mismo recorrido sin copiar nada:

def total_from(values, start):
    if start == len(values):
        return 0
    return values[start] + total_from(values, start + 1)

Cierre

Autoevaluación

¿Lo entendiste?

¿Cuál de estas NO es una de las piezas de una función recursiva?

total(values[1:]) sobre una lista de n elementos: ¿cuánta memoria usa en el peor momento?

total([]) devuelve 0 como corresponde, pero total([5]) devuelve 10. ¿Qué pieza está rota?

Para demostrar que una recursión termina, ¿qué alcanza?