Lua Academy · Lezione

Ricorsione in Lua

Implementi algoritmi ricorsivi e comprenda l'ottimizzazione delle chiamate in coda di Lua.

Ricorsione in Lua è una lezione Lua Academy gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Lua Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Lua Academy include 4 lezioni in totale.

Che cos'è la ricorsione?

La ricorsione si verifica quando una funzione chiama sé stessa per risolvere un'istanza più piccola dello stesso problema. Ogni funzione ricorsiva ha bisogno di un caso base, in cui si arresta, e di un caso ricorsivo, in cui riduce il problema. Senza un caso base, la ricorsione causa un overflow dello stack.

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!

Fattoriale

Il fattoriale è l'esempio classico di ricorsione: n! = n × (n-1)!, con il caso base 0! = 1. Ogni chiamata riduce n di 1 fino a raggiungere il caso base. I risultati vengono poi "riesaminati" risalendo lo stack delle chiamate e moltiplicandoli progressivamente.

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

Successione di Fibonacci

La successione di Fibonacci è un altro esempio classico: fib(n) = fib(n-1) + fib(n-2). La ricorsione ingenua ha complessità esponenziale, perché ricalcola ripetutamente gli stessi valori. Vedremo la memoizzazione come soluzione, ma prima consideriamo la forma di base.

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

Ricorsione con memoizzazione

La memoizzazione memorizza in una tabella i risultati calcolati in precedenza. A ogni chiamata, controllare prima la cache. Se il valore è presente, restituirlo immediatamente. Altrimenti, calcolarlo e memorizzarlo. In questo modo, l'algoritmo di Fibonacci passa da un tempo esponenziale a uno lineare.

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

Ottimizzazione delle chiamate in coda

Lua esegue l'ottimizzazione delle chiamate in coda (TCO): quando l'ultima azione di una funzione è una chiamata a un'altra funzione, Lua riutilizza il frame corrente dello stack. In questo modo, le funzioni ricorsive in coda usano uno spazio nello stack pari a O(1). Non tutte le ricorsioni sono ricorsioni in coda: la chiamata deve essere l'ultima operazione della funzione.

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

Attraversamento di un albero

La ricorsione è particolarmente adatta a esprimere l'attraversamento di un albero. Un albero è una tabella con i campi value, left e right. Gli attraversamenti preorder, inorder e postorder differiscono solo per il momento in cui viene elaborato il valore rispetto alle chiamate ricorsive.

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

Ricorsione reciproca

Due funzioni possono chiamarsi a vicenda, realizzando una ricorsione reciproca. In Lua sono necessarie dichiarazioni anticipate: dichiarare prima le variabili locali e poi assegnare loro le funzioni. In questo modo ogni funzione può fare riferimento alla variabile dell'altra, che è già nell'ambito.

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

La ricorsione è ideale per operare su strutture annidate. Copiare profondamente una tabella significa copiarne il contenuto e copiare ricorsivamente anche le eventuali tabelle annidate, così le modifiche alla copia non influiscono sull'originale.

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

Il flood fill, usato nei programmi di disegno e nelle mappe dei giochi, si presta naturalmente alla ricorsione. Partendo da una cella, la si contrassegna e poi si riempie ricorsivamente ogni vicino non ancora visitato. La ricorsione termina quando raggiunge i bordi o celle già visitate.

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

Gestire la profondità dello stack

Lo stack delle chiamate predefinito di Lua è limitato, in genere a circa 200 livelli per le chiamate non in coda. Una ricorsione non in coda molto profonda causa un errore di "stack overflow". Le soluzioni sono convertirla in ricorsione in coda, usare uno stack esplicito (una tabella) oppure usare le coroutine per attività iterative di grandi dimensioni.

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

Quale delle seguenti è una chiamata in coda corretta in Lua?

Riepilogo: ricorsione

Riepilogo:

Ogni funzione ricorsiva ha bisogno di un caso base e di un caso ricorsivo
Le chiamate in coda, quando l'ultima azione è una chiamata, vengono ottimizzate da Lua e usano uno stack O(1)
La memoizzazione trasforma una ricorsione esponenziale in una lineare
La ricorsione reciproca richiede dichiarazioni anticipate
La ricorsione profonda su alberi o grafi è naturale; prestare attenzione alla profondità dello stack per le chiamate non in coda

Domande Frequenti

La lezione «Ricorsione in Lua» è gratuita?

Sì — il testo completo di «Ricorsione in Lua» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Lua Academy, passa a CoddyKit PRO. Il corso Lua Academy include 4 lezioni in totale.

Cosa imparerò in «Ricorsione in Lua»?

Implementi algoritmi ricorsivi e comprenda l'ottimizzazione delle chiamate in coda di Lua. Eserciti Lua Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Lua Academy?

Non è richiesta alcuna esperienza precedente. Lua Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.

Quanto tempo richiede la lezione «Ricorsione in Lua»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Lua Academy?

Sì. Ogni lezione Lua Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

← Torna a Lua Academy