Lua Academy · Leçon

Récursivité en Lua

Implémentez des algorithmes récursifs et comprenez l’optimisation des appels terminaux de Lua.

Récursivité en Lua est une leçon Lua Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Lua Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Lua Academy comprend 4 leçons au total.

Qu'est-ce que la récursion ?

La récursion se produit lorsqu'une fonction s'appelle elle-même pour résoudre une instance plus petite du même problème. Toute fonction récursive a besoin d'un cas de base (où elle s'arrête) et d'un cas récursif (où elle réduit le problème). Sans cas de base, la récursion provoque un dépassement de la pile.

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!

Factorielle

La factorielle est l'exemple classique de récursion : n! = n × (n-1)!, avec le cas de base 0! = 1. Chaque appel réduit n de 1 jusqu'à atteindre le cas de base. Les résultats « remontent » ensuite la pile d'appels en se multipliant au passage.

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 suite de Fibonacci est un autre exemple classique : fib(n) = fib(n-1) + fib(n-2). La récursion naïve est exponentielle : elle recalcule plusieurs fois les mêmes valeurs. Nous verrons la mémoïsation comme solution, mais commençons par la forme de 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

Récursion avec mémoïsation

La mémoïsation met en cache les résultats déjà calculés dans une table. À chaque appel, vérifiez d'abord le cache. Si la valeur s'y trouve, retournez-la immédiatement. Sinon, calculez-la et stockez-la. Cela transforme le temps d'exécution exponentiel de Fibonacci en temps linéaire.

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

Optimisation des appels terminaux

Lua effectue une optimisation des appels terminaux (TCO) : lorsque la dernière action d'une fonction est un appel à une autre fonction, Lua réutilise le cadre de pile actuel. Ainsi, les fonctions récursives terminales utilisent un espace de pile O(1). Toute récursion n'est pas terminale : l'appel doit être la dernière action de la fonction.

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

Parcours d'arbre

La récursion exprime naturellement le parcours d'un arbre. Un arbre est une table possédant les champs value, left et right. Les parcours préfixe, infixe et postfixe ne diffèrent que par le moment où la valeur est traitée par rapport aux appels récursifs.

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

Récursion mutuelle

Deux fonctions peuvent s'appeler mutuellement. En Lua, vous devez effectuer des déclarations anticipées : déclarez d'abord les variables locales, puis affectez les fonctions. Ainsi, chaque fonction peut référencer la variable de l'autre, qui se trouve déjà dans sa portée.

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

Copie profonde récursive

La récursion convient parfaitement aux opérations sur des structures imbriquées. Copier profondément une table signifie copier son contenu et copier récursivement les tables imbriquées (afin que la modification de la copie n'affecte pas l'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)

Algorithme de remplissage par propagation

Le remplissage par propagation (utilisé dans les programmes de peinture et les cartes de jeux) se prête naturellement à la récursion. En partant d'une cellule, marquez-la, puis remplissez récursivement chaque voisine non visitée. La récursion s'arrête lorsqu'elle atteint les limites ou des cellules déjà visitées.

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

Surveiller la profondeur de la pile

La pile d'appels par défaut de Lua est limitée (généralement à environ 200 niveaux pour les appels non terminaux). Une récursion non terminale profonde provoque une erreur de « dépassement de la pile ». Solutions : la convertir en récursion terminale, utiliser une pile explicite (table) ou utiliser des coroutines pour les tâches itératives volumineuses.

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

Vérification rapide

Laquelle des expressions suivantes constitue un appel terminal correct en Lua ?

Récapitulatif : récursion

Résumé :

Toute fonction récursive a besoin d'un cas de base et d'un cas récursif
Les appels terminaux (dont la dernière action est un appel) sont optimisés par Lua — pile O(1)
La mémoïsation transforme une récursion exponentielle en récursion linéaire
La récursion mutuelle nécessite des déclarations anticipées
La récursion profonde sur les arbres ou les graphes est naturelle ; surveillez la profondeur de la pile pour les appels non terminaux

Questions Fréquemment Posées

La leçon « Récursivité en Lua » est-elle gratuite ?

Oui — le texte complet de « Récursivité en Lua » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Lua Academy, passe à CoddyKit PRO. Le cours Lua Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Récursivité en Lua » ?

Implémentez des algorithmes récursifs et comprenez l’optimisation des appels terminaux de Lua. Tu pratiques Lua Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Lua Academy ?

Aucune expérience préalable n'est requise. Lua Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.

Combien de temps prend la leçon « Récursivité en Lua » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Lua Academy ?

Oui. Chaque leçon Lua Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

← Retour à Lua Academy