, wie die Ausgabe komplexer rekursive Funktion zu bestimmen, von Hand

Question

Hier ist der rekursiven Code in Frage:

def trace(a, b): 
    if (a > b): 
     return -1 
    elif (a == b): 
     print (a * a) 
     return a * a 
    else: 
     m = (a + b)/2 
     return trace (a, m) + trace (m + 1, b) 

x=trace(1,4) 

während ich bin nicht sicher, was diese Funktion tun soll, werden wir die Ausgabe von x=trace(1,4) finden soll zusammen mit dem Wert von x, von Hand (was bedeutet, dass wir den Leerlauf nicht verwenden können, um uns zu helfen).

Nach einiger Zeit habe ich festgestellt, dass die Funktion 1 und 12,25 drucken wird, was der Ausgabe sein wird, wenn x trace(1,4) zugewiesen wird.

Allerdings kann ich nicht bestimmen, wie der Wert von X sein wird. Obwohl die Antwort -91.75 ist, habe ich nicht den leisesten Hinweis, wie es abgeleitet wurde (obwohl ich weiß, wie lange es dauern würde, um diese Antwort zu finden, und ich bin mir nicht sicher, wie wir schnell auf die Lösung in kurzer Zeit, zB beim Verfassen einer Prüfung).

Vielen Dank im Voraus für Ihre Hilfe!

Answer 1

haben einen Blick auf diese Zeilen:

m = (a + b)/2 
return trace(a, m) + ... 

diese Linien nur noch ausgeführt werden, wenn b größer als a ist. Das bedeutet, m wird immer größer als a und der erste rekursive Funktionsaufruf hat genau das gleiche Problem. Mit den Werten a = 1 und b > a konvergiert m zu 1. In der Theorie endet die Rekursion nie, da m niemals 1.0 oder weniger sein wird. Die Float-Genauigkeit ist jedoch begrenzt, daher gibt es einen Punkt (nach vielen rekursiven Aufrufen), bei dem der Prozessor m nicht von 1.0 abweichen kann. An diesem Punkt wird elif (a == b): wahr und stoppt die Rekursion. Das erklärt nicht, warum das Ergebnis -91.75 ist, aber es zeigt, warum es fast unmöglich ist, alle rekursiven Aufrufe in einem Diagramm oder Baum oder etw anzuzeigen. Ich hoffe, es hilft.

Answer 2

Zunächst habe ich betrogen. Mit dem meiner Brust hier sind ein paar Hinweise: Die Funktion ist definitiv nicht für Python 3 gedacht! Der Grund ist der Operator /. In Python 2 führte dies zu Integern in Python3, die zu Floats führten. Unter Berücksichtigung dieser Voraussetzung ist hier meine Lösung:

Die Funktion ist nicht komplex. Der Datentyp jeder Ihrer Variablen ist Integer! m wird immer eine ganze Zahl sein. x ist 30. Die Rekursionsstufe ist drei, was sieben Aufrufen Ihrer Funktion entspricht (einschließlich der ersten). Und hier geht es um Dinge wie diese: Holen Sie sich Papier und einen Stift und schreiben Sie jeden Schritt auf.

1. Der Eingang ist: a = 1 und b = 4, die in Ihrer Funktion zum anderen Teil führt ... bisher keine Ausgabe. Dort wird m als (1 + 4)/2 berechnet. In meinem Buch ist das 2.5. Aber das ist auf 2 gerundet, weil wir ganze Zahlen haben. Dann beginnt die Rekursion mit zwei Aufrufen (1,2) und (3,4)
2. Betrachten wir (1,2): a = 1 und b = 2. Wieder keine Ausgabe und wir gehen direkt zum else-Teil: m wird als 3/2 berechnet, was eine nette 1,5 auf 1 gerundet ist. Wieder zwei Aufrufe der Funktion mit neuen Parametern (1,1) und (2, 2). Beachten Sie, dass beide Aufrufe nun in den Elif-Teil der Funktion eintreten und jeder einen Ausgabe- und Rückgabewert erzeugt. Sie können (1,1) durch 1 und (2,2) durch 4 ersetzen. Die Rekursion wird hier ausgeführt, und der Aufruf von trace (1,2) ergibt 5. Betrachten wir den anderen Zweig der Rekursion.
3. Der Eingang ist a = 3 und b = 4, was zu einem weiteren Rufpaar mit den folgenden Parametern führt: (3,3) und (4,4). Ich denke, jetzt sollten Sie den Dreh raus bekommen. Der Spaßfaktor besteht darin, alle Rückgabewerte so zusammenzufassen, wie sie bereitgestellt werden.

In Bezug auf was die Funktion tut: Es fasst alle Quadrate aller ganzen Zahlen zwischen a und b.