Répondre à la discussion
Affichage des résultats 1 à 27 sur 27

Comment python gère-t-il la récursivité ?



  1. #1
    martini_bird

    Comment python gère-t-il la récursivité ?


    ------

    Salut,

    la question est dans le titre et ma réponse est, après expérience : très mal !

    Sans rire, je suis contraint même pour des trucs relativement basiques de passer en itératif : quelqu'un saurait-il m'expliquer pourquoi ?

    Merci d'avance !

    PS : Merci d'éviter le troll récursif vs itératif...

    -----
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  2. Publicité
  3. #2
    Pole

    Lightbulb Re : Comment python gère-t-il la récursivité ?

    Peut-être que dans l'appel d'une fonction, le compilateur remplace simplement l'appel de fonction par le code que contient la fonction. Comme dans un #define du C
    Après, je ne connais pas du tout Python. Donc je peut me tromper entièrement.

    Pole.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  4. #3
    overmind

    Re : Comment python gère-t-il la récursivité ?

    Citation Envoyé par Pole Voir le message
    Peut-être que dans l'appel d'une fonction, le compilateur remplace simplement l'appel de fonction par le code que contient la fonction. Comme dans un #define du C
    Oh non! C'est tout de même un language plus évolué que ça... (En plus il n'y a pas de compilateur...)

    Quels genre de codes te posent problèmes?
    Personellement je n'ai jamais eu de problèmes avec ça.

    En même temps j'essaye toujours de préférer à la récursivité des structures de piles que je gère moi même.

  5. #4
    martini_bird

    Re : Comment python gère-t-il la récursivité ?

    Salut,

    Quels genre de codes te posent problèmes?
    Par exemple si je lui demande de parcourir une liste de facettes pour les afficher, il explose dès que la liste a plus de 1000 éléments.

    La fonction est du genre :
    Code:
    def dessineListe(list):
        if list=[]:
            print "ok" 
        else:
            list[0].dessine() # la méthode dessine() est dans la classe "facettes"
            dessineList( list[1:len(list)] )
    Alors qu'en faisant
    Code:
    def dessineListe(list):
        for idx in range(len(list)):
            list[idx].dessine()
    je n'ai pas de pb.

    J'ai un autre exemple où il faut ramer pour "dérécursifier" (ça se dit ?). En l'état, c'est super long (à partir de n=25, il faut compter en minutes puis en heure...).

    Désolé, c'est un peu (beaucoup ) crade comme code, mais bon je le mets quand même : la méthode renvoie une liste constituée des partitions de n (les listes d'entiers dont la somme de ses éléments vaut n).
    Code:
    def buildyoung(n):
    	if (n==1):
    		return [[1]]
    	if (n<1):
    		return [[]]
    	idx=1	
    	r=[[n]]
    	while (idx<n):
    		l=buildyoung(n-idx)
    		for partition in l:
    			if (idx<=partition[len(partition)-1]):
    				partition[len(l):len(l)]=[idx]
    				r[len(r):len(r)]=[partition]
    		idx=idx+1
    	return r
    Par exemple :

    Code:
    >>> buildyoung(6)
    [[6], [5, 1], [4, 1, 1], [3, 1, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [2, 2, 1, 1], [3, 2, 1], [4, 2], [2, 2, 2], [3, 3]]
    Cordialement.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  6. #5
    Pole

    Re : Comment python gère-t-il la récursivité ?

    Tu envoie un tableau de 1000 puis 999,998,... cases!!!!
    Si tu sommes ça donne environ 500 000! La pile doit craquer (Il me semble que la pile d'un programme est limitée à 1Mo donc il suffit que la taille d'une facette soit plus grande que 2 octets,....). A moins que Python envoies l'adresse de la première case du tableau comme en C. (Encore une fois, je ne connais pas Python)

    Pole.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  7. A voir en vidéo sur Futura
  8. #6
    overmind

    Re : Comment python gère-t-il la récursivité ?

    Je rapelle qu'un slice [x:y] recrée une nouvelle liste à chaque fois...
    C'est ça qui pose problème, pas la récursivité.

    Il faut t'arranger pour éviter de recopier le la mémoire inutilement... (ex: passer les indices en paramètres et la liste par référence)

  9. Publicité
  10. #7
    overmind

    Re : Comment python gère-t-il la récursivité ?

    Citation Envoyé par Pole Voir le message
    Tu envoie un tableau de 1000 puis 999,998,... cases!!!!
    Si tu sommes ça donne environ 500 000! La pile doit craquer (Il me semble que la pile d'un programme est limitée à 1Mo donc il suffit que la taille d'une facette soit plus grande que 2 octets,....). A moins que Python envoies l'adresse de la première case du tableau comme en C. (Encore une fois, je ne connais pas Python)

    Pole.
    Attention, encore une fois python est interprété, les arguments ne vont pas directement sur la pile et on n'y crée pas de tableaux non plus...
    Ici ce qui se passe c'est qu'à chaque appel de R(slice(liste)) slice crée une copie d'une partie de liste sur un genre de heap, et passe le tout par référence à R.
    Le problème c'est que malgrès un passage par référence, une copie est réalisée...

  11. #8
    martini_bird

    Re : Comment python gère-t-il la récursivité ?

    SAlut,

    ok merci pour les précisions : ça venait donc de mon programme (ce à quoi il fallait bien s'attendre ). Je pensais que le "slice" envoyait la queue de la liste et non une copie. Je me suis aussi fait abusé par le terme "liste" : c'est en fait un tableau (rien à voir avec le type "list" de caml par exemple).

    Bonne soirée !
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  12. #9
    overmind

    Re : Comment python gère-t-il la récursivité ?

    Citation Envoyé par martini_bird Voir le message
    SAlut,

    ok merci pour les précisions : ça venait donc de mon programme (ce à quoi il fallait bien s'attendre ). Je pensais que le "slice" envoyait la queue de la liste et non une copie. Je me suis aussi fait abusé par le terme "liste" : c'est en fait un tableau (rien à voir avec le type "list" de caml par exemple).

    Bonne soirée !
    En fait c'est bien une liste (et remarquablement bien foutue d'ailleurs) mais dans son modèle il faut un constructeur de copies... C'est "[:]" qui est utilisé. (d'ailleurs à mon avis un slice qui modifierai en même temps l'original serait assez *********...)

  13. #10
    martini_bird

    Re : Comment python gère-t-il la récursivité ?

    Salut,

    ok merci, mais dans ce cas il n'existe pas une fonction qui renvoie la queue d'une liste ?

    Bonne journée.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  14. #11
    overmind

    Re : Comment python gère-t-il la récursivité ?

    Par défaut je ne crois pas...
    Par contre tu peux faire un classe de "wrapper" qui transforme __getitem__(i) en __getitem__(i+k) sur la liste originale. Ensuite tu surcharges getslice pour renvoyer l'instance de wrapper à la place d'une copie de la liste, et le tour est joué.

  15. #12
    martini_bird

    Re : Comment python gère-t-il la récursivité ?

    Salut,
    Citation Envoyé par overmind Voir le message
    Par défaut je ne crois pas...
    Par contre tu peux faire un classe de "wrapper" qui transforme __getitem__(i) en __getitem__(i+k) sur la liste originale. Ensuite tu surcharges getslice pour renvoyer l'instance de wrapper à la place d'une copie de la liste, et le tour est joué.
    Tiens, en passant, on peut surcharger des méthodes ? Car j'avais lu que c'était impossible (et mes tentatives ont été courtoisement rejetées...)
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  16. Publicité
  17. #13
    overmind

    Re : Comment python gère-t-il la récursivité ?

    Ça dépend de ce que tu apelles surcharger.
    Faire de la surcharge d'opérateur, oui; surcharger au sens faire la différence entre toto(a) et toto(a,b) comme des méthodes indépendantes, non.
    Ceci dit un on peut parfaitement faire une méthode toto avec liste de paramètres variable et appel de la méthode ad hoc après quelques tests (attention à ne pas perdre la généricité lors de ces tests).

  18. #14
    fderwelt

    Re : Comment python gère-t-il la récursivité ?

    Bonsoir,

    Je ne connais pas trop python, mais je me permets une remarque d'ordre général. À la limite du troll, pas trop j'espère.

    Quand on a une culture C++ (comme moi), il n'y a pas de différence entre une surcharge du genre:
    int f(int a) ;
    int f(int a, int b) ;
    ou une du genre:
    int operator + (int a) ;
    int operator + (int a, int b) ;
    Juste une question de notations.

    Maintenant, pourquoi C++ ne fait-il pas la différence entre:
    int f(int a) ;
    double f(int a) ;
    ce qui permettrait des choses du style:
    int i = f(0) ;
    double x = f(0) ;
    Techniquement, ce serait faisable. Mais, mis à part les problèmes de lisibilité, ça supposerait de connaître tous les constructeurs par défaut d'une classe, y compris ceux générés automatiquement par le compilo... pénible. Mais dommage quand même, non?

    -- françois
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

  19. #15
    overmind

    Re : Comment python gère-t-il la récursivité ?

    Le plus gros problème dans ce cas serait de différentier l'appel de deux méthodes...
    Ex:
    Code:
    int toto(int a);
    void toto(int a);
    int main()
    {
    toto(a); // j'appelle qui moi? au secours!!!
    }

  20. #16
    jayjay75

    Re : Comment python gère-t-il la récursivité ?

    Citation Envoyé par martini_bird Voir le message
    ok merci, mais dans ce cas il n'existe pas une fonction qui renvoie la queue d'une liste ?
    Les slicing marche aussi avec les indices négatifs et nulls.
    Code:
    >>> a
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>> a[-1]
    9
    >>> a[-2:]
    [8, 9]

  21. #17
    overmind

    Re : Comment python gère-t-il la récursivité ?

    Certes, mais je crois qu'il voulait plus une référence vers une fin de liste compte tenu des problèmes qu'il recontre...

    EDIT: bienvenue, au fait!

  22. #18
    jayjay75

    Re : Comment python gère-t-il la récursivité ?

    Merci et bonjour a tous !

    Pour réponde à la question de départ, le problème se situe dans l'algorithme.
    La quasi-totalité des appels à buildyoung() sont effectués inutilement.
    En stockant simplement les résultats temporaires on passe d'une complexité o(n!) à o(n log n) :
    Code:
    def buildyoung(n, tempData={0:[[]]}):
        if n not in tempData:
            r=[[n]]
            for idx in range(1,n):
                for partition in buildyoung(n-idx, tempData):
                    if (idx<=partition[-1]):
                        r.append(partition+[idx])
            tempData[n] = r
        return tempData[n]
    Sur mon PC, pour n=25, je passe de 114 sec à 0,03 sec. Vous avez dit efficace ?
    Dernière modification par jayjay75 ; 12/10/2006 à 22h17.

  23. Publicité
  24. #19
    overmind

    Re : Comment python gère-t-il la récursivité ?


  25. #20
    martini_bird

    Re : Comment python gère-t-il la récursivité ?

    Salut,

    ah ben oui, c'est logique !

    Merci.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  26. #21
    Fra_Diavolo

    Question Re : Comment python gère-t-il la récursivité ?

    Bonsoir,

    je voudrais revenir à la question de départ (s'il y a encore du monde).
    Je suis un fan de la récursivité et surtout de la récursivité terminale et je suis perplexe quant à la manière dont python gère la récursivité, terminale ou pas d'ailleurs.
    Exemple: Fibonacci:

    # Fibonacci itératif
    def fibo1(n):
    f0=0; f1=1
    if (n==0): return 0
    if (n==1): return 1
    f2=1
    i=1
    while (i<n):
    f2,f1,f0 =f1+f0, f2, f1
    f1,f0 =f2, f1
    i=i+1

    return f2


    # Fibo récursif terminal
    def fibo2(n,acc1,acc2):
    if (n==0): return acc2
    if (n==1): return acc1
    return fibo2(n-1,acc1+acc2,acc1)



    # Fibonacci DPR
    def fiboDPR(n):
    if (n==0): return 0
    if (n==1): return 1
    if (n==2): return 1
    (p,r)=divmod(n,2)
    if (r==0):
    return fiboDPR(p)*(fiboDPR(p-1)+fiboDPR(p+1))
    if (r==1):
    fp=fiboDPR(p)
    fp1=fiboDPR(p+1)
    return fp*fp + fp1*fp1


    Pour n=10000 on a les temps
    Fibo it 0.0310001373291
    Fibo RT 0.140999794006
    Fibo DPR 0.219000101089

    on voit que fibo2 est plus lent, ce qui me surprend (mais c'est effectivement peut être à caase du passage de paramètres ?) mais que fiboDPR soit le plus lent des trois, là je ne comprends pas du tout.

  27. #22
    overmind

    Re : Comment python gère-t-il la récursivité ?

    Avec le module timeit: (n=100, pour n=1000 j'ai des débordements de récursivité...)
    Temps de fiboDPR:0.00069855928421
    Temps de fibo1:6.69407844543e-05
    Temps de fibo2:0.000101609230042


    Je ne vois pas le problème... fibo1 est itératif, et va à l'essentiel, dans fibo2 on fait les mêmes calculs plus les appels, et dans fiboDPR on se tape encore plus d'appels de fonctions...

  28. #23
    Fra_Diavolo

    Re : Comment python gère-t-il la récursivité ?


    ben non justement,
    dans fiboDPR comme tu divise "en gros" n par 2, tu ne calcules pas tout les nombres entre f0 et f(n), loin de là et même si tu fait un peu plus d'appels à cause des appels pour fiboDPR(0) et fiboDPR(1).
    Dans certains environnements comme Mathematica ou Maple ("langages" interprétés tous les deux) ça va généralement plus vite que le récursitivité, idem pour fibo2, j'ai fait plein de tests.
    ça veut dire que l'appel d'une fonction en python est "cher" ?

    ps: il faut ajouter par exemple

    import os, sys, time

    sys.setrecursionlimit(100000)

    pour aller au delà de la limite

  29. #24
    Fra_Diavolo

    Re : Comment python gère-t-il la récursivité ?

    houps,

    je voulais dire "ça va généralement plus vite que la version itérative"

  30. Publicité
  31. #25
    Pole

    Re : Comment python gère-t-il la récursivité ?

    Si tu veux aller plus vite, passe à des langages compilés (C,C++,Pascal....).
    Et si tu veux accélérer fiboDPR,tu peux faire que 2 appels si r=0 : si tu connais Fn et Fn-1 tu devrais facilement connaître Fn+1
    Essaye de passer en itératif(il faut calculer en même temps Fn et Fn-1), peut être que Python enregistre les appels des fonctions (tu peux tester en utilisant la définition de la suite Fn=Fn-1+Fn-2 et F1=1,F2=1,pour calculer comme ça,il faut 2^n appels,si Python les mémorise,ça passe à n).

    Pole.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  32. #26
    overmind

    Re : Comment python gère-t-il la récursivité ?

    Citation Envoyé par Fra_Diavolo Voir le message

    ça veut dire que l'appel d'une fonction en python est "cher" ?

    ps: il faut ajouter par exemple

    import os, sys, time

    sys.setrecursionlimit(100000)

    pour aller au delà de la limite
    Merci pour le truc, je connaissais pas.

    J'ai fait le test en C pour fibo1 et fibo2, fibo2 est plus lent, mais pas tellement, ce qui me fait dire que oui, les appels de fonction en python sont chers...
    Dailleurs c'est pas compliqué, fibo2 fait exactement la même chose que fibo1, avec un appel en plus à chaque addition, ce qui suppose recopier plein de fois dans la mémoire les résultats (au moins en C)...

  33. #27
    Fra_Diavolo

    Thumbs up Re : Comment python gère-t-il la récursivité ?

    http://forums.futura-sciences.com/im...ies/Bravo1.gif

    AH, j'ai honte,
    un appel pour "rien" dans fiboDPR

    avec

    # Fibonacci DPR
    def fiboDPR(n):
    if (n==0): return 0
    if (n==1): return 1
    if (n==2): return 1
    (p,r)=divmod(n,2)
    if (r==0): fp=fiboDPR(p); fpm1=fiboDPR(p-1); fp1=fp+fpm1; return fp*(fpm1+fp1)
    if (r==1): fp=fiboDPR(p);fp1=fiboDPR(p+1) ; return fp*fp + fp1*fp1

    on a:
    pour n=10000
    Fibo it 0.0159997940063
    Fibo RT 0.125
    Fibo DPR 0.0150001049042

    pour n=11000
    Fibo it 0.0309998989105
    Fibo RT 0.109999895096
    Fibo DPR 0.0150001049042

    là ça me rassure!
    Merci.

Discussions similaires

  1. Schema pour gere 1 chauffe eau solaire!
    Par flyingman dans le forum Électronique
    Réponses: 2
    Dernier message: 30/08/2007, 23h19
  2. Convertisseur BCD-7seg qui gère l'hexa
    Par FantomX dans le forum Électronique
    Réponses: 2
    Dernier message: 31/12/2006, 18h52
  3. TPE sur une centrale d'alarme géré par un pic 16f84
    Par diba dans le forum TPE / TIPE et autres travaux
    Réponses: 0
    Dernier message: 24/01/2005, 13h02
  4. Intégrale et recursivité
    Par Olorin dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 17/01/2005, 12h22
  5. Lecteur CD - non géré
    Par Krynn dans le forum Matériel - Hardware
    Réponses: 8
    Dernier message: 08/03/2004, 09h18
Découvrez nos comparatifs produits sur l'informatique et les technologies.