La récursivité est une sorte d'appel de fonction dans lequel une fonction s'appelle elle-même. Ces fonctions sont également appelées fonctions récursives. La récursivité structurelle est une méthode de résolution de problèmes où la solution à un problème dépend de solutions à de plus petites instances du même problème.

Le terme récursivité décrit une structure de code dans laquelle une fonction s'appelle potentiellement. Ces fonctions sont également appelées fonctions récursives.

La récursivité structurelle est une méthode de résolution de problèmes où la solution à un problème dépend de solutions à des instances plus petites ou plus simples du même problème.

En informatique, une fonction récursive s'appelle directement ou indirectement, par exemple lorsque plusieurs fonctions mutuellement récursives fonctionnent ensemble. Une récursivité ne peut pas être sans fin, chaque niveau de récursivité nécessite de la mémoire. C'est la raison pour laquelle les fonctions récursives ont besoin de conditions pour ne pas s'appeler, donc une fonction récursive s'appelle potentiellement elle-même mais pas inconditionnellement.

Certains langages de programmation fonctionnels ne définissent aucune construction en boucle, mais reposent uniquement sur la récursivité pour appeler à plusieurs reprises du code. De même, dans les langages qui fournissent des boucles, il est possible d'écrire n'importe quelle fonction récursive à l'aide de boucles sans nécessiter de récursivité.

Cela définit deux approches de base pour appeler à plusieurs reprises un morceau de code.

  • Approche itérative (Utilisation de constructions de boucles)
  • Approche récursive (utilisation de la récursivité)

En plus du code du programme, la récursivité peut également se produire dans les structures de données, où un objet ou un tableau imbriqué peut contenir une référence à un élément plus haut dans l'arborescence des données.

Exemples en plusieurs langues

C

void recursiveFunction(int num) {
   if (num < 4)
      recursiveFunction(num + 1);
   printf("%d\n", num);
}

C ++

void recursiveFunction(int num) {
   if (num < 4)
      recursiveFunction(num + 1);
   cout<<num;
}

Java

public static int factorial(int N) { 
   if (N == 1) return 1; 
   return N * factorial(N-1); 
}

OCaml

let rec factorial n =
    if n <= 1 then 1 else n * factorial (n - 1)

Haskell

factorial n = if n == 0 then 1 else n * factorial (n - 1)

Perl

sub factorial {
  if ($_[0] > 1) {
    return $_[0] * &factorial($_[0] - 1);
  } else {
    return 1;
  }
}

Haxe

function factorial(num:Int) { 
   if (num == 1) return 1; 
   return num * factorial(num - 1); 
}

Python (2 ou 3)

def factorial(n):
    return 1 if n <= 1 else n * factorial(n - 1)

Utilisation des balises

La recursiondoit être utilisée pour les problèmes liés à la programmation lors de l'utilisation de la récursivité dans n'importe quel langage de programmation. Sur Stack Overflow, veuillez éviter les questions théoriques telles que "comment fonctionne la récursivité?"

Les références

Plus d'informations