Implémentation récursive des fonctions C++ : quelles sont les utilisations courantes de la récursion ?

La récursion est une technique dans laquelle une fonction s'appelle elle-même et est largement utilisée dans des scénarios où les problèmes sont résolus étape par étape. En C++, la récursivité a les utilisations courantes suivantes : Résoudre des nombres de Fibonacci Calculer des factorielles Calculer des permutations et des combinaisons Traverser des structures arborescentes Résoudre des problèmes de résolution de labyrinthes

Implémentation récursive des fonctions C++ : Explorez les utilisations courantes de la récursivité en programmation

La récursion est un ordinateur technique scientifique qui permet à une fonction de s'appeler elle-même. Il est largement utilisé dans des scénarios nécessitant une résolution de problèmes étape par étape. Cet article explorera les utilisations courantes de la récursivité en C++ et l'illustrera à travers des cas pratiques.

Utilisation de base : séquence de Fibonacci

L'utilisation récursive la plus simple consiste à trouver la séquence de Fibonacci. Chaque nombre de cette séquence est la somme des deux nombres précédents. L'implémentation spécifique est la suivante :

int fibonacci(int n) {
  if (n <= 1) {
    return 1;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

Factory Calculating

Trouver la factorielle d'un nombre est également une application récursive classique. La factorielle est le résultat de la multiplication de ce nombre par tous les entiers positifs inférieurs à lui.

int factorial(int n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

Permutations et combinaisons

La récursion peut également être utilisée pour calculer des permutations et des combinaisons. Les arrangements sont des manières d'organiser des objets dans un ordre spécifique, tandis que les combinaisons sont des manières d'organiser des objets sans tenir compte de l'ordre.

Permutation :

int permutations(int n, int r) {
  if (r == 0) {
    return 1;
  } else {
    return n * permutations(n - 1, r - 1);
  }
}

Combinaison :

int combinations(int n, int r) {
  if (r == 0 || n == r) {
    return 1;
  } else {
    return combinations(n - 1, r - 1) + combinations(n - 1, r);
  }
}

Traversée de structures arborescentes

La récursion est largement utilisée pour parcourir des structures arborescentes, telles que des arbres et des graphiques.

Parcours de pré-commande d'arbre binaire :

void preorderTraversal(TreeNode* root) {
  if (root != nullptr) {
    std::cout << root->val;
    preorderTraversal(root->left);
    preorderTraversal(root->right);
  }
}

Cas pratique : Résolution de labyrinthe

L'utilisation de la récursivité peut résoudre le problème de résolution de labyrinthe. L'algorithme récursif fonctionne en essayant tous les chemins possibles jusqu'à ce qu'il trouve le chemin vers la sortie.

bool solveMaze(int x, int y, int** maze) {
  if (maze[x][y] == 2) {
    return true;
  } else if (maze[x][y] == 0) {
    return false;
  } else {
    maze[x][y] = 0;
    return solveMaze(x + 1, y, maze) || 
           solveMaze(x, y + 1, maze) || 
           solveMaze(x - 1, y, maze) || 
           solveMaze(x, y - 1, maze);
  }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!