Récursivité

Résolu/Fermé
DD - Modifié le 11 janv. 2022 à 13:21
mamiemando Messages postés 33100 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 13 mai 2024 - 17 janv. 2022 à 17:20
Bonsoir,
Je suis désolé pour la dernière question supprimée mais je travaille en python et j'ai un problème avec un code : je voudrais supprimer la récursivité dans ma fonction pour qu'il consomme moins d'énergie.
Bref, pouvez-vous m'aider ?
Cordialement
ma_liste = string.printable
max_length = 2

def force_brute(word):
    if len(word) < max_length:
        for lettre in ma_liste:
            if mdp == word + lettre:
                print("le mdp est : " + word + lettre)
                exit()
            else:
                print(word + lettre)
                force_brute(word + lettre)

mdp = '.'
force_brute('')
A voir également:

6 réponses

yg_be Messages postés 22783 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 13 mai 2024 1 481
11 janv. 2022 à 10:12
bonjour,
ton programme est-il complet?
0
Bonjour,
En fait, non. Par mégarde, j'ai oublié le "import string".
Cordialement
0
yg_be Messages postés 22783 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 13 mai 2024 1 481
11 janv. 2022 à 10:25
Je pense que, dans ce cas-ci, la récursivité n'est pas une source de consommation excessive d'énergie.
0
Mais alors, comment expliquer la consommation d'énergie ?
0
yg_be Messages postés 22783 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 13 mai 2024 1 481
Modifié le 11 janv. 2022 à 19:08
Comment as-tu mesuré cette consommation?

J'ai testé avec un programme non récursif, il n'est certainement pas plus rapdie.
0
DD > yg_be Messages postés 22783 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 13 mai 2024
11 janv. 2022 à 20:30
Sachant que mon ordi fait du 3 GHz (en gros 3 000 000 000 d'opérations à la seconde), que le code ne testait que dans les centaines de mots de passe par seconde et qu'il n'y avait que cette fenêtre d'ouverte, j'en ai fait cette conclusion.
0
georges97 Messages postés 11894 Date d'inscription lundi 31 janvier 2011 Statut Contributeur Dernière intervention 13 mai 2024 2 267
Modifié le 12 janv. 2022 à 12:17
Bonjour DD,

Je me permets d'intervenir car le sujet m'a interpellé. Non que j'ai une quelconque compétence mais parce que je n'ai pas encore abordé l'utilisation de la récursivité, qui d'après ce que j'ai retenu de mes lectures, permet de calculer notamment les factorielles et donc en principe est approprié au traitement de séries longues.

Mais surtout, votre argumentaire basé sur la fréquence du microprocesseur ne me semble pas s'appliquer à la comparaison entre les vitesses de traitement entre deux scripts utilisant des instructions ou de fonctions différentes.

D'une part parce que python étant un langage interprété, la vitesse de traitement découle de la "qualité" de la bibliothèque utilisées dans les scripts à comparer.

D'autre part, les différentes moutures de python (python, cpython, numpy, etc.) utiliseront des fonctions spécialisées pour traiter tel ou tel type d'algorithme et sont des environnements bien plus rapides puisqu'intégrant ou important des modules en C, donc compilés. C'est d'ailleurs, le choix de l'implémentation en fonction de la problématique qui explique que les programmeurs expérimentés choisissent l'environnement après analyse des instructions requises.

Certaines fonctions par exemple vont traiter les données entier plutôt que float et la vitesse de traitement en découlera.

Et surtout, le script en question, qui fonctionne parfaitement, inclut un print par tour d'instruction for.. , sachant que la fonction print() sous python 3.x demande un certain temps de calcul intermédiaire, bien plus pénalisant que l'emploi de fonctions récursives comme le souligne yg_be, que je salue.

A mon avis, pour mesurer des performances, il faudrait utiliser une instruction ou un module permettant le calcul du temps d'exécution de deux scripts concurrents. J'ai cru voir que cela existait, mais peut-être fais je la confusion avec des sources pour C. Je n'ai pas cherché plus avant.

Bien évidemment, yg_be ou un autre de nos précieux spécialistes voudront bien compléter ou infirmer mes suppositions.

Cordialement
0
yg_be Messages postés 22783 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 13 mai 2024 1 481
12 janv. 2022 à 14:01
Le calcul de factorielle est un parfait exemple d'utilisation inappropriée de fonction récursive.

Une fonction récursive permet parfois de faciliter l'écriture et la compréhension du code, donc d'éviter des erreurs.
Cependant, cela a deux désavantages:
- le temps que prend chaque appel à la fonction
- l'espace requis pour stocker ces appels et les variables associées (qui dépend de la "profondeur" dans laquelle on rentre, du nombre d'appels en cours)

Dans le cas d'un calcul de factorielle,
- une boucle est quasi aussi claire qu'une fonction récursive
- le temps d'appel est long par rapport au travail fait dans chaque appel
- la profondeur est égale à la valeur du nombre dont on cherche la factorielle

Dans le cas du mot de passe:
- travailler sans récursive est beaucoup plus embrouillé que l'utilisation d'une récursive
- le temps d'appel est court comparé au travail fait dans chaque appel
- la profondeur est égale à la longueur maximum du mot de passe

Pour mesurer le temps écoulé, une recherche sur Internet: "temps écoulé en Python".

J'ai supposé, peut-être à tort, que DD avait supprimé les print() avant de mesurer le temps d'éxécution de son script.

Moi je traite 1 million de mots de passe en moins d'une demi seconde, avec la méthode récursive.

Et il est possible de gagner un peu de temps en évitant d'évaluer deux fois
word + lettre
.
0
georges97 Messages postés 11894 Date d'inscription lundi 31 janvier 2011 Statut Contributeur Dernière intervention 13 mai 2024 2 267 > yg_be Messages postés 22783 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 13 mai 2024
12 janv. 2022 à 14:52
Merci pour ton retour et tes explications , yg_be. Cela m'évitera de me fourvoyer dans l'utilisation de la récursivité, sachant que je n'ai pas par ailleurs de besoin quotidien de l'usage de factorielles. Comme tu le suggères, la fonction time () convient pour cette mesure de durée d'exécution.

Encore merci.
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
mamiemando Messages postés 33100 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 13 mai 2024 7 753
Modifié le 17 janv. 2022 à 17:14
Bonjour,

Comme le dit yg_be, il est préférable d'écrire un programme de manière itérative que récursive quand c'est possible. En effet, chaque appel récursive engendre une recopie en mémoire des paramètres de chaque appel récursif. Cette zone mémoire est appelée la pile (car on "empile/dépiles" les appels de fonction, en particulier les appels de fonction). Si trop d'appels récursifs sont fait, la pile n'est pas assez grand et on obtient un débordement de pile (stack overflow en anglais, qui a donné son nom à un célèbre site d'entraide...). Outre la mémoire consommée, ces recopies nécessite des opérations d'écriture supplémentaires pour mettre à jour la pile.

À titre pédagogique, la fonction factorielle est souvent l'exemple bateau utilisé pour introduire la récursivité car c'est comme ça que les matheux la présente. Toutefois, comme le dit yg_be, on peut écrire très facilement ce calcul avec un programme itératif qui sera donc en pratique plus efficace. Les mises à jour de la pile sont dans ce cas particulier d'autant plus inutile qu'on a besoin en réalité besoin de mémoriser uniquement à quel facteur on est rendu et le résultat courant :

def factorielle(n):
    ret = 1
    for i in range(2, n + 1):
        ret *= i
    return ret


Un exemple ou la récursivité serait plus pertinent serait un parcours d'arbre ou un algorithme de branch & bound ou de branch & cut qui peuvent se voir comme des parcours dans un arbre de recherche. Toutefois, tout parcours d'arbre et plus généralement de graphe peut se faire à l'aide d'une pile (et d'une color map dans le cas d'un graphe). Dit autrement, on peut quasiment tout le temps écrire un programme récursif sous forme itérative (et inversement). Le choix entre l'un ou l'autre et donc la performance et la lisibilité.

Si on revient au problème initial, on peut voir le problème posé comme un parcours d'arbre, où chaque nœud de profondeur k évalue l'un des mots de passe de longueur k, et où chaque nœud fils est obtenu par ajout d'un caractère supplémentaire. C'est exactement ce que fait le programme du message #1.

Fondamentalement, on explore donc a^k où a est la taille de l'alphabet nœud, et c'est pour ça que le programme coûte cher. En écrivant le programme de manière itérative (par exemple à l'aide de
itertools.product
), l'implémentation sera certes meilleure, mais continuera à évaluer autant de solutions, donc il n'y aura pas une amélioration significative en terme de complexité algorithmique. C'est d'ailleurs pour ça que les outils qui servent à casser des mots de passe n'explorent pas toutes les permutations (par exemple en se basant sur des mots qui existent) ou se basent sur d'autres stratégies.

Quoi qu'il en soit, il est important de rappeler trois choses :
  • Il est important d'utiliser des mots de passe sûrs ;
  • Avoir accès à une machine via un compte utilisateur suffit à attaquer les profils (cependant systèmes d'exploitation font "exprès" d'attendre un peu entre chaque essai pour empêcher les attaques par force brute qui prennent alors un temps astronomique -- ce que font également la plupart des logiciels et sites webs également);
  • Pirater une machine est puni par la loi et selon moi, il y a des manières plus intelligentes de dépenser son temps et son énergie (et celle de planète par la même occasion, puisque c'était le sujet initial).


Bonne chance
0
georges97 Messages postés 11894 Date d'inscription lundi 31 janvier 2011 Statut Contributeur Dernière intervention 13 mai 2024 2 267
12 janv. 2022 à 17:18
Merci mamiemondo pour cet utile rappel à la loi, que bien trop de visiteurs prennent soin d'ignorer. Je me rends d'ailleurs compte que le post #1 parle d'une dernière question supprimée (sans doute à juste titre) dont nous ne savons rien.

Si effectivement, il doit être apporté ici des réponses concernant la pénétration de systèmes informatiques, il est primordial, de mon point de vue, de signifier le consensus sur la valeur et j'oserais dire la noblesse du codage, en s'opposant à toute demande douteuse.

J'ai grandement apprécié également la citation de stackoverflow, exemplaire à bien des égards et dont la haute teneur pourrait inspirer bien des forums pollués par des dérives en tous genres.

Pour ma part, en précisant que mon incise dans le fil du demandeur n'était motivée que par la curiosité vis à vis de tests sur un mot de deux caractères. Et que j'ai à l'esprit l'amélioration d'un jeu du pendu que j'essaie d'améliorer au fil de ma progression sous python.

Je serais pour ma part tout aussi "intolérant" que mamiemando par rapport au piratage, forme de terrorisme social et philosophique sous couvert de finalités pédagogiques. Sans vouloir préjuger des intentions et objectifs du demandeur et sans intention aucune de troller ce fil.

Cordialement
0
DD > georges97 Messages postés 11894 Date d'inscription lundi 31 janvier 2011 Statut Contributeur Dernière intervention 13 mai 2024
12 janv. 2022 à 18:31
Êtes-vous en train de me prendre pour un pirate ? Je n'ai que 13 ans et je ne connais que le C++ et je possède des bases en python mais sinon, ce programme n'est qu'un test rien de plus.
0
georges97 Messages postés 11894 Date d'inscription lundi 31 janvier 2011 Statut Contributeur Dernière intervention 13 mai 2024 2 267 > DD
Modifié le 12 janv. 2022 à 19:22
Si vous étiez un pirate, vous ne viendriez pas sur ce site, bien connu pour rejeter les demandes de "formation" à cette activité. Les pirates ont d'autres références et lieux de rendez-vous.

Par ailleurs, l'âge ne dispense pas de lire ce qui est énoncé Sans vouloir préjuger des intentions et objectifs du demandeur ainsi que ma tentative de participation positive au post #12 pourraient plaider en ma faveur

Mais les rappels de mamiemando, que j'approuve ainsi que 10 ans de présence sur CCM m'ont convaincu que des personnes peu respectueuses de la loi et de leurs prochains accèdent à CCM avec des intentions malhonnêtes, même si vous n'en avez jamais rencontré.

Si j'avais pensé que vous en étiez, je vous l'aurais fait comprendre et de plus, aurais demandé la fermeture du fil.

Il eût été plus utile de répondre sur les tests que vous avez menés suite aux interventions de yg_be et de mamiemando puisque seule la mienne vous semble inacceptable.

Bonne continuation
0
yg_be Messages postés 22783 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 13 mai 2024 1 481 > DD
12 janv. 2022 à 19:13
Moi pas, DD.
De toutes façons, faire une liste de tous les mots de passe possibles n'est pas le début d'une activité de piratage.
1
mamiemando Messages postés 33100 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 13 mai 2024 7 753 > yg_be Messages postés 22783 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 13 mai 2024
Modifié le 13 janv. 2022 à 17:35
DD, personne ne te juge. Il faut que tu comprennes que sur ce forum on voit de tout. Par défaut, on ne sait pas si une demande est malveillante ou pas. Même si la personne qui pose une question est de bonne foi, rien ne garantit que les éléments abordés ne seront pas mal exploités par une personne malveillante. Les rappels de bien séance sont là pour ça.

Si tu veux éviter ce genre de "désagréments", il suffit de poser tes futures questions de sorte à éviter qu'on puisse avoir des doutes. Typiquement ton problème aurait pu être ainsi formulé : "Comment énumérer toutes les chaînes de caractères de taille inférieure ou égale à n ?". Simple, court, clair, précis, pas de place au doute.
0
mamiemando Messages postés 33100 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 13 mai 2024 7 753
Modifié le 17 janv. 2022 à 17:33
Voici une implémentation itérative et donc a priori plus efficace. Il est important de passer par
itertools
pour améliorer la performance. Et il est important aussi d'utiliser la bonne fonction :
  • itertools.combinations
    ne renvoie que les mots de passe dont les lettres sont croissantes ;
  • itertools.permutations
    renvoie les mots sans caractères dupliqués ;
  • c'est donc bien
    itertools.product
    qu'il faut utiliser (voir cette discussion et la définition du produits cartésiens).


Un bon exemple pour tester le programme est donc une chaîne comme
'pass'
car les lettres ne sont pas dans l'ordre croissant et car il y a des caractères répétés (en l'occurrence le
's'
).

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import string
from itertools import product

password = tuple("pass")
alphabet = "abcdefghijklmnopqrstuv" # string.printable
stop = False

for n in range(len(password) + 1):
    for attempt in product(alphabet, repeat=n):
        if attempt == password:
            stop = True   
            break
    if stop:
        break

if stop:
    print("".join(attempt))
else:
    print("Pas trouvé!")


Dans cette implémentation, le mot de passe à deviner est mis sous forme de tuple, car c'est ce que retournent les primitives du module
itertools
. Ceci permet de faire le test d'égalité directement. Pour transformer le tuple sous forme de chaîne, on peut utiliser la méthode
str.join
.

Enfin, pour accélérer le code, on n'oublie pas le
break
pour interrompre les deux boucles
for
imbriquées.

Si on veut faire un truc plus sérieux, typiquement une fonction qui ne prend pas en paramètre la réponse mais un oracle qui sert à tester le mot de passe, un paramètre pour l'alphabet et le nombre de caractère maximum du mot de passe cherché, ça donne un code qui ressemble à ça (on notera que grâce au
return
, on peut quitter les boucles
for
plus facilement :

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
                        
import string
from itertools import product

class Oracle:
    def __init__(self, password):
        self.password = tuple(password)
    def check(self, attempt):
        return attempt == self.password

def brute_force(oracle, alphabet = string.printable, max_len = 10):
    for n in range(max_len):
        for attempt in product(alphabet, repeat=n):
            if oracle.check(attempt):
                return "".join(attempt)
    return None

oracle = Oracle("pass")
attempt = brute_force(oracle, "abcdefghijklmnopqrstuv")
if attempt is not None:
    print("".join(attempt))
else:
    print("Pas trouvé!")


Bonne chance
0