Python: Rekursive Funktion, um die größte Zahl in der Liste zu finden

Ich versuche, eine Laborarbeit aus dem Lehrbuch Zelle Python Programming zu machen

Die Frage bat mich, "eine rekursive Funktion max() zu schreiben und zu testen, um die größte Zahl in einer Liste zu finden. Das Maximum ist das größere Teil des ersten Items und das Maximum aller anderen Items." Ich verstehe die Frage nicht aus dem Lehrbuch.

 def Max(list): if len(list) <= 1: else: return list[0] else: m = Max(list[1:]) return m if m > list[0] else list[0] def main(): list = eval(raw_input(" please enter a list of numbers: ")) print("the largest number is: ", Max(list)) main() 

Oder vielleicht nehme ich an, eine txt-datei mit nummern zu öffnen und dann rekursiv zu benutzen?

Ich glaube, rekursive Werke wie diese

 def function() > if something: >>return 0 >else: >>return function() 

7 Solutions collect form web for “Python: Rekursive Funktion, um die größte Zahl in der Liste zu finden”

Ihr Verständnis dafür, wie die Rekursion funktioniert, scheint gut zu sein.

Ihr if-Block ist durcheinander gebracht, Sie haben zwei else s zu eins, if und die Ausrichtung heraus ist. Du musst dein erstes else entfernen und un-indent alles unterhalb der if one level. z.B:

 def Max(list): if len(list) == 1: return list[0] else: m = Max(list[1:]) return m if m > list[0] else list[0] def main(): list = eval(raw_input(" please enter a list of numbers: ")) print("the largest number is: ", Max(list)) main() 

Hier ist ein weiterer Ansatz, um oben Problem zu lösen

 def maximum(L): if len(L) == 1: return L[0] else: return max(L[0],maximum(L[1:])) 

So Beispiel Eingang und Ausgang:

 L= [2,4,6,23,1,46] print maximum(L) 

Produziert

 46 

Der Grundansatz ist das.

  1. Wenn die Liste nur ein einziges Element enthält, ist dieses Element die max. Gib es sofort zurück.
  2. Andernfalls enthält die Liste mehrere Elemente. Entweder ist das erste Element in der Liste das Maximum, oder es ist nicht.
  3. Das Maximum des ersten Elements ist einfach das erste Element in der Liste.
  4. Rekursiv ruf Max auf den Rest (alles andere als erstes Element), um das Maximum dieser Elemente zu finden.
  5. Vergleichen Sie die Ergebnisse aus Schritt 3 und 4. Das Ergebnis ist die Zahl, die größer ist. Gib es zurück.

Im Moment hast du einige Syntaxfehler. Zum Beispiel hast du zwei else Klauseln für eine Single, und die Einrückung sieht komisch aus. Sie können nur einen else für einen if Block haben. Aber wenn Sie diesen Anweisungen folgen, sollten Sie einen Arbeitsalgorithmus haben.

 def Max(lis,maxx=-float("inf")): if len(lis) == 1: #only one element in lis return maxx if maxx>lis[0] else lis[0] #return lis[0] if it's greater than maxx else: m=lis[0] if lis[0]>maxx else maxx # m = max(lis[0],maxx) return Max(lis[1:],m) #call Max with lis[1:] and pass 'm' too print Max([1,2,39,4,5,6,7,8]) #prints 39 print Max([1,2,3,4,5,6,7,8]) #prints 8 

Diese Lösungen scheitern nach einer bestimmten Listengröße.

Das ist eine bessere Version:

 def maximum2(a, n): if n == 1: return a[0] x = maximum2(a[n//2:], n - n//2) return x if x > a[0] else a[0] def maximum(a): return maximum2(a, len(a)) maximum(range(99999)) >>> 99998 

Ich poste einen anderen Lösungsansatz des Problems. Die meisten Antworten manipulieren die Liste mit dem Slice-Operator in jedem rekursiven Anruf. Zu der Zeit, in der die Übung keinen strengen Funktionsprototyp zur Verfügung stellt, werde ich auch als Funktionsparameter die Länge der Liste übergeben.

Angenommen, wir versuchen, das maximale Element aus einer Sequenz S , von n Elementen zu finden und zurückzugeben.

Funktions-Prototyp: Max(S, n)

Basisfall: Wenn S nur ein Element enthält, gib es zurück. (Offensichtlich ist das einzige Element in der Sequenz das max.)

Recur: Wenn nicht der Basisfall, rufen Sie Max jedes Mal für ein weniger Element, das ist Anruf Max(S, n-1) . Dann speichern wir den zurückkehrenden Wert in eine Variable namens previous , die das vorherige Element aus der Sequenz anzeigt und diesen Wert mit dem nächsten Element in der Sequenz überprüft, welches das richtige Element des aktuellen rekursiven Anrufs ist und das Maximum dieser Werte zurückgibt .

Eine Rekursionsspur der obigen Prozedur ist in der folgenden Abbildung gegeben. Angenommen, wir versuchen, das Maximum aus einer Liste zu finden, die [5, 10, 20, 11, 3] .

Rekursionsspur

Hinweis: Um Ihnen weiter zu helfen, denken Sie daran, dass wir rekursiv die Liste von der rechten am meisten Element nach links am meisten iterieren

Schließlich ist hier der Arbeitscode:

 def find_max_recursively(S, n): """Find the maximum element in a sequence S, of n elements.""" if n == 1: # reached the left most item return S[n-1] else: previous = find_max_recursively(S, n-1) current = S[n-1] if previous > current: return previous else: return current if __name__ == '__main__': print(find_max_recursively([5, 10, 20, 11, 3], 5)) 

Hinweis: Die rekursive Implementierung funktioniert standardmäßig nur mit Sequenzen von 1000 meisten Elementen.

Um gegen unendliche Rekursionen zu bekämpfen, haben die Designer von Python eine absichtliche Entscheidung getroffen, die Gesamtzahl der Funktionsaktivierungen zu begrenzen, die gleichzeitig aktiv sein können. Der genaue Wert dieser Grenze hängt von der Python-Verteilung ab, aber ein typischer Standardwert ist 1000 . Wenn diese Grenze erreicht ist, erhöht der Python-Interpreter einen RuntimeError mit einer Meldung, maximum recursion depth exceeded .

Michael T. Goodrich (2013), Datenstrukturen und Algorithmen in Python , Wiley

Um den Standardwert zu ändern, gehen Sie folgendermaßen vor:

 import sys sys.setrecursionlimit(1000000) 
 def getMaxNumber(numbers): return 'NA' if len(numbers) == 0 else max(numbers) 
  • Python - Eigenschaftseinstellung aus der Liste verursacht maximale Rekursionstiefe überschritten
  • Trennungsliste mit Rekursion
  • Python-Rekursions- und return-Anweisungen
  • Rekursionsfunktion in Python
  • Refactoring rekursive "Vorkommen von" Funktion
  • Python rekursive Funktion, die von 0 bis n?
  • Python RuntimeError: maximale Rekursionstiefe überschritten
  • Rekursiv finden Sie die kth größte int in Liste der Liste der int in Python
  • N-Queen-Backtracking in Python: Wie gibt man Lösungen zurück, anstatt sie zu drucken?
  • Iteration in Rekursion umwandeln
  • Kreuz Produkt von Sets mit Rekursion
  • Python ist die beste Programmiersprache der Welt.