La récursivité

La récursivité désigne le fait pour une fonction de s’appeler elle-même.
C’est une méthode souvent utilisée pour résoudre des problèmes qui peuvent être décomposés en sous-problèmes similaires.

Dans l’exemple suivant, la fonction fact s’appelle elle-même jusqu’à atteindre le cas de base fact(0) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function fact(n)
  if n == 0 then
    return 1
  end

  return n * fact(n - 1)
end

print(fact(7))

-- output :
--  5040

Ici, le calcul effectué est :

1

7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040

Il est important de toujours définir un cas de base (if n == 0 then return 1 end) pour éviter une récursion infinie.