Iteration und Rekursion in Python

Wenn eine Situation auftritt, ist eine rekursive Operation erforderlich, aber die Anzahl der Rekursionen ist sehr groß und beträgt mehr als 10.000 Mal. Lassen Sie uns nicht über die Rekursion von mehr als 10.000 Mal sprechen. Der ursprüngliche Testcode ist in Java. Ohne JDK und Kompilierungsumgebung verwenden wir Python

Schauen wir uns zuerst den ursprünglichen Java-Code an:

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));
    }
}

Ich habe nicht viel mit Java gespielt, aber diese Codezeilen sind trotzdem stressfrei. Ich werde das Chaos schnell beseitigen und es in Python-Code ändern

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

Fügen Sie den Code ein, F5, etwas ist schiefgelaufen

Diese Version des Codes dauerte ursprünglich nicht lange, weil eine Folge von zehnstelligen Ganzzahlen direkt verwendet werden kann Es kann verwendet werden, daher bezweifle ich, dass es etwas mit long zu tun hat

Natürlich hat es tatsächlich nichts mit long zu tun Die von unterstützte Ganzzahllänge Python ist sehr lang. Siehe den zuvor geschriebenen Code:

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

Der obige Code wandelt eine lange Folge von Dezimalzahlen in eine hexadezimale Darstellung um, oder es kann kann in ein beliebiges Hexadezimalsystem oder in ein hexadezimales Oktalsystem konvertiert werden. Und hexadezimal, verwenden Sie einfach oct(), hex(), um es zu lösen, und verwenden Sie die euklidische Division, um es zu lösen

Daher kann es gesehen werden Dass der Fehler nicht in der Größe der Zahl liegt, ist 11589 ja gerade bei Computern nur eine Beilage, 2^16 und 65536 gibt es

Eigentlich habe ich es erst hier herausgefunden dass der wahre Grund für den vorherigen rekursiven Fehler nicht erwähnt wurde und ich verärgert war

Der Grund für den rekursiven Fehler lag an Python. Das Standard-Rekursionslimit beträgt nur etwa 1000 Mal, aber hier müssen wir 10000 ausführen Ich habe lange damit verbracht, es zu putzen: RuntimeError: maximale Rekursionstiefe überschritten

Also habe ich es schnell überprüft und festgestellt, dass ich das Rekursionslimit selbst festlegen kann Erweiterung, Sie können auch die offizielle Website-Dokumentation überprüfen

Um Vorteile und Abstürze zu vermeiden, fügt die Python-Sprache im Allgemeinen standardmäßig ein Limit für die Anzahl der Male hinzu. Wenn ich dieses Limit also ändere, wird dies der Fall sein OK?

import sys

# setze die maximale Tiefe auf 20000

sys.setrecursionlimit(20000)

Füge den obigen Code ein und ändere ihn entscheidend auf 20000. Jetzt sollte es kein Problem mit dieser Einschränkung geben, aber das Ergebnis war schockierend. Ich war verwirrt

und habe nicht weiter nachgefragt Ich habe es besprochen, bin aber nicht näher auf dieses Thema eingegangen. Aber wenn es um die Effizienz rekursiver Operationen in praktischen Anwendungen geht, sieht man die Verwendung von Rekursion tatsächlich selten, außer in Lehrbüchern, obwohl ich nicht allzu beeindruckt bin, aber eine for-Anweisung kann damit umgehen

Der Code lautet wie folgt:

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

Mit nur wenigen Codezeilen war es im Handumdrehen erledigt. Als ich an das letzte Interview dachte, fragte mich der TX-Interviewer nach dem Algorithmus. Damals erwähnte er die Verwendung von Rekursion zur Implementierung einer Operation.

Es ist lange her und ich kann mich damals nicht mehr genau an die Frage erinnern, aber die heutige Lektion lautet: In den meisten Fällen (weniger Code geschrieben, Schätzung basierend auf Gefühl) rekursiv Die Effizienz ist relativ niedrig. Das wurde auch im Unterricht erwähnt

. Die Effizienz der Iteration ist offensichtlich höher als die der Rekursion (ich erinnere mich nicht genau an das spezifische Konzept der Iteration). Ich bin mir jedoch sicher, dass es auch nach Hunderttausenden von Operationen kein Problem geben wird Wenn ich das Rekursionslimit geändert habe, bin ich immer noch auf einen Strike gestoßen

Schließlich posten Sie einen Link zu Python Long VS C Long Long. Wenn Sie interessiert sind, können Sie es sich ansehen