Les algorithmes récurrents : cas de base, appels et complexité

Question 1 sur 5 10:00

[{"id":2335,"question":"Quel est le cas de base dans la fonction récursive calculant la factorielle d'un nombre n ?","option_a":"Si n = 0, retourner 1","option_b":"Si n = 1, retourner 1","option_c":"Si n = 0, retourner 0","option_d":"Si n = 1, retourner 0","option_e":"","option_f":"","bonne_reponse":"A","explication":"Le cas de base pour la factorielle est n = 0 (ou n = 1), car 0! = 1 et 1! = 1. Cela permet d'arrêter la récursion et d'éviter une pile infinie.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":2336,"question":"Quelle est la complexité temporelle de l'algorithme récursif pour calculer la suite de Fibonacci sans optimisation ?","option_a":"O(1)","option_b":"O(n)","option_c":"O(2^n)","option_d":"O(n log n)","option_e":"","option_f":"","bonne_reponse":"C","explication":"Sans optimisation (mémoïsation), chaque appel récursif pour Fibonacci(n) génère deux appels récursifs supplémentaires, ce qui conduit à une complexité exponentielle O(2^n).","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":2337,"question":"Quel problème classique illustre parfaitement l'utilisation de la récursivité pour réduire un problème en sous-problèmes plus simples ?","option_a":"Le tri par sélection","option_b":"La tour de Hanoï","option_c":"Le tri à bulles","option_d":"La recherche linéaire","option_e":"","option_f":"","bonne_reponse":"B","explication":"La tour de Hanoï est un problème emblématique où la récursivité permet de décomposer le problème en déplaçant n-1 disques vers un pilier intermédiaire, puis en déplaçant le disque restant vers la destination finale.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":2338,"question":"Quelle technique permet d'optimiser une fonction récursive en évitant les calculs redondants ?","option_a":"La programmation dynamique","option_b":"La mémoïsation","option_c":"L'itération","option_d":"Le tri rapide","option_e":"","option_f":"","bonne_reponse":"B","explication":"La mémoïsation consiste à stocker les résultats des appels récursifs dans un tableau ou une structure de données pour éviter de les recalculer, réduisant ainsi la complexité.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":2339,"question":"Dans une fonction récursive, que se passe-t-il si le cas de base est mal défini ou absent ?","option_a":"La fonction retourne toujours 0","option_b":"La fonction génère une erreur de type 'NoneType'","option_c":"La fonction entre dans une boucle infinie et provoque un stack overflow","option_d":"La fonction s'exécute correctement mais avec une complexité accrue","option_e":"","option_f":"","bonne_reponse":"C","explication":"L'absence ou l'erreur dans le cas de base empêche l'arrêt de la récursion, ce qui conduit à une pile d'appels infinie et une erreur de stack overflow.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0}]