0Pricing
Lua Academy · Lección

Recursión en Lua

Implemente algoritmos recursivos y comprenda la optimización de llamadas finales de Lua.

Recursión en Lua es una lección gratuita de Lua Academy en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Lua Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Lua Academy incluye 4 lecciones en total.

¿Qué es la recursión?

La recursión ocurre cuando una función se llama a sí misma para resolver una instancia más pequeña del mismo problema. Toda función recursiva necesita un caso base (donde se detiene) y un caso recursivo (donde reduce el problema). Sin un caso base, la recursión provoca un desbordamiento de pila.

local function countdown(n)
  if n <= 0 then
    print("Blast off!")
    return
  end
  print(n)
  countdown(n - 1)
end

countdown(5)
-- 5, 4, 3, 2, 1, Blast off!

Factorial

El factorial es el ejemplo clásico de recursión: n! = n × (n-1)!, con el caso base 0! = 1. Cada llamada reduce n en 1 hasta alcanzar el caso base. Los resultados se «deshacen» por la pila de llamadas y se multiplican a medida que regresan.

local function factorial(n)
  if n <= 1 then return 1 end
  return n * factorial(n - 1)
end

print(factorial(1))   -- 1
print(factorial(5))   -- 120
print(factorial(10))  -- 3628800

Fibonacci

La sucesión de Fibonacci es otro ejemplo clásico: fib(n) = fib(n-1) + fib(n-2). La recursión ingenua tiene un coste exponencial, ya que recalcula los mismos valores repetidamente. Veremos la memoización como solución, pero primero estudiaremos la forma básica.

local function fib(n)
  if n <= 1 then return n end
  return fib(n - 1) + fib(n - 2)
end

for i = 0, 10 do
  io.write(fib(i) .. " ")
end
print()
-- 0 1 1 2 3 5 8 13 21 34 55

Recursión con memoización

La memoización almacena en caché los resultados calculados previamente en una tabla. En cada llamada, compruebe primero la caché. Si el valor está allí, devuélvalo inmediatamente. De lo contrario, calcúlelo y guárdelo. Esto convierte el tiempo exponencial de Fibonacci en tiempo lineal.

local memo = {}
local function fib(n)
  if memo[n] then return memo[n] end
  if n <= 1 then return n end
  local result = fib(n-1) + fib(n-2)
  memo[n] = result
  return result
end

print(fib(40))  -- 102334155  (fast!)

Optimización de llamadas en cola

Lua realiza optimización de llamadas en cola (TCO): cuando la última acción de una función es llamar a otra función, Lua reutiliza el marco de pila actual. Esto hace que las funciones recursivas de cola usen un espacio de pila O(1). No toda recursión es recursión de cola: la llamada debe ser lo último que haga la función.

-- Tail-recursive factorial using accumulator
local function factTail(n, acc)
  acc = acc or 1
  if n <= 1 then return acc end
  return factTail(n - 1, n * acc)  -- tail call
end

print(factTail(10))  -- 3628800
-- Can handle very large n without stack overflow

Recorrido de árboles

La recursión expresa de forma natural el recorrido de árboles. Un árbol es una tabla con los campos value, left y right. Los recorridos en preorden, inorden y postorden solo se diferencian en el momento en que se procesa el valor con respecto a las llamadas recursivas.

local function inorder(node)
  if node == nil then return end
  inorder(node.left)
  io.write(node.value .. " ")
  inorder(node.right)
end

local tree = {
  value=4,
  left={value=2, left={value=1}, right={value=3}},
  right={value=6, left={value=5}, right={value=7}}
}
inorder(tree)  -- 1 2 3 4 5 6 7

Recursión mutua

Dos funciones pueden llamarse entre sí (recursión mutua). En Lua, necesita declaraciones anticipadas: declare primero las variables locales y luego asigne las funciones. De este modo, cada función puede hacer referencia a la variable de la otra, que ya se encuentra en el ámbito.

local isEven, isOdd

isEven = function(n)
  if n == 0 then return true end
  return isOdd(n - 1)
end

isOdd = function(n)
  if n == 0 then return false end
  return isEven(n - 1)
end

print(isEven(10))  -- true
print(isOdd(7))    -- true

Copia profunda recursiva

La recursión es ideal para trabajar con estructuras anidadas. Copiar profundamente una tabla significa copiar su contenido y copiar recursivamente las tablas anidadas (para que modificar la copia no afecte al original).

local function deepCopy(orig)
  local copy
  if type(orig) == "table" then
    copy = {}
    for k, v in pairs(orig) do
      copy[deepCopy(k)] = deepCopy(v)
    end
    setmetatable(copy, getmetatable(orig))
  else
    copy = orig
  end
  return copy
end

local a = {1, {2, 3}}
local b = deepCopy(a)
b[2][1] = 99
print(a[2][1])  -- 2 (unchanged)

Algoritmo de relleno

El relleno (usado en programas de dibujo y mapas de juegos) se implementa de forma natural mediante recursión. A partir de una celda, márquela y luego rellene recursivamente cada vecino que no se haya visitado. La recursión termina cuando alcanza los límites o celdas ya visitadas.

local grid = {
  {0,0,0,1,0},
  {0,1,0,1,0},
  {0,1,1,1,0},
  {0,0,0,0,0},
}

local function fill(g, r, c)
  if r<1 or r>#g or c<1 or c>#g[r] then return end
  if g[r][c] ~= 0 then return end
  g[r][c] = 2  -- mark visited
  fill(g,r-1,c); fill(g,r+1,c)
  fill(g,r,c-1); fill(g,r,c+1)
end

fill(grid, 1, 1)
print(grid[1][1], grid[2][1])  -- 2  2

Control de la profundidad de la pila

La pila de llamadas predeterminada de Lua es limitada (normalmente, unos 200 niveles para llamadas que no son de cola). Una recursión profunda que no sea de cola provoca un error de «desbordamiento de pila». Algunas soluciones son convertirla en recursión de cola, usar una pila explícita (una tabla) o usar corrutinas para tareas iterativas grandes.

-- Simulate deep recursion danger
local function depth(n)
  if n == 0 then return "done" end
  return depth(n - 1)  -- tail call, safe
end
print(depth(100000))  -- done  (tail call, no overflow)

-- Non-tail: limited depth
local function countDown(n)
  if n == 0 then return 0 end
  return 1 + countDown(n - 1)  -- NOT a tail call
end
-- countDown(10000) would stack overflow

Comprobación rápida

¿Cuál de las siguientes es una llamada en cola correcta en Lua?

Repaso: recursión

Resumen:

  • Toda función recursiva necesita un caso base y un caso recursivo
  • Lua optimiza las llamadas en cola (cuando la última acción es una llamada), con una pila O(1)
  • La memoización convierte la recursión exponencial en lineal
  • La recursión mutua requiere declaraciones anticipadas
  • La recursión profunda en árboles o grafos es natural; controle la profundidad de la pila en las llamadas que no sean de cola

Preguntas frecuentes

¿La lección «Recursión en Lua» es gratis?

Sí — el texto completo de «Recursión en Lua» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Lua Academy, actualiza a CoddyKit PRO. El curso de Lua Academy incluye 4 lecciones en total.

¿Qué aprenderé en «Recursión en Lua»?

Implemente algoritmos recursivos y comprenda la optimización de llamadas finales de Lua. Practicas Lua Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar Lua Academy?

No se requiere experiencia previa. Lua Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.

¿Cuánto tiempo toma la lección «Recursión en Lua»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de Lua Academy?

Sí. Cada lección de Lua Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

  1. Definición y llamada de funciones
  2. Múltiples valores de retorno
  3. Varargs y el operador ...
  4. Recursión en Lua
← Volver a Lua Academy