Français
Menu

Qu'est-ce que Récursion (récursivité) ?

Le fait qu'une fonction s'appelle elle-même au cours de son propre traitement. Le problème est découpé en problèmes plus petits de même forme, et les appels s'arrêtent sur un cas qui n'est plus découpé (le cas de base). Chaque appel occupe de l'espace sur la pile, si bien qu'une récursion trop profonde provoque un débordement de pile. La récursion terminale, dans laquelle l'appel récursif est la dernière action de la fonction, peut être transformée en boucle.

Nom japonais: 再帰

« Récursion (récursivité) » apparaît dans 12 questions d'entraînement réparties sur 6 thèmes, dont Structures de données et algorithmes, Éditeurs de liens, chargeurs et exécutables, Bases de la programmation (trace de pseudo-code).

Domaine: Structures de données et algorithmes

S'entraîner : questions sur Récursion (récursivité)

Lorsqu'une récursion trop profonde dépasse la limite de la pile, que se passe-t-il généralement sous Linux notamment ?

  1. ALe programme touche la page de garde à accès interdit située au-delà de la pile et se termine anormalement
  2. BL'OS déplace automatiquement la pile sur disque, permettant une récursion de profondeur illimitée
  3. CLes anciens cadres de pile sont automatiquement effacés et le calcul se poursuit correctement
Afficher la réponse et l'explication

Réponse : A. Le programme touche la page de garde à accès interdit située au-delà de la pile et se termine anormalement

La pile a une limite, au-delà de laquelle se trouve une page de garde à accès interdit. Si une récursion trop profonde amène la pile jusqu'à cette page, un défaut de page survient et l'OS arrête le programme (erreur de segmentation). L'avantage de la page de garde est d'arrêter le programme avant qu'il ne corrompe d'autres données. Déclarer un grand tableau en variable locale produit le même effet ; il est donc plus sûr de placer les grandes données dans le tas.

Dans un graphe non orienté, les voisins de chaque sommet sont A : B, C / B : A, D, E / C : A, F / D : B / E : B, F / F : C, E. Un parcours en profondeur par récursion part du sommet A. Les voisins sont examinés dans l'ordre indiqué, et dès qu'un sommet non visité est trouvé, le parcours s'y déplace. Dans quel ordre les sommets sont-ils visités ?

  1. AA, B, C, D, E, F
  2. BA, B, D, E, C, F
  3. CA, B, D, E, F, C
Afficher la réponse et l'explication

Réponse : C. A, B, D, E, F, C

Depuis A, le parcours passe à B, puis à D, le premier voisin non visité de B. Le seul voisin de D, B, est déjà visité : le parcours revient donc à B et passe à E, puis de E au sommet non visité F, et de F à son voisin C. L'ordre est donc A, B, D, E, F, C. A, B, C, D, E, F est l'ordre du parcours en largeur, qui visite d'abord les sommets les plus proches. A, B, D, E, C, F revient en arrière depuis E sans aller au sommet non visité F : ce n'est donc pas un ordre de parcours en profondeur.

« Récursion (récursivité) » dans les explications

Questions mentionnant « Récursion (récursivité) » (12)

  1. Lorsqu'une récursion trop profonde dépasse la limite de la pile, que se passe-t-il généralement sous Linux notamment ?
  2. Dans un graphe non orienté, les voisins de chaque sommet sont A : B, C / B : A, D, E / C : A, F / D : B / E : B, F / F : C, E. Un parcours en profondeur par récursion part du sommet A. Les voisins sont examinés dans l'ordre indiqué, et dès qu'un sommet non visité est trouvé, le parcours s'y déplace. Dans quel ordre les sommets sont-ils visités ?
  3. Une fonction fib(n) qui calcule les nombres de Fibonacci est définie par récursion : « si n vaut 1 ou moins, renvoyer n ; sinon, renvoyer fib(n−1) + fib(n−2) ». Quand on appelle fib(5), combien de fois fib est-elle appelée, premier appel compris ?
  4. Quelle zone est généralement utilisée pour sauvegarder temporairement l'adresse de retour, entre autres, lors de l'appel d'un sous-programme (fonction) ?
  5. Quel effet produit l'optimisation des appels terminaux appliquée au dernier appel récursif de la fonction ci-dessus ?
  6. Où est placée pendant l'exécution une variable locale (variable automatique) sans static déclarée dans une fonction C ?
  7. Quel est l'avantage de l'agencement qui fait croître le tas et la pile d'un processus en sens opposés, avec un vaste espace libre entre eux ?
  8. Dans un graphe dont les arêtes n'ont pas de poids, on veut trouver le plus petit nombre d'arêtes entre un sommet de départ et chacun des autres sommets. Quelle association entre méthode de recherche et structure de données convient ?
  9. Une fonction f(x, y) est définie par « si y vaut 0, renvoyer x ; sinon, renvoyer f(y, x mod y) ». Quand on appelle f(84, 36), quelle est la valeur renvoyée, et combien de fois f est-elle appelée, premier appel compris ?
  10. ÷ est la division ; quand le résultat est affecté à une variable entière (y compris un argument de fonction), la partie fractionnaire est supprimée. Lorsque la fonction pow suivante est appelée sous la forme pow(2, 10), combien de fois pow est-elle appelée, premier appel compris ?
  11. Quelle est la valeur de retour de la fonction fib suivante appelée sous la forme fib(10) ?
  12. int fait 32 bits (valeur maximale 2147483647). Quelle est la plus grande valeur de n pour laquelle la fonction fact(n) ci-dessus renvoie correctement la factorielle de n, sans dépassement de capacité ?

Termes associés

Pile (stack) Variable Argument Tableau Tas (heap) Parcours en profondeur (depth-first search) Parcours en largeur (breadth-first search) Pointeur de pile Cadre de pile (stack frame) Valeur de retour

Retour au glossaire