rekursive Suche boolesche Rückgabefunktion

Question

Schreiben Sie eine rekursive Funktionssuche (l, key), die einen booleschen Wert zurückgibt: True, wenn der Schlüssel in der Liste l steht; Falsch, wenn es nicht ist. Beschreiben Sie die Basisfälle und wie sich das kleinere Problem auf das größere bezieht. Sie können den Listenoperator in oder die Listenmethode index() nicht verwenden.

Kann mir jemand erklären, was ich hier für die Beschreibung tun muss? Ich weiß nichts über Rekursion, um zu wissen, wo ich anfangen soll. Es ist für eine Prüfungsüberprüfungslaboraufgabe.

Hier ist der Code, den ich zur Verfügung gestellt habe.

def search(l,key): 
    """ 
    locates key in list l. if present, returns True; else returns False. 
    PRE: l is a list. 
    POST: l is unchanged; returns True if key in l; False otherwise. 
    """ 

Probe Main:

l1 = [1, '2', 'x', 5, -2] 

print search(l1, 'x') # should output: "True" 

print search(l1, 2)  # should output: "False" 

Answer 1

Alle Rekursion neigt dazu, die gleichen Regeln zu folgen:

• einen oder mehr Abschluss Fälle.
• Jeder andere Fall ist eine etwas einfachere Form des aktuellen Falls.

So zum Beispiel eine (sehr ineffizient) Art und Weise zwei positive Zahlen addieren a und b:

• wenn b Null ist, kehren ein. Geben Sie andernfalls die beiden Nummern a+1 und b-1 ein.

Etwas wie:

• , wenn die Liste leer ist, Sie nicht das finden sie: return false

  def addtwo (a, b): 
      if b == 0: 
       return a 
      return addtwo (a+1, b-1) 
  

  Nun ist über die Fälle für Ihre Zuordnung lassen denken.

• Wenn das erste Element der Liste Ihrem Schlüssel entspricht, haben Sie Folgendes gefunden: return true.
• andernfalls in der Liste suchen, indem Sie das erste Element entfernen.

In Pseudo-Code (die sehr ähnlich wie Python ist aber unterschiedlich genug, dass Sie einige Arbeit zu tun haben würden):

def search (list, key): 
    if list is empty: 
     return false 
    if key == first item in list: 
     return true 
    return search (list with first element removed, key) 

Answer 2

Jede Frage bezüglich Rekursion sollte mit derselben behandelt werden Art und Weise (in der Regel) ... fragen Sie sich, was die base case ist und dann auf, dass für höhere Fälle bauen ...

Also in dieser Frage, fragen Sie sich, wenn ich dort sicher sein kann, nicht key im list ist .. Es ist offensichtlich, wenn die Liste leer ist, du bist sicher, dass sie nicht vorhanden ist.

Für eine größere Liste, vergleichen Sie das erste Element, wenn es das gleiche wie die key ist, Sie True sofort zurück, aber es ist einhüllen nicht, Sie führen alle Prüfungen für die rest of the list ....

So studieren Sie alle diese Aspekte, Hier ist Ihr Algorithmus. für die Verwendung einen Klein ‚l‘ als Kennung in seinem Beispielcode

function locate(lst,key) 
    if lst == emptylist then return False 
    if lst[0] == key then return True 
    else return locate(lst[1..],key) //i use the notation lst[1...] to indicate list starting from 1 index.