Rekursiv dekrementieren eine Liste durch 1

Sehr schnelle und einfache Hausaufgabe Frage. Ich habe es in Ordnung, aber ich finde es besser
Weg, es zu tun Eine mehr pythonische Art und Weise.
Hier ist mein Code, um rekursiv jedes Element einer Liste um 1 zu dekrementieren.

l = range(30) def recurseDecrMap(l, x = []): if len(l) == 0: return [] else: x.append(l[0] -1) recurseDecrMap(l[1:], x) return x 

Also danke für jede Eingabe. Ich versuche zu lernen, bessere Rekursion zu machen. Schwierigkeiten bekommen
Das macht es.

7 Solutions collect form web for “Rekursiv dekrementieren eine Liste durch 1”

Sie können nur ein Argument verwenden, meiner Meinung nach ist es einfacher:

 def recurseDecrMap(l): if not l: return [] else: return [l[0]-1] + recurseDecrMap(l[1:]) 

Aber wie @jamylak darauf hingewiesen hat, ist die Komplexität dieses Algorithmus O (N ^ 2), da l[1:] eine neue Liste mit Verweisen auf den Rest der Elemente in der Liste erstellt.

Wenn Sie Effizienz benötigen, würde ich Ihnen empfehlen, Listenverständnisse zu verwenden ( Haidros Antwort ), aber ich nehme an, dass es keine Priorität ist, wenn Sie es nur für Lernzwecke wollen.

Wahrscheinlich weniger pythonisch, aber da:

 def recurseDecrMap(l): return [l[0]-1] + recurseDecrMap(l[1:]) if l else [] 

Für was es wert ist, ist dies eine schreckliche Art, über Rekursion zu lernen, weil Sie es verwenden, um etwas zu tun, das nicht inhärent rekursiv ist. Wenn dein Lehrer dich wirklich bittet, ein Programm zu schreiben, das die Elemente einer Liste wie [1, 2, 3, 4] rekursiv dekrementiert, dann beschämt auf ihn / sie.

Wie Haidro bemerkte, ist die pythonischste Lösung, um dieses Problem zu lösen, nur über die Liste mit einem Listenverständnis zu iterieren

 [i - 1 for i in l] 

Als Schleife ist das so

 def decr(l): a = [] for i in l: a.append(i - 1) return a 

Rekursion ist nützlich, wenn Sie das gleiche Problem auf beliebigen Tiefenstufen lösen wollen. Zum Beispiel, sagen Sie, Sie hatten so etwas wie [1, [2, 3], [[4], 5]] und Sie wollten jede Zahl um 1 dekrementieren, während die Listenstruktur beibehalten wurde. In diesem Fall würde eine rekursive Lösung die iterative Lösung für den Basisfall verwenden und sich für den rekursiven Fall nennen.

 def decr_recursive(l): a = [] for i in l: if isinstance(i, list): a.append(decr_recursive(i)) else: a.append(i - 1) return a 

Dies kann leicht geändert werden, wenn Sie mehr als nur Listen oder Ganzzahlen unterstützen möchten.

 >>> decr([1, [2, 3], [[4], 5]]) [0, [1, 2], [[3], 4]] 

Dies ist die Art von Problem, das sehr schwer zu lösen ist, ohne Rekursion zu verwenden, ist aber leicht zu lösen. Was du fragst, ist die Art von Problem, das einfach ohne Rekursion zu lösen ist (es ist nur eine einfache Iteration über eine Liste um Gottes willen), aber etwas schwierig, damit zu lösen.

Einige Gründe, warum Sie Rekursion in Python vermeiden sollten

  • Es ist schwerer zu lesen. Vergleichen Sie [i - 1 for i in l] , oder sogar die explizite Schleife, um so etwas wie

     def decr(l): if not l: return [] return [l[0] - 1] + decr(l[:1]) 
  • Das Aufrufen einer Funktion in Python kann teuer sein. Ich bekomme ungefähr die gleichen Zeitpunkte wie Ashwini Chaudhary auf meinem Computer. Aber [i - 1 for i in range(10**4)] nimmt 559 μs auf meinem Computer. Das ist drei Größenordnungen schneller als die schnellste rekursive Methode.

  • Rekursive Funktionen funktionieren nicht über 1000 Anrufe, es sei denn, Sie setzen die Rekursionsgrenze höher ein. Vielleicht hast sys.setrecursionlimit(10**5) die Antwort von sys.setrecursionlimit(10**5) in der Antwort von Ashwini Chaudhary bemerkt. Dies ist notwendig, weil ohne sie, würde jeder Anruf zu einem RuntimeError: maximum recursion depth exceeded nach einem riesigen Traceback. Aber auch mit diesem, eine etwas größere Liste würde immer noch zu einer Rekursionsgrenze führen. Und nach der Dokumentation gibt es eine Top-Grenze für jedes Betriebssystem, und die Einstellung zu hoch kann zu einem Absturz führen.

  • Rekursive Funktionen sind schwerer zu debuggen. Nicht nur verschmutzen sie Ihre Stack-Traces mit Hunderten von Anrufen aus der gleichen Funktion, aber sie sind konzeptionell schwerer zu folgen, denn der gleiche Teil der gleichen Funktion wird auf unterschiedliche Weise verwendet, je nachdem, welche Ebene in den Stapel Sie sind in Die natürliche menschliche Denkweise ist iterativ. Wir machen die Dinge eins zu einer Zeit. Unsere eigenen Gehirne sind nur ein paar Stufen tief, also haben wir eine sehr harte Zeit, Probleme auf rekursive Weise zu lösen, wie "lass mich anfangen, ein Problem zu lösen, aber bevor ich fertig bin, lass mich ein anderes Problem lösen und dann Wenn ich fertig bin, werde ich das ursprüngliche Problem beenden, und im kleineren Problem kann ich dasselbe tun, damit ich mehrere Level tief finde, bevor ich fertig bin. " Deshalb gehst du in die Küche, um einen Stift zu bekommen, dann siehst du eine Schokoriegel und fängst es zu essen, und wenn du fertig bist, vergisst du den Stift. Sie "rekursierten" ein Niveau, vom Stiftproblem zum Süßigkeitstabproblem, und Ihr geistiger Stapel wurde zu tief (gerade zwei Niveaus, aber das ist genug). Wenn du stattdessen die Schokoriegel gepackt hättest, aber bevor du es geöffnet hast und es angefangen hast, es zu finden, fand man auch den Stift (das beste iterative Analoge, mit dem ich kommen könnte), das hättest du beide ohne zu vergessen. Die Art und Weise, wie Sie Probleme in Programmen lösen sollten genau so sein, wie Sie sie in Ihrem Kopf lösen, denn das ist der einzige Weg, den Sie verstehen, was Ihr Code tut. Python ist so eine großartige Sprache, denn seine High-Level-Schnittstelle lässt Sie genau das machen (zumindest häufiger als in niedrigeren Sprachen). Verwenden Sie diese Tatsache!

Hier ist der schlimmste Weg – mit Fixed Point Combinator :

 Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg))) recurseDecrMap = Y(lambda f: lambda l: [l[0]-1] + f(l[1:]) if l else []) 

Hier ist eine einfache pythonische Art:

 >>> mylist = range(30) >>> def func(l): ... return [i-1 for i in l] >>> func(mylist) [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28] 

Erläuterung:

Ich verwendete Listenverständnisse , um eine neue Liste aller Elemente in mylist deren Wert ein kleiner ist als das, was es war.

Es ist nichts falsch mit deinem Code, außer wenn du es mehr als einmal benutzen wirst:

 >>> recurseDecrMap(l) [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28] >>> recurseDecrMap(l) [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28] 

Um dies zu vermeiden, schau doch diese Antwort an .

Timing Vergleiche von verschiedenen Möglichkeiten, dies zu tun:

 In [1]: import sys In [2]: sys.setrecursionlimit(10**5) In [3]: from so import * In [4]: %timeit recur(range(10**4)).show() 10 loops, best of 3: 18.2 ms per loop In [5]: %timeit recurse1(range(10**4)) 1 loops, best of 3: 559 ms per loop In [6]: %timeit recurse2(range(10**4)) 1 loops, best of 3: 1e+03 ms per loop In [7]: %timeit recurse3(range(10**4)) 1 loops, best of 3: 1.02 s per loop In [8]: %timeit recurse4(range(10**4)) 1 loops, best of 3: 596 ms per loop 

Code:

 class recur: # No extra memory is required in this method def __init__(self,lis): self.lis=lis self.len=len(self.lis) self.rec(0) def show(self): return self.lis def rec(self,n): if n!=self.len: self.lis[n]-=1 self.rec(n+1) def recurse1(l,lis=None): lis=lis if lis is not None else [] if l: lis.append(l[0]-1) return recurse1(l[1:],lis) else: return lis def recurse2(l): return [l[0]-1] + recurse2(l[1:]) if l else [] def recurse3(l): if len(l) == 0: return [] else: return [l[0] -1] + recurse3(l[1:]) def recurse4(l, x = []): if len(l) == 0: return [] else: x.append(l[0] -1) recurse4(l[1:], x) return x 

Hier ist eine rekursive Lösung, die mit großen Listen fertig werden kann, ohne die Rekursions-Tiefengrenze zu treffen. Durch die Teilung und Eroberung der Rekursionstiefe ist O (log (N)) im schlimmsten Fall im Vergleich zu O (N) mit naiver Rekursion. Jede Art von Rekursion ist eine schlechte Wahl der Technik für dieses Problem aber, da es trivial gelöst mit einer einfachen for-Schleife ist.

 def dec_list(xs, a, b): if b == a + 1: xs[a] -= 1 if a + 1 >= b: return mid = (a + b) // 2 dec_list(xs, a, mid) dec_list(xs, mid, b) def dec(xs): dec_list(xs, 0, len(xs)) xs = range(1001) dec(xs) print xs 
  • Baktracking-Funktion, die die Berechnung berechnet, überschreitet die maximale Rekursionstiefe
  • Refactoring rekursive "Vorkommen von" Funktion
  • Finde alle Index mit Rekursion
  • Python-Rekursions- und return-Anweisungen
  • Python rekursiver Funktionsfehler: "maximale Rekursionstiefe überschritten"
  • Python RuntimeError: maximale Rekursionstiefe überschritten
  • Das max-Element in einer Sequenz mit Rekursion zu finden
  • Lock-Kombinationen für dynamische Sperrgröße
  • Rekursive dircmp (vergleiche zwei Verzeichnisse, um sicherzustellen, dass sie die gleichen Dateien und Unterverzeichnisse haben)
  • Gibt es eine Möglichkeit, eine rekursive Funktion zu schreiben, die alle ganzen Zahlen in einer Liste durchsucht und sieht, ob irgendwelche zwei gleich einer negativen Summe sind?
  • Rekursionsfunktion funktioniert nicht richtig
  • Python ist die beste Programmiersprache der Welt.