Cours d’algorithmique de licence 1 toujours. On attaque quelque chose de plus difficile et on rentre dans les questions d’algorithmique avec une fonction récursive. Juste avant, les étudiant⋅es ont travaillé sur la factorielle. Entretien réalisé le 11/02/2025, et complétée le lendemain.

Les nombres de Fibonacci forment une suite F(n) pour n≥0 telle que : F(0) = 0, F(1) = 1, et F(n) = F(n−1) + F(n−2).

  1. Écrivez une fonction récursive fibo pour calculer le n-ième nombre de Fibonacci.
  2. Lancez cette fonction pour de petites, puis de grandes valeurs de n.
  3. Que constatez-vous ?
  4. Expliquez ce constat en listant tous les appels à votre fonction.

La suite de Fibonacci est une suite de nombres dans laquelle chaque nombre est la somme des deux précédents. La définition récursive de la suite de Fibonacci est la suivante :

Ça c’est nouveau : le vampire reformule l’énoncé.

1. Écrire une fonction récursive fibo pour calculer le n-ième nombre de Fibonacci

Voici comment vous pouvez écrire une fonction récursive en Python pour calculer le n-ième nombre de Fibonacci :

Argh, je me suis encore fait avoir en lui laissant choisir le langage. Je coupe la suite et on recommence. (Oui, je vouvoie le vampire, surtout par souci de cohérence avec mon énoncé mais j’imagine bien qu’il s’en fiche de la cohérence à ce niveau.)

Refaites complètement cet exercice en C.

D’accord, refaisons cet exercice en C. Nous allons suivre les mêmes étapes que précédemment : écrire une fonction récursive pour calculer les nombres de Fibonacci, tester cette fonction pour de petites et grandes valeurs, observer les performances, et expliquer les résultats.

De nouveau, le bon élève qui reprend les termes de l’énoncé.

1. Écrire une fonction récursive fibo pour calculer le n-ième nombre de Fibonacci

Voici comment vous pouvez écrire une fonction récursive en C pour calculer le n-ième nombre de Fibonacci :

#include <stdio.h>

int fibo(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibo(n-1) + fibo(n-2);
    }
}

int main() {
    int n = 10; // Exemple avec n = 10
    printf("Fibonacci de %d est %d\n", n, fibo(n));
    return 0;
}

Tout ça est très bien. Je note le vous pouvez écrire, le vampire fait vraiment en sorte qu’on s’approprie son travail.

2. Lancer cette fonction pour de petites, puis de grandes valeurs de n

Pour de petites valeurs de ( n ), la fonction fonctionne bien. Par exemple :

int main() {
    printf("Fibonacci de 5 est %d\n", fibo(5));  // Affiche 5
    printf("Fibonacci de 10 est %d\n", fibo(10)); // Affiche 55
    return 0;
}

Pour de grandes valeurs de ( n ), la fonction devient très lente. Par exemple :

int main() {
    printf("Fibonacci de 30 est %d\n", fibo(30)); // Peut prendre un certain temps
    printf("Fibonacci de 50 est %d\n", fibo(50)); // Peut prendre beaucoup de temps
    return 0;
}

Là je suis surpris : il n’a pas lancé le calcul, évidemment, mais il a directement donné ce qu’on constaterait si on lance le calcul, en des termes tout à fait appropriés. On voit qu’il a bien appris ce problème et le restitue comme il faut.

3. Que constatez-vous ?

Vous constatez que pour de grandes valeurs de n, la fonction devient extrêmement lente. Cela est dû au fait que la fonction récursive effectue de nombreux appels répétitifs, ce qui entraîne une complexité exponentielle.

4. Expliquer ce constat en listant tous les appels à votre fonction

Pour comprendre pourquoi la fonction devient lente, examinons les appels récursifs pour n = 5 :

fibo(5)
  fibo(4) + fibo(3)
    fibo(3) + fibo(2) + fibo(2) + fibo(1)
      fibo(2) + fibo(1) + fibo(1) + fibo(0) + fibo(1) + fibo(0)
        fibo(1) + fibo(0) + fibo(1) + fibo(1) + fibo(0) + fibo(1) + fibo(0)

Vous pouvez voir que fibo(2) est calculé trois fois, fibo(1) est calculé cinq fois, etc. Ce phénomène s’aggrave à mesure que n augmente, car chaque appel à fibo(n) entraîne deux appels supplémentaires à fibo(n-1) et fibo(n-2), ce qui conduit à une explosion combinatoire des appels récursifs.

Son explication est élaborée, il détaille tous les appels, et il donne les bons nombres d’appels pour fibo(2) et fibo(1). Mais la représentation qu’il en fait est fausse, ou alors je ne l’ai pas comprises, et en tout cas elle ne permet pas de compter le nombre d’appels à fibo(1). Voilà comment je lis le bloc ci-dessus :

Donc, soit il reporte des appels qu’il ne faudrait pas reporter, soit il a oublié de reporter l’appel à fibo(1) issu de la 3ème ligne. Dans les deux cas, le résultat ne veut plus rien dire et n’aide en rien à conclure qu’on a 5 appels à fibo(1).

Pour résoudre ce problème, vous pouvez utiliser la mémoïsation (ou memoization en anglais), qui consiste à stocker les résultats des appels précédents pour éviter de les recalculer. Voici comment vous pouvez implémenter cela en C :

#include <stdio.h>

#define MAX 100

int memo[MAX];

int fibo_memo(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = fibo_memo(n-1) + fibo_memo(n-2);
        return memo[n];
    }
}

int main() {
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1; // Initialiser le tableau de mémoïsation
    }
    int n = 50; // Exemple avec n = 50
    printf("Fibonacci de %d est %d\n", n, fibo_memo(n));
    return 0;
}

Avec cette version, les appels répétitifs sont évités, ce qui rend la fonction beaucoup plus efficace pour de grandes valeurs de n.

Alors là il me sort une proposition qu’il avait déjà sortie en Python. Malheureusement en C, ça sera plus compliqué à mettre en œuvre, et je vais l’interroger sur cet aspect parce que pour le reste, l’exercice est terminé.

Mais, notons dès à présent que cette solution est à la fois valide sur le plan technique et stupide sur le plan algorithmique. En effet, pour éviter la combinatoire du problème, la bonne solution consiste à faire le calcul en avant, avec deux variables mémorisant les deux termes précédents, qui suffisent à calculer le terme suivant. Et en aucun cas on n’a besoin d’un tableau mémorisant tous les termes précédents et donc la taille est problématique à définir, comme le vampire l’exposera lui même.

Donc d’un côté, le vampire identifie correctement un problème avec l’algorithme, de l’autre il propose une mauvaise solution dans laquelle il va s’enferrer. Certes, l’énoncé demande une solution récursive. Mais l’énoncé ne demande pas non plus de corriger le problème constaté, juste de l’identifier.

Je commence par une question indirecte.

Que se passe-t-il si on appelle fibo_memo(200) ?

Si vous appelez fibo_memo(200) avec le code fourni précédemment, vous allez rencontrer plusieurs problèmes :

  1. Dépassement de la taille du tableau memo : Le tableau memo est défini avec une taille maximale de 100 (#define MAX 100). Si vous appelez fibo_memo(200), vous allez accéder à des indices du tableau memo qui sont hors des limites, ce qui entraînera un comportement indéfini et probablement un crash du programme.

  2. Dépassement de la capacité des entiers : Les nombres de Fibonacci croissent exponentiellement. Pour n = 200, le nombre de Fibonacci est extrêmement grand. Le type int en C ne peut pas stocker des valeurs aussi grandes. Vous aurez besoin d’utiliser un type de données capable de gérer de très grands entiers, comme unsigned long long ou une bibliothèque pour les grands nombres.

Pour résoudre ces problèmes, vous devez :

  1. Augmenter la taille du tableau memo pour qu’il puisse stocker au moins 200 valeurs.
  2. Utiliser un type de données capable de stocker de très grands entiers.

Voici comment vous pouvez modifier le code pour gérer ces problèmes :

De nouveau, il propose une solution non demandée, et tend des bâtons pour se faire battre. Mais sinon, ses réponses sont correctes.

#include <stdio.h>
#include <stdlib.h>

#define MAX 201

unsigned long long memo[MAX];

unsigned long long fibo_memo(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = fibo_memo(n-1) + fibo_memo(n-2);
        return memo[n];
    }
}

int main() {
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1; // Initialiser le tableau de mémoïsation
    }
    int n = 200; // Exemple avec n = 200
    printf("Fibonacci de %d est %llu\n", n, fibo_memo(n));
    return 0;
}

Explications :

  1. Type unsigned long long : Ce type est utilisé pour stocker les résultats des calculs de Fibonacci, car il peut gérer des valeurs beaucoup plus grandes que le type int.

  2. Taille du tableau memo : La taille du tableau memo est augmentée à 201 pour pouvoir stocker les résultats jusqu’à fibo_memo(200).

Avec ces modifications, le programme devrait être capable de calculer fibo_memo(200) sans dépasser les limites du tableau memo et sans dépasser la capacité des entiers.

On ne va pas le laisser dans cette fuite en avant parce que des entiers j’en ai encore beaucoup en stock et ça va vite devenir répétitif.

Peut-on choisir une taille pour MAX qui garanti qu’on n’aura jamais un débordement de tampon ?

En théorie, vous pouvez choisir une taille pour MAX qui garantit que vous n’aurez jamais de débordement de tampon en fonction de la taille maximale de n que vous prévoyez de traiter. Cependant, il y a plusieurs considérations pratiques à prendre en compte :

  1. Limites de la mémoire : La taille maximale de MAX dépend de la quantité de mémoire disponible sur votre système. Si vous choisissez une valeur très grande pour MAX, vous risquez de consommer trop de mémoire, ce qui peut rendre votre programme inefficace ou même provoquer des erreurs de mémoire.

  2. Limites des types de données : Même avec des types de données capables de stocker de très grands entiers (comme unsigned long long), il y a des limites pratiques à la taille des nombres que vous pouvez manipuler. Par exemple, le type unsigned long long en C peut stocker des valeurs jusqu’à 2⁶⁴ - 1, mais les nombres de Fibonacci croissent exponentiellement et dépassent rapidement cette limite.

  3. Performance : Pour de très grandes valeurs de n, le calcul des nombres de Fibonacci devient très coûteux en termes de temps de calcul, même avec la mémoïsation. Il est important de trouver un équilibre entre la taille de MAX et les performances du programme.

Alors non, on ne peut pas choisir une taille pour MAX qui va garantir contre les débordements de tampons, dès qu’on fixe une taille, il suffit de proposer n plus grand. Mais je comprends le point de vue exposé comme si on connaît n alors on peut choisir MAX, ce qui est aussi incorrect puisque le premier est donné à l’exécution et le second à la compilation. Mais acceptons ça, et alors je suis globalement d’accord avec ces constats. Cependant, il enchaîne de façon absurde en défendant une position qui se résumé à : puisque la mémoïsation ne marche pas, on va continuer à en faire.

Solution pratique

Pour garantir qu’il n’y ait jamais de débordement de tampon, vous pouvez dynamiquement allouer de la mémoire en fonction de la valeur de n que vous souhaitez traiter. Voici comment vous pouvez le faire en C :

#include <stdio.h>
#include <stdlib.h>

unsigned long long *memo;

unsigned long long fibo_memo(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = fibo_memo(n-1) + fibo_memo(n-2);
        return memo[n];
    }
}

int main() {
    int n = 200; // Exemple avec n = 200
    memo = (unsigned long long *)malloc((n + 1) * sizeof(unsigned long long));
    if (memo == NULL) {
        fprintf(stderr, "Erreur d'allocation de mémoire\n");
        return 1;
    }
    for (int i = 0; i <= n; i++) {
        memo[i] = -1; // Initialiser le tableau de mémoïsation
    }
    printf("Fibonacci de %d est %llu\n", n, fibo_memo(n));
    free(memo); // Libérer la mémoire allouée
    return 0;
}

Explications :

  1. Allocation dynamique : Le tableau memo est alloué dynamiquement en fonction de la valeur de n. Cela garantit que vous avez toujours suffisamment de mémoire pour stocker les résultats intermédiaires.

  2. Gestion des erreurs : Si l’allocation de mémoire échoue, le programme affiche un message d’erreur et se termine.

  3. Libération de la mémoire : Après avoir utilisé le tableau memo, la mémoire est libérée pour éviter les fuites de mémoire.

Avec cette approche, vous pouvez garantir qu’il n’y aura jamais de débordement de tampon, tout en utilisant la mémoire de manière efficace.

Il qualifie d’efficace une approche qui consiste à remplir la mémoire avec des tas de valeurs inutiles. Passons.

Essayons de faire un pas de côté pour montrer qu’on veut pouvoir calculer pour vraiment n’importe quel n.

Et si on veut que n puisse être saisi au clavier ?

Si vous souhaitez que la valeur de n puisse être saisie au clavier, vous pouvez utiliser la fonction scanf en C pour lire l’entrée de l’utilisateur. Voici comment vous pouvez modifier le programme pour permettre à l’utilisateur de saisir la valeur de n :

#include <stdio.h>
#include <stdlib.h>

unsigned long long *memo;

unsigned long long fibo_memo(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = fibo_memo(n-1) + fibo_memo(n-2);
        return memo[n];
    }
}

int main() {
    int n;
    printf("Entrez la valeur de n : ");
    if (scanf("%d", &n) != 1) {
        fprintf(stderr, "Erreur de saisie\n");
        return 1;
    }

    memo = (unsigned long long *)malloc((n + 1) * sizeof(unsigned long long));
    if (memo == NULL) {
        fprintf(stderr, "Erreur d'allocation de mémoire\n");
        return 1;
    }

    for (int i = 0; i <= n; i++) {
        memo[i] = -1; // Initialiser le tableau de mémoïsation
    }

    printf("Fibonacci de %d est %llu\n", n, fibo_memo(n));

    free(memo); // Libérer la mémoire allouée
    return 0;
}

Explications :

  1. Lecture de l’entrée utilisateur : La fonction scanf est utilisée pour lire la valeur de n saisie par l’utilisateur. Le format %d est utilisé pour lire un entier.

  2. Vérification de la saisie : La fonction scanf retourne le nombre d’éléments lus avec succès. Si scanf ne retourne pas 1, cela signifie que la saisie n’a pas été correcte, et le programme affiche un message d’erreur et se termine.

  3. Allocation dynamique : Le tableau memo est alloué dynamiquement en fonction de la valeur de n saisie par l’utilisateur. Cela garantit que vous avez toujours suffisamment de mémoire pour stocker les résultats intermédiaires.

  4. Gestion des erreurs : Si l’allocation de mémoire échoue, le programme affiche un message d’erreur et se termine.

  5. Libération de la mémoire : Après avoir utilisé le tableau memo, la mémoire est libérée pour éviter les fuites de mémoire.

Avec ces modifications, le programme permet à l’utilisateur de saisir la valeur de n au clavier, tout en garantissant une gestion correcte de la mémoire et des erreurs.

Alors oui, c’est correct, techniquement. Mais c’est toujours aussi stupide. On est en train de mobiliser des techniques de programmation sophistiquées au lieu de remettre en cause l’algorithme naïf.

Peut-on résoudre le problème de combinatoire qu’on a observé lors de calcule de la suite de Fibonnacci autrement qu’en utilisant de la mémoïsation ?

Oui, il existe d’autres méthodes pour résoudre le problème de combinatoire observé lors du calcul de la suite de Fibonacci, sans utiliser la mémoïsation. Voici quelques approches alternatives :

1. Approche itérative

L’approche itérative est une méthode efficace pour calculer les nombres de Fibonacci sans utiliser de mémoïsation. Elle utilise une boucle pour calculer les valeurs de manière séquentielle, ce qui évite les appels récursifs répétitifs.

#include <stdio.h>

unsigned long long fibo_iterative(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }

    unsigned long long a = 0;
    unsigned long long b = 1;
    unsigned long long c;

    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }

    return b;
}

int main() {
    int n;
    printf("Entrez la valeur de n : ");
    if (scanf("%d", &n) != 1) {
        fprintf(stderr, "Erreur de saisie\n");
        return 1;
    }

    printf("Fibonacci de %d est %llu\n", n, fibo_iterative(n));
    return 0;
}

Et voilà une solution convenable. Comme constaté précédemment, si on peut identifier en quoi il se trompe, on peut lui demander d’avancer vers une meilleure solution. Mais si on n’a pas le recul ou les connaissances pour le pousser plus loin, comme lorsqu’on est étudiant⋅e en première année et qu’on apprend l’algorithmique et la programmation, il faudra se contenter de ses réponses partielles ou absurdement compliquées.

Ce qui me surprend, c’est que le vampire est à la fois très premier degré (comme ici lorsque je lui demande si on saisi n au clavier, il répond faisons le) et en même temps il rebondit correctement sur des allusions pas vraiment plus explicites. Ça reste assez déroutant et je n’arrive pas encore à saisir s’il y a une logique derrière. (De toute façon ça n’est pas important, ce n’est pas le but de ces entretiens.)

Je coupe la suite de sa réponse qui présente d’autres solutions classiques, je n’ai pas regardé en détail, c’est du boulot de vérifier ce qu’il dit. On sort largement du cadre de l’exercice, et vous avez le lien pour regarder.

Mon impression pour le moment : d’une part, c’est techniquement impressionnant, il pond des trucs sophistiqués, les explications argumentées sont correctes. Mais en même temps, il avance dans des directions absurdes compte tenu du niveau qu’il exhibe par ailleurs. Et il y a cette faute sur le comptage des appels qui doit nous interpeler : elle n’est pas anodine. Le vampire est un perroquet stochastique, il a pondu un texte qui ressemble fort à ce qu’on attend, mais qui ne fait qu’y ressembler.

Épisode 4