Récursivité Résolu/Fermé

Question

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

yg_be · Answer

bonjour,
ton programme est-il complet?

yg_be · Answer

Je pense que, dans ce cas-ci, la récursivité n'est pas une source de consommation excessive d'énergie.

DD · Answer

Mais alors, comment expliquer la consommation d'énergie ?

georges97 · Answer

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

mamiemando · Answer

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

mamiemando · Answer

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

Récursivité

6 réponses

Discussions similaires