Explication détaillée des méthodes d'itération et de récursivité en python

Lorsque vous rencontrez une situation, il est nécessaire d'effectuer une opération récursive, mais le nombre de récursions est très important, plus de 10 000 fois. Ne parlons pas de plus de 10 000 récursions. Le code de test original est en java sans jdk ni environnement de compilation, utilisons python

Jetons d'abord un coup d'œil au code java original :

public class UpCount {
    private long calc(int depth) {
        if (depth == 0) return 1;
        long cc = calc(depth - 1);
        return cc + (depth % 7) + ((((cc ^ depth) % 4) == 0) ? 1 : 0); 
    }
    public static void main(String[] args) {
        UpCount uc = new UpCount();
        System.out.println(uc.calc(11589));
    }
}

Je n'ai pas beaucoup joué à Java, mais ces lignes de code sont toujours sans stress. J'ai rapidement éliminé le désordre et je l'ai changé en code python

def calc(depth):
    if depth == 0:
        return 1
    cc = long(calc(depth-1))
    xor_mod = (cc ^ depth)%4
    if xor_mod == 0:
        return cc+(depth%7)+1
    else:
        return cc+(depth%7)
 
number = long(calc(11589))
print number

. Le code est collé, F5 , quelque chose s'est mal passé

Cette version du code n'ajoutait pas de longueur à l'origine, car la chaîne précédente de plus de dix chiffres entiers peut être utilisée directement , donc je soupçonne que c'est lié à long. Cela n'a pas d'importance

Bien sûr, en fait, cela n'a rien à voir avec long. La longueur entière prise en charge par python est très longue. :

cimal = 7
original = 28679718602997181072337614380936720482949
array = ""
result= ""
while original !=0:
    remainder = original % cimal
    array += str(remainder)
    original /= cimal
length = len(array)
for i in xrange(0,length):
    result += array[length-1-i]
print result

Le code ci-dessus Convertissez une longue chaîne de nombres décimaux en représentation hexadécimale, ou en n'importe quel système hexadécimal, convertissez-la en octal ou hexadécimal. Utilisez simplement oct() et hex() pour le faire. Utilisez la division euclidienne. Résolvons-le

Par conséquent, on peut voir que l'erreur ne réside pas dans la taille du nombre. Après tout, 11589 n'est qu'un jeu d'enfant pour les ordinateurs d'aujourd'hui, 2. ^16 et 65536

En fait Ce n'est qu'à ce moment-là que j'ai réalisé que la vraie raison de l'erreur récursive précédente n'était pas mentionnée. J'étais hagard

La raison de l'erreur récursive est que la récursion par défaut. La limite de Python n'est que d'environ 1 000 fois, mais ici, il doit s'exécuter 10 000 fois. Il m'a fallu beaucoup de temps pour actualiser : Exécuter tempsErreur : profondeur de récursion maximale dépassée

Alors je me suis dépêché. vérifié et constaté que je peux définir moi-même la limite de récursivité. En guise d'extension, vous pouvez également consulter la documentation du site officiel

En général, afin d'éviter les avantages et les plantages. , le langage python ajoute une limite au nombre de fois par défaut, donc si je change cette limite, est-ce que ça ira ?

import sys

# set le profondeur maximale de 20000

sys.setrecursionlimit(20000)

Insérez le code ci-dessus et changez-le de manière décisive. Maintenant, il ne devrait y avoir aucun problème. Mais le résultat était choquant. J'étais confus

et je n'ai pas continué à vérifier. J'ai demandé à mon ami Littlehann et j'en ai discuté, mais je n'ai pas approfondi cette question. Mais en ce qui concerne l'efficacité des opérations récursives dans les applications pratiques, il est en effet rare de voir l'utilisation de la récursivité sauf dans les manuels. Itérons, même si je ne suis pas très impressionné, mais une

instruction for

peut. être fait. Le code est le suivant :

Juste quelques lignes de code, d'un seul coup. En pensant à la dernière interview, l'intervieweur tx m'a posé des questions sur l'algorithme, à ce moment-là, il a mentionné l'utilisation de la récursivité pour implémenter une opération. Maintenant, réfléchissez-y, peut-il également être utilisé par itération ?

def calc(depth):
    tmp = 0
    result = 1
    
    for i in xrange(0,depth+1):
        cc = result
        if (cc ^ i)%4 == 0:
            tmp = 1
        else:
            tmp = 0
        result = result + (i)%7 + tmp
        
    return result
final = calc(11589)
print final

Cela fait longtemps, et je ne me souviens pas clairement de la question à ce moment-là, mais la leçon d'aujourd'hui est la suivante : dans la plupart des cas (moins de code écrit, estimation basée sur le ressenti), récursif L'efficacité est relativement faible. C'est certain. Cela a également été évoqué en classe

. L'efficacité de l'utilisation de l'itération est évidemment supérieure à celle de la récursivité (je ne me souviens pas clairement du concept spécifique d'itération). Utilisez au moins la

boucle

, je suis sûr qu'il n'y aura aucun problème avec des centaines de milliers. d'opérations, mais même si je change la limite de récursion, j'ai quand même rencontré un avertissementEnfin, un autre lien vers python long VS C long long est publié Si vous êtes intéressé, vous pouvez le consulter

<.>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!