Codeanalyse für JavaScript-Rekursion und Schleifenleistungsvergleich

In Bezug auf die Leistung hat die Rekursion keinen Vorteil gegenüber Schleifen. Zusätzlich zum Overhead mehrerer Funktionsaufrufe kann die Rekursion in manchen Fällen auch zu unnötigen wiederholten Berechnungen führen. Nehmen wir zum Beispiel ein rekursives Programm, das die Fibonacci-Folge berechnet. Beim Finden des n-ten Elements A(n) wird jedes Element ausgehend vom n-ten Element wiederholt berechnet. Je kleiner die Anzahl der Elemente, desto häufiger wird sie wiederholt. Sei B(i) die Häufigkeit, mit der das i-te Element berechnet wird, dann gibt es

B(i)=1; (i)=B(i +1)+B(i+2); i
Auf diese Weise bildet B(i) eine interessante inverse Fibonacci-Folge. Wenn wir A(n) finden, gilt:

B(i)=A(n+1-i)

Aus einem anderen Blickwinkel betrachtet sei C(i) zu finden A(i) Die Anzahl der erforderlichen Additionen beträgt:

C(i)=0, 1

C(i)=1+C(i-1)+C (i -1); i>1

Sei D(i)=C(i)+1, es gibt

D(i)=1; >
D(i)=D(i-1)+D(i-1)

D(i) bildet also eine weitere Fibonacci-Folge. Und es kann geschlossen werden:

C(n)=A(n+1)-1

Und A(n) wächst in einer geometrischen Reihe, diese redundante Wiederholung in n Es wird ganz erstaunlich, wenn es größer ist. Das entsprechende Programm, das Schleifen verwendet, hat

B(n)=1; n ist ein beliebiger Wert

C(n)=0, 1

C(n). )=n-1; n>1

Daher ist das Programm, das die oben angegebenen Schleifen verwendet, viel schneller als das Programm, das Rekursion verwendet.

Wie bei Schleifen kann auch dieser Fehler bei der Rekursion behoben werden. Wir müssen uns nur die berechneten Terme merken und können bei der Suche nach höheren Termen die vorherigen Terme direkt lesen. Diese Technik ist bei der Rekursion üblich und wird als Auswendiglernen bezeichnet.

Das Folgende ist ein rekursiver Algorithmus zum Finden der Fibonacci-Folge mithilfe der Speichertechnologie.

Das obige ist der detaillierte Inhalt vonCodeanalyse für JavaScript-Rekursion und Schleifenleistungsvergleich. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!