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.

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))

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

@josmiley: testé, c'est correct.

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

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.

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