fonction récursive pour générer les nbrs sur n bits

bonjour tout le monde.
je voudrais générer tous les nombres codés sur n bits avec une fonction recursive. si quelqu'un a une idée n'hesitez pas à me donner un coup de main.
NB: il se peut résouder ce probleme en utilisant n boucles for mais la complexité augmente. je cherche une solution optimale avec une fonction récursive.
merci d'avance de votre aide.

tu fais une fonction avec 2 int en paramètre.
le 1er est le nombre, le 2e est la position du bit.

PS : quoi que ... je n'ai peut-être rien compris au problème. :aie:

bonjour simpatico

Citation:

---

je voudrais générer tous les nombres codés sur n bits avec une fonction recursive

---

je ne vois pas en quoi la récursivité va nous aider la dedans. juste une boucle for ferait l'affaire.

Perso avec des boucles, je vois pas bien comment faire (mais peut être n'ai-je pas bien tout compris non plus).
Pour ce qui est de la complexité, c'est forcément exponentiel je pense, car la taille de la sortie est exponentielle.
Par exemple, les entiers codés sur 4 bits, il y en 2^4.
Donc nécessairement...

Voilà un pseudo code qui pourra te mettre sur la voie...

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Fonction nbits(entier n) Si (n = 1) renvoyer {'1', '0'} Sinon resultatmoins1 = nbits( n - 1) resultat = {} Pour chaque nombre m dans resultatsmoins1 resultat = resultat U { concat('0', m) } resultat = resultat U { concat('1', m) } Fpour renvoyer resultat Fsi FinFonction

---

Le U, c'est pour l'union...
Théoriquement, ça marche... Cela dit, le résultat sera pas trié (t'auras pas les nombres du plus petit au plus grand).

Avec une boule :

Code:

---

1 2 3

for (i = 0; i < (1 << n); i++) { /* ... */ }

---

Dans cette boucle i prend successivement toutes les valeurs qu'on peut représenter sur n bits :mouarf:

Citation:

---

Envoyé par matafan

Dans cette boucle i prend successivement toutes les valeurs qu'on peut représenter sur n bits :mouarf:

---

Tu peux enlever le mouarf, je pense. Ce sont effectivement la définition la plus exacte et la meilleure approche à donner.

Héhé, je n'y avais pas pensé. C'était pourtant si simple :D
Le posteur aura néanmoins le plaisir de découvrir une fonction récursive pas efficace :aie: