Rekursionseinstieg: Fakultät - Logikproblem!?

Logikproblem

Func fa($num,$faktor)
MsgBox(0,$num,$faktor); dient nur zur kontrolle und zeigt das richtige an
$faktor = $faktor - 1
If $faktor = 1 Then Return $num
$num = $num * $faktor
Return fa($num,$faktor)
EndFunc
$n=4
$f=4
$p=fa($n,$f)
MsgBox(0,"Fakultät von: "&$n,$p)l

edit: Erläuterung:
Nur die innerste Funktion gibt "24" an die nächstaäußere Funktion zurück, diese gibt den Rückgabewert nicht weiter.
Deshalb muss da Return fa($num,$faktor) statt nur fa($num,$faktor) stehen.

Anmerkung: Rekusion ist um einiges langsamer als Iteration!

$n = 25

$bench_start = TimerInit()
ConsoleWrite(Fibonacci_i($n) & @CRLF)
$bench_end_i = Round(TimerDiff($bench_start), 4)

$bench_start = TimerInit()
ConsoleWrite(Fibonacci_r($n) & @CRLF)
$bench_end_r = Round(TimerDiff($bench_start), 4)

ConsoleWrite(@CRLF & "Iterative: " & $bench_end_i & " ms" & @CRLF & "Recursive: " & $bench_end_r & " ms" & @CRLF & "Diff: " & Abs($bench_end_i - $bench_end_r) & " ms !" & @CRLF & @CRLF)

Func Fibonacci_i($f)
Dim $arr_fib[3]
$arr_fib[0] = 0
$arr_fib[1] = 1
For $i = 2 To $f
$arr_fib[2] = $arr_fib[1] + $arr_fib[0]
$arr_fib[0] = $arr_fib[1]
$arr_fib[1] = $arr_fib[2]
Next
Return $arr_fib[2]
EndFunc

Func Fibonacci_r($f)
If $f = 0 Then Return 0
If $f = 1 Then Return 1
Return Fibonacci_r($f - 1) + Fibonacci_r($f - 2)
EndFunc

Woran das hängt kann ich nicht sagen! Habe mal dazu ein Thread im engl. Forum erstellt, aber die Dev. haben nichts konkretes sagen können! Für Rekursion ist AutoIt wohl eher nicht geeignet!

Also nach Möglichkeit Rekursion vermeiden!

Ob das auch so in anderen Sprachen, wie z.B. C/C++ ist?

Gruß,
UEZ

Zitat von peethebee

Grundsätzlich mal ja.
Funktionsaufrufe sind teuer, weil man Variablen sichern muss beim Aufruf und bei der Rückkehr. Außerdem muss man die Funktion in der Funktionstabelle nachschlagen und dahin springen. Das ist natürlich relativ umso teurer, je weniger Code pro Iteration/Funktionsaufruf abgearbeitet wird :).
Die Stärke des Effekts kann natürlich variieren.
Zudem kann mancher Compiler (einfache) Rekursionen in Iterationen umbauen.

Johannes

Da stimme ich dir vollkommen zu, aber ist der Unterschied so krass wie in AutoIt? In meinem Beispiel wächst der Unterschied exponential mit n!

Gruß,
UEZ

Zitat von UEZ

In meinem Beispiel wächst der Unterschied exponential mit n!

Das ist mathematisch begründet und nicht informationstechnisch.
Du hast dir zwar ein schönes Beispiel herausgesucht aber es taugt nicht für einen allgemeingültigen Vergleich zwischen Rekursion und Iteration.
Bei der Fibonacci-Folge baut jede Fibonacci-Zahl auf "niedrigeren" Fibonacci-Zahlen auf.
Bei der Rekursion werden diese "niedrigeren" Fibonacci-Zahlen für jede Fibonacci-Zahl neu berechnet und damit unnötigerweise mehrmals berechnet.
Bei deiner iterativen Variante werden die letzen Fibonacci-Zahlen gepspeichert und für die Berechnung folgender Fibonacci-Zahlen mehrmals verwendet - eine Fibonacci-Zahl wird insgesamt also nur einmal berechnet - im Gegensatz zur Rekursion.
Da ist der exponentielle Anstieg im Vergleich zu dieser iterativen Methode nur logisch - aber er ist rein mathematisch begründet - auch in reinem Assembler gegossen würdest du diesen Anstieg feststellen.

Zitat

Das ist mathematisch begründet und nicht informationstechnisch.

Da gebe ich dir nur teilweise recht!

Zitat

Du hast dir zwar ein schönes Beispiel herausgesucht aber es taugt nicht für einen allgemeingültigen Vergleich zwischen Rekursion und Iteration.

Hast du ein besseres Beispiel? Wenn ja, dann bin ich sehr gespannt darauf!

Zitat

Bei der Fibonacci-Folge baut jede Fibonacci-Zahl auf "niedrigeren" Fibonacci-Zahlen auf.
Bei der Rekursion werden diese "niedrigeren" Fibonacci-Zahlen für jede Fibonacci-Zahl neu berechnet und damit mehrmals berechnet.
Bei deiner iterativen Variante werden die letzen Fibonacci-Zahlen gepspeichert und für die Berechnung folgender Fibonacci-Zahlen mehrmals verwendet - eine Fibonacci-Zahl wird also nur einmal berechnet - im Gegensatz zur Rekursion.

Und deswegen liegt die Laufzeit so weit auseinander? Eine Verdoppelung würde ich ja noch akzeptieren.

Zitat

Da ist der exponentielle Anstieg im Vergleich zu dieser iterativen Methode nur logisch - aber er ist rein mathematisch begründet - auch in reinem Assembler gegossen würdest du diesen Anstieg feststellen.

Das es einen Unterschied zwischen Rekursion und Interation gibt, da Rekusion mehr Berechnungen hat, ist mit schon klar, aber das der Unterschied so gewaltig ist, ist mir ein Rätsel. Liegt sehr wahrscheinlich an AutoIt und dessen internen Strukturen.

Ich werde demnächst mal das Beispiel in C++ coden und messen, ob dort der Unterschied so groß ist.

Gruß,
UEZ

Zitat von UEZ

Hast du ein besseres Beispiel? Wenn ja, dann bin ich sehr gespannt darauf!

Fühl dich bitte nicht angegriffen wo gar keine Kritik da war.
Lies bitte nochmal ganz genau was ich geschrieben habe dann erkennst du das das Problem nicht die Vorgehensweise beim berechnen ist sondern die Berechnung selber.
Bei der Rekursion müssen in deinem Beispiel mehr Berechnungen durchgeführt werden als bei der Iteration.
Genauer gesagt steigt dieser Unterschied in der Anzahl der notwendigen Berechnungen exponential.
Um dir das noch deutlicher zu machen hab ich dir mal den Rekursionsbaum zur Berechnung von Fib(5) aufgemalt:
autoit.de/wcf/attachment/7452/
Wie du sehen kannst müssen für jeden Zweig die niedrigeren Fibonacci-Zahlen neu berechnet werden - egal ob sie schon einmal in einem anderen Zweig berechnet wurden.
Das heißt die meisten Zahlen werden unnötigerweise mehrmals berechnet!
Und das jedesmal mit allen wiederrum darunter liegenden Fibonacci-Zahlen.
Bei der Variante mit der Iteration wird das anders gemacht - da werden die letzten Fibonacci-Zahlen gespeichert und können so gleich zur Berechnung der nächsten Zahlen genommen werden ohne noch einmal ausgerechnet werden zu müssen.
Jede Zahl wird nur einmal berechnet!
Bei der Rekursion schaukelt sich das mit steigender Fibonacci-Zahl hoch.
Es hängt also nicht damit zusammen das bei einer Rekursion ständig die Funktion in der Function-Table nachgeschlagen werden muss usw.
Kann sein das es einen Einfluss hat - aber hier wird er definitiv ums zigfache durch die Rechenmethode überlagert.
Deswegen sagte ich das dies nicht repräsentativ ist für einen reinen Technik-Vergleich zwischen Iteration und Rekursion.
Und nein - ich hab kein besseres Beispiel - darum ging es hier auch nicht.
Ich wollte dich lediglich darauf hinweisen das du für die Erklärung des Phänomens in der falschen Kiste suchst - es hat nichts mit dem Konzept sondern mit der mathematischen Umsetzung.
Ich hoffe anhand des Bildes ist dir nun klar warum folgende Aussage nicht zutreffen kann:

Zitat von UEZ

Und deswegen liegt die Laufzeit so weit auseinander? Eine Verdoppelung würde ich ja noch akzeptieren.

Und sorry falsch ich dich irgendwie angegriffen habe - das war mir nicht bewusst und auch definitiv nicht gewollt.
Ich wollte dir lediglich die mathematische Begründung für den exponentiellen Anstieg erklären - nicht mehr.

Ihr habt mich überzeugt, dass die Rekusion von den Fibonacci nicht mit AutoIt, sondern wirklich mit der Rekursionstiefe und somit mit der Anzahl der Berechnungen zu tun hat!

@AspinirinJunkie: ich habe deine berechtigte Kritik nicht als Angriff angesehen! Ich dachte nur, dass der Unterschied nicht so krass sein würde! Ich habe mir den Rekursionsbaum für n=3 angeschaut, aber daraus lässt sich nicht klar absehen, dass die Berechnungen exponentiell zunehmen!

Jeder sollte Kritik nicht als Angriff ansehen, sondern eher als eine konstruktive Diskussionsgrundlage!

DANKE,
UEZ

Coole Optimierung der Rekusion!

Wobei bei mir die Iteration immer noch schneller ist:

Iterative : 0.454 ms
Recursive : 0.0036 ms -> hab's auskommentiert, damit ich nicht lange warten muss für n=50
Recursive2: 1.9964 ms

n=2500:

Iterative : 9.8585 ms
Recursive2: 29.6587 ms

Gruß,
UEZ

Irgendwie kommt mir deine optimierte Variante bekannt vor - vielleicht noch aus dem Studium...

Zitat

Die Iterative Variante hat auch noch einen Fehler bei kleinen Fib. Zahlen (0, 1)

Da ist die Abfrage für n < 2 nicht implementiert

Func Fibonacci_i($f)
If $f = 0 Then
Return 0
ElseIf $f = 1 Then
Return 1
Else
$arr_fib_n0 = 0
$arr_fib_n1 = 1

For $i = 2 To $f
$arr_fib = $arr_fib_n1 + $arr_fib_n0
$arr_fib_n0 = $arr_fib_n1
$arr_fib_n1 = $arr_fib
Next

Return $arr_fib
EndIf
EndFunc

So ab n = 10 wird die Iteration schneller..

Gruß,
UEZ

@Raptor
Dankeschön - wieder was gelernt: Wusste gar nicht das AutoIt Funktionsüberladung zulässt

UEZ
Dem hab ich nichts hinzuzufügen - seh das genauso

Hab, um die Eingangsfrage zu klären, das ganze mal in C++ gegossen (auch Raptors Methode mit inbegriffen):

#include <fstream>
#include <vector>
#include <stdio.h>
#include <windows.h>


using namespace std;


unsigned long long fiboRek1(long int  n){
         if (n<=1) return n;
         return fiboRek1(n-1) + fiboRek1(n-2);
}


unsigned long long fiboIt(long int n){
         std::vector<long long> v;
         v.push_back(0);
         v.push_back(1);
         for (long int i=2; i<=n; i++)
             v.push_back(v[i-1]+v[i-2]);  
         return v[n];
}


unsigned long long fiboRek2(long int);
unsigned long long fiboRek2(long int, long int, long int);




int main(){
    unsigned i;
    int n;

    LARGE_INTEGER lStart, lEnd, lFreq;


    QueryPerformanceFrequency(&lFreq);

    printf ("Bis zu welcher Fibonacci-Zahl soll gerechnet werden?: ");
    scanf ("%d",&n);

    ofstream out("FiboOut.txt", ios::out);

    out << "Fib-Zahl	 Erg_It            t_It [ms]   Erg_Rek        t_Rek [ms]   Erg_Rek2          t_Rek2 [ms]";

    for(i=0; i<=n;i++){
             out << endl;
             out.width(4); 
             out<<i;
             QueryPerformanceCounter(&lStart);
             out.width(30);
             out<<fiboRek1(i);
             QueryPerformanceCounter(&lEnd);
             out << "    tRek1=";
             out.width(6);
             out << ((lEnd.QuadPart - lStart.QuadPart) * 1000) / lFreq.QuadPart;


             QueryPerformanceCounter(&lStart);
             out.width(30);
             out << fiboIt(i);
             QueryPerformanceCounter(&lEnd);
             out << "    tIt=";       
             out.width(6);
             out << ((lEnd.QuadPart - lStart.QuadPart) * 1000) / lFreq.QuadPart;

             QueryPerformanceCounter(&lStart);
             out.width(30);
             out << fiboRek2(i);
             QueryPerformanceCounter(&lEnd);
             out << "    tRek2=";       
             out.width(6);
             out << ((lEnd.QuadPart - lStart.QuadPart) * 1000) / lFreq.QuadPart;;
             }
    return 0;
}            


unsigned long long fiboRek2(long int n){
         if (n < 2) return n;
         return fiboRek2(1, 1, n);    
}


unsigned long long fiboRek2(long int a, long int b, long int n){
         if (n < 3) return b;
         return fiboRek2(b,  a + b, n - 1);    
}

Problem nur dabei: Ich kann mit meiner Methode nur auf Millisekunden genau messen - die iterative und die 2. rekursive Methode sind allerdings schneller...
Erst ab etwa Fib(8000) kann ich bei mir einen Effekt auf die iterative Methode feststellen.
Wenn da noch jemand eine Möglichkeit kennt...
Ach und ab Fib(47) hab ich hab ich bei der 2. Rekursionvariante anscheinend einen Bereichsüberlauf - wem da was auffällt...

Ich habe die #05 - L-System Fraktale auch rekusriv programmiert! Ich weiß gar nicht, wie man das als Iteration coden kann!

Wer mal eine Idee hat, kann sich ja bei mir melden!

Gruß,
UEZ