Récursivité et fonctionnement de la pile d’appels

Audio automatique activé : les prochaines questions seront lues quand vous cliquerez sur Continuer.

1. 1

   Quel est le rôle principal d’un cas de base dans une fonction récursive ?

   A Arrêter les appels récursifs lorsqu’un cas suffisamment simple est atteint B Répéter automatiquement chaque appel un nombre fixe de fois C Supprimer les paramètres transmis à la fonction
2. 2

   Une fonction f(n) appelle f(n − 1) jusqu’à f(0). Lorsque f(0) vient d’être appelée depuis f(3), quel est l’ordre des cadres dans la pile, du bas vers le haut ?

   

   A f(0), f(1), f(2), f(3) B f(3), f(2), f(1), f(0) C f(3), f(1), f(2), f(0)
3. 3

   Quelle définition récursive calcule correctement la factorielle d’un entier n supérieur ou égal à 0 ?

   A fact(0) = 0 et fact(n) = n + fact(n − 1) B fact(0) = 1 et fact(n) = fact(n − 1) − n C fact(0) = 1 et fact(n) = n × fact(n − 1)
4. 4

   Même lorsqu’un cas de base est présent, dans quelle situation une récursion peut-elle ne jamais l’atteindre ?

   A L’argument évolue dans une direction qui l’éloigne du cas de base B La fonction possède une variable locale C Le cas de base renvoie une valeur constante
5. 5

   Considérez somme(n) : si n = 0, renvoyer 0 ; sinon, renvoyer n + somme(n − 1). Que vaut somme(4) ?

   A 6 B 10 C 16
6. 6

   Quel affichage produit l’appel compte(3) ?
   
   compte(n) :
   si n = 0, retourner
   afficher n
   compte(n − 1)

   

   A 1, 2, 3 B 3, 2, 1, 0 C 3, 2, 1
7. 7

   Si l’instruction « afficher n » est déplacée après l’appel récursif dans compte(n), quel affichage produit compte(3) ?

   A 1, 2, 3 B 3, 2, 1 C 0, 1, 2, 3
8. 8

   Quelles informations trouve-t-on généralement dans le cadre d’activation d’un appel de fonction ?

   

   A Uniquement le nom de la fonction B Les paramètres, les variables locales et les informations de retour C Toutes les variables de tous les programmes exécutés
9. 9

   Qu’est-ce qu’un appel récursif terminal ?

   A Un appel qui apparaît uniquement dans le cas de base B Un appel effectué deux fois avec les mêmes paramètres C Un appel récursif après lequel aucune opération supplémentaire n’est nécessaire
10. 10

    Sans mémoïsation, quelle est la nature de la complexité temporelle de l’algorithme récursif naïf de Fibonacci ?

    A Exponentielle B Logarithmique C Constante
11. 11

    Dans l’arbre complet des appels de fib(4), avec fib(0) et fib(1) comme cas de base, combien d’appels sont effectués au total ?

    

    A 7 B 9 C 11
12. 12

    La fonction fact(5) appelle successivement fact(4) jusqu’à fact(0). Quel est le nombre maximal de cadres de factorielle présents simultanément dans la pile ?

    

    A 4 B 5 C 6
13. 13

    Une fonction récursive additionne les n éléments d’un tableau en traitant exactement un élément par appel. Quelle est sa complexité temporelle ?

    A O(n) B O(log n) C O(n²)
14. 14

    Une recherche dichotomique récursive réduit un intervalle de 16 éléments à 8, puis 4, 2 et 1 élément. Combien de divisions par deux ont été réalisées ?

    

    A 3 B 4 C 5
15. 15

    Que désigne la récursivité mutuelle ?

    A Une fonction qui s’appelle deux fois dans la même instruction B Deux exécutions indépendantes d’une même fonction C Plusieurs fonctions qui s’appellent récursivement les unes les autres
16. 16

    Pour une fonction récursive qui vérifie un palindrome en comparant les caractères aux deux extrémités, quel est un cas de base valide ?

    

    A Il reste zéro ou un caractère à examiner B Les deux premiers caractères sont identiques C La chaîne contient au moins deux caractères
17. 17

    Une récursion possède un cas de base correct, mais la profondeur requise peut atteindre plusieurs millions d’appels. Quelle transformation réduit le mieux le risque de débordement de pile ?

    A Ajouter davantage de variables locales à chaque appel B Remplacer la récursion par une solution itérative utilisant une boucle C Déplacer le cas de base après l’appel récursif
18. 18

    Dans quel ordre un parcours récursif préfixe visite-t-il les parties d’un arbre binaire ?

    

    A Sous-arbre gauche, racine, sous-arbre droit B Sous-arbre gauche, sous-arbre droit, racine C Racine, sous-arbre gauche, sous-arbre droit
19. 19

    Quel effet la mémoïsation produit-elle sur le calcul récursif de Fibonacci jusqu’à fib(n) ?

    

    A Elle mémorise chaque résultat et ramène généralement le temps à O(n) B Elle supprime les cas de base et rend le temps constant C Elle augmente volontairement le nombre d’appels récursifs