Lua Academy · Aula

Recursão em Lua

Implemente algoritmos recursivos e compreenda a otimização de chamadas finais do Lua.

Recursão em Lua é uma aula grátis de Lua Academy no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Lua Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Lua Academy inclui 4 aulas no total.

O que é Recursão?

Recursão ocorre quando uma função chama a si mesma para resolver uma instância menor do mesmo problema. Toda função recursiva precisa de um caso-base (em que para) e de um caso recursivo (em que reduz o problema). Sem um caso-base, a recursão causa um estouro da pilha.

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!

Fatorial

O fatorial é o exemplo clássico de recursão: n! = n × (n-1)!, com o caso-base 0! = 1. Cada chamada reduz n em 1 até alcançar o caso-base. Os resultados são "desempilhados" de volta pela pilha de chamadas, sendo multiplicados nesse processo.

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

A sequência de Fibonacci é outro exemplo clássico: fib(n) = fib(n-1) + fib(n-2). A recursão ingênua é exponencial — ela recalcula os mesmos valores repetidamente. Veremos a memoização como solução, mas primeiro analisaremos a 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

Recursão com Memoização

A memoização armazena em cache resultados calculados anteriormente em uma tabela. A cada chamada, verifique primeiro o cache. Se o valor estiver lá, retorne-o imediatamente. Caso contrário, calcule-o e armazene-o. Isso transforma o tempo exponencial de Fibonacci em tempo linear.

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!)

Otimização de Chamadas em Cauda

Lua realiza otimização de chamadas em cauda (TCO): quando a última ação de uma função é uma chamada a outra função, Lua reutiliza o quadro atual da pilha. Isso faz com que funções recursivas em cauda usem espaço O(1) na pilha. Nem toda recursão é recursão em cauda — a chamada precisa ser a última coisa na função.

-- 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

Percurso de Árvores

A recursão expressa naturalmente o percurso de árvores. Uma árvore é uma tabela com os campos value, left e right. Os percursos em pré-ordem, em-ordem e pós-ordem diferem apenas no momento em que o valor é processado em relação às chamadas 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

Recursão Mútua

Duas funções podem chamar uma à outra (recursão mútua). Em Lua, você precisa de declarações antecipadas: declare primeiro as variáveis locais e depois atribua as funções. Dessa forma, cada função pode referenciar a variável da outra, que já está no escopo.

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

Cópia Profunda Recursiva

A recursão é ideal para operações em estruturas aninhadas. Fazer uma cópia profunda de uma tabela significa copiar seu conteúdo e copiar recursivamente todas as tabelas aninhadas (para que modificar a cópia não afete a 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 Preenchimento por Inundação

O preenchimento por inundação (usado em programas de pintura e mapas de jogos) é naturalmente recursivo. Começando por uma célula, marque-a e depois preencha recursivamente cada vizinha ainda não visitada. A recursão termina quando encontra limites ou células já 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

Atenção à Profundidade da Pilha

A pilha de chamadas padrão de Lua é limitada (normalmente cerca de 200 níveis para chamadas que não são em cauda). Uma recursão profunda que não seja em cauda causa um erro de "estouro da pilha". Soluções: convertê-la em recursão em cauda, usar uma pilha explícita (tabela) ou usar corrotinas para tarefas 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

Verificação Rápida

Qual das opções a seguir é uma chamada em cauda adequada em Lua?

Recapitulação: Recursão

Resumo:

Toda função recursiva precisa de um caso-base e de um caso recursivo
As chamadas em cauda (quando a última ação é uma chamada) são otimizadas por Lua — pilha O(1)
A memoização transforma a recursão exponencial em linear
A recursão mútua exige declarações antecipadas
A recursão profunda em árvores/grafos é natural; observe a profundidade da pilha em chamadas que não são em cauda

Perguntas Frequentes

A aula “Recursão em Lua” é grátis?

Sim — o texto completo de “Recursão em Lua” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Lua Academy, atualize para CoddyKit PRO. O curso de Lua Academy inclui 4 aulas no total.

O que vou aprender em “Recursão em Lua”?

Implemente algoritmos recursivos e compreenda a otimização de chamadas finais do Lua. Você pratica Lua Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar Lua Academy?

Nenhuma experiência prévia é necessária. Lua Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.

Quanto tempo leva a aula “Recursão em Lua”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de Lua Academy?

Sim. Cada aula de Lua Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

← Voltar para Lua Academy