Quiz: Maîtrise des algorithmes récursifs essentiels — 8 perguntas

1. Quel est le rôle principal d'une fonction récursive dans la résolution d'un problème ?

A. Elle sert uniquement à effectuer des opérations mathématiques simples

B. Elle sert à décomposer un problème en sous-problèmes plus simples pour le résoudre par une succession d'appels

C. Elle exécute une tâche répétitive sans changement dans ses paramètres

D. Elle évite l'utilisation de la mémoire en ne conservant aucune information sur l'état

Answer: (B)

Explicação

La fonction récursive décompose un problème complexe en sous-problèmes plus simples en s'appelant elle-même avec des paramètres modifiés, permettant une résolution étape par étape jusqu'à un cas de base.

2. Quelle est la cause principale qui peut entraîner une erreur de débordement de pile (RecursionError) dans une fonction récursive ?

A. Une erreur dans la logique de réduction du problème, même si un cas de base est présent

B. L'absence ou la mauvaise gestion du cas de base qui empêche la récursion de s’arrêter

C. L'utilisation excessive de la mémoire dans d’autres parties du programme

D. Une mauvaise optimisation de la fonction récursive pour réduire le coût des appels

Answer: (B)

Explicação

L'absence ou la mauvaise gestion du cas de base dans une fonction récursive empêche la récursion de s’arrêter, ce qui peut entraîner un débordement de pile et provoque une RecursionError. Cette erreur se produit lorsque la récursion devient infinie, ce qui est directement lié à l’absence ou à une mauvaise définition du cas de base.

3. Quelle est la définition d'une fonction récursive ?

A. Une fonction qui utilise uniquement des boucles pour répéter ses opérations.

B. Une fonction qui ne nécessite pas de cas de base pour s'arrêter.

C. Une fonction qui ne fait pas d'appels successifs et ne se répète pas.

D. Une fonction qui s'appelle elle-même dans son corps pour traiter un problème.

Answer: (D)

Explicação

Une fonction récursive est une fonction qui, lors de son exécution, s’appelle elle-même dans son corps pour continuer à traiter le problème, ce qui permet de le décomposer en sous-problèmes plus simples.

4. Comment appliquer la relation récursive pour calculer la puissance d’un nombre en programmation récursive ?

A. En utilisant la relation x^n = x * x^{n-1} avec n réduit à chaque appel jusqu’au cas de base où n=0.

B. En utilisant une boucle pour multiplier x par lui-même n fois, sans recours à la récursion.

C. En multipliant le nombre par lui-même jusqu’à l’exposant n, puis en divisant par 2 à chaque étape.

D. En additionnant le nombre x à lui-même n fois, puis en soustrayant 1 à chaque étape.

Answer: (A)

Explicação

La bonne méthode pour appliquer la puissance récursive consiste à utiliser la relation x^n = x * x^{n-1}, en appelant la fonction avec n-1 à chaque étape, jusqu’au cas de base où n=0 et le résultat est 1. Les autres options ne reflètent pas la méthode récursive correcte décrite dans le contenu.

5. Qui est crédité d'avoir formulé ou développé la méthode appelée 'multiplication russe' ?

A. Cette méthode a été proposée par un ingénieur russe au XXe siècle.

B. Elle a été formulée par un mathématicien russe au XIXe siècle.

C. Elle a été inventée par un inventeur français au XVIIIe siècle.

D. Elle tire son origine d'une méthode ancienne utilisée en Russie.

Answer: (D)

Explicação

La méthode appelée 'multiplication russe' est une technique ancienne qui a été utilisée en Russie, d'où son nom. Le texte indique que cette méthode repose sur une décomposition par division et doublement, et est connue sous le nom 'multiplication russe', ce qui suggère une origine géographique plutôt qu’un auteur précis. La réponse 1 reflète cette attribution.

6. Comment la récursivité se distingue-t-elle fondamentalement d'une boucle itérative dans la résolution de problèmes ?

A. La récursivité utilise une structure de données différente de celle utilisée par la boucle.

B. La récursivité implique que la fonction s'appelle elle-même, tandis qu'une boucle répète une série d'instructions sans appel à elle-même.

C. La récursivité est toujours plus efficace que l'itération pour résoudre n'importe quel problème.

D. La récursivité ne nécessite pas de cas de base, contrairement à la boucle qui doit toujours avoir une condition d'arrêt.

Answer: (B)

Explicação

La récursivité repose sur le fait qu'une fonction s'appelle elle-même pour décomposer le problème en sous-problèmes jusqu'à atteindre un cas de base, tandis qu'une boucle répète une série d'instructions sans appel à elle-même, utilisant une condition d'arrêt pour sortir de la répétition.

7. Quel est le nombre minimal de déplacements requis pour résoudre le problème des tours de Hanoï avec n disques, selon la formule mentionnée dans le texte ?

A. n^2

B. n log n

C. 2^n - 1

D. 2^n + 1

Answer: (C)

Explicação

La formule donnée dans le texte indique que le nombre minimal de déplacements pour n disques est 2^n - 1. Les autres options sont des expressions mathématiques plausibles mais incorrectes dans ce contexte, conçues pour tester la précision de la connaissance de la formule.

8. Quelle caractéristique est essentielle pour qu'une fonction récursive fonctionne correctement ?

A. Elle doit appeler une autre fonction sans condition

B. Elle doit produire un résultat immediately sans appel

C. Elle doit utiliser une boucle pour répéter l'action

D. Elle doit comporter un cas de base qui arrête la récursion

Answer: (D)

Explicação

Une fonction récursive doit comporter un cas de base pour arrêter la récursion, évitant ainsi une boucle infinie. La source insiste sur l'importance d'une condition d'arrêt claire pour assurer la terminaison.