Partage
  • Partager sur Facebook
  • Partager sur Twitter

Fonction récursive Python

Anonyme
    7 avril 2021 à 21:20:11

    Bonjour, je dois réaliser une fonction récursive à partir de cette fonction:

    res = naturel % 2

        while naturel > 0:

            naturel //= 2

            res += naturel % 2

        return res

    J'aimerais avoir de l'aide, s'il vous plaît.

    • Partager sur Facebook
    • Partager sur Twitter
      8 avril 2021 à 3:14:55

      Que fait cette fonction? Elle compte le nombre de bits à 1 dans le nombre.
      Une fonction récursive a besoin d'une condition d'arrêt.
      On commence par regarder le bit le moins significatif.
      Ensuite on compte le nombre de bits à 1 dans ce qui suit, et ce tant qu'il y a des bits à 1.
      La condition "tant qu'il y a des bits à 1" est la condition d'arrêt.
      Compter dans "ce qui suit" revient à diviser le nombre par 2 et rappeler cette même fonction.
      Ce qui donne:
      def bitCount(naturel):
       if naturel == 0: return 0
       return naturel%2 + bitCount(naturel//2)
      n=int(input("Nombre: "))
      print(bitCount(n))
      • Partager sur Facebook
      • Partager sur Twitter

      Le Tout est souvent plus grand que la somme de ses parties.

        8 avril 2021 à 3:55:55

        Pas testé, suis sur mon tel ... Mais je suppose que ça fonctionne, c'est le même code que PierrotLeFou.

        bitCount = lambda n : n and n%2+bitCount(n>>1)



        -
        Edité par josmiley 8 avril 2021 à 4:00:10

        • Partager sur Facebook
        • Partager sur Twitter

        "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

          8 avril 2021 à 4:34:46

          @josmiley: testé, c'est correct. :)
          • Partager sur Facebook
          • Partager sur Twitter

          Le Tout est souvent plus grand que la somme de ses parties.

            8 avril 2021 à 5:32:25

            PierrotLeFou, pour ton code, j'aurais plutôt mis la condition de sortie après puisqu'elle ne sera vraie qu'une seule fois.

            if naturel :
                return naturel%2+...
            return 0



            • Partager sur Facebook
            • Partager sur Twitter

            "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

              8 avril 2021 à 7:34:55

              Tout à fait pertinent.
              On n'est pas obligé de tester la condition d'arrêt de la façon donc je l'ai écrite.
              C'est un peu plus rapide comme tu l'as fait.
              • Partager sur Facebook
              • Partager sur Twitter

              Le Tout est souvent plus grand que la somme de ses parties.

                8 avril 2021 à 10:56:42

                josmiley a écrit:

                PierrotLeFou, pour ton code, j'aurais plutôt mis la condition de sortie après puisqu'elle ne sera vraie qu'une seule fois.

                if naturel :
                    return naturel%2+...
                return 0



                Bonne remarque, que je viens d'incorporer dans mon tutoriel sur la récursivité. En C/C++, ce placement peut légèrement accélérer le code, mais le compilateur saurait peut-être optimiser (en Python pas d'accélération véritable car le nombre d'appels récursifs est limité).

                -
                Edité par PascalOrtiz 8 avril 2021 à 11:55:10

                • Partager sur Facebook
                • Partager sur Twitter

                Fonction récursive Python

                × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                • Editeur
                • Markdown