Rekursionen, wie verstehen lernen?

Vellas

Hi!

Vielleicht hilft dir das:
http://www.mycsharp.de/wbb2/thread.php?threadid=2044&hilight=Rekursion&hilightuser=7

Code-Hacker

John Doe

Ich versuch mal in Worten.

Du rufst fac(3) auf. 3 != 0, d.h. du lieferst als Ergebnis das Resultat von fac(2) * 3.
Wichtig die Funktion (fac(3)) ist noch nicht zueende.
Du rufst fac(2) auf. 2 != 0, d.h. du lieferst als Ergebnis das Resultat von fac(1) * 2.
Wichtig die Funktion (fac(2)) ist noch nicht zueende.
Du rufst fac(1) auf. 1 != 0, d.h. du lieferst als Ergebnis das Resultat von fac(0) * 1.
Wichtig die Funktion (fac(1)) ist noch nicht zueende.
Du rufst fac(0) auf. 0 == 0, d.h. du lieferst als Ergebnis das Resultat 1.
fac(0) ist beendet.
d.h. fac(1) liefert als Resultat 11.
fac(1) ist beendet.
d.h. fac(2) liefert als Resultat 2*1*1.
fac(2) ist beendet.
d.h. fac(3) liefert als Resultat 3*2*11.
fac(3) ist beendet. ENDE

vielleicht hilfts

mfg JJ

John Doe

Wenn schon Uni-Script dann kann ich mir folgende rekursive Version nicht
verkneifen, da der Algorithmus nur suboptimal bzw. fehlerhaft ist ist.

int fkt(int n)
{
  return (n <= 1) ? 1 : (n * fkt(n-1))
}

die Original-Abbruchbedingung (n == 0) führt bei Eingabe einer negativen Zahl
zu einer Endlosschleife.

mfg

Dann ist deine Funktion aber auch nicht ganz fehlerlos, wenn sie für negative Argumente 1 zurückliefer

John Doe

Besser als ne Endlosschleife.
Ich hab auf die Schnelle nicht die Definition für negative Fakultät
gefunden.

Danke für die schnellen Antworten!

John Doe schrieb:

Ich versuch mal in Worten.

Du rufst fac(3) auf. 3 != 0, d.h. du lieferst als Ergebnis das Resultat von fac(2) * 3.
Wichtig die Funktion (fac(3)) ist noch nicht zueende.
Du rufst fac(2) auf. 2 != 0, d.h. du lieferst als Ergebnis das Resultat von fac(1) * 2.
Wichtig die Funktion (fac(2)) ist noch nicht zueende.
Du rufst fac(1) auf. 1 != 0, d.h. du lieferst als Ergebnis das Resultat von fac(0) * 1.
Wichtig die Funktion (fac(1)) ist noch nicht zueende.
Du rufst fac(0) auf. 0 == 0, d.h. du lieferst als Ergebnis das Resultat 1.
fac(0) ist beendet.
d.h. fac(1) liefert als Resultat 11.
fac(1) ist beendet.
d.h. fac(2) liefert als Resultat 2*1*1.
fac(2) ist beendet.
d.h. fac(3) liefert als Resultat 3*2*11.
fac(3) ist beendet. ENDE

vielleicht hilfts

mfg JJ

Thx, das hat mir ein wenig weitergeholfen, ich dachte immer die Fkt wird nach jedem else Zweig beendet...
Aber das Prob ist wie kommt man selbst auf eine Rekursion?
Die Funktionsweise einer Rek versteh ich einigermaßen, wird irgendwie von "hinten nach vorne" abgearbeitet und wiederum von "vorne nach hinten" ausgegeben.
Oder man kann sich einen Stapel Bücher vorstellen, die von unten nach oben aufgestapelt wird und wieder von oben nach unten abgearbeitet.

Was aber das Prob bei mir ist, ich seh das im Code irgendwie nicht, wieso nach return 1 wieder die funktionen von 1 bis n aufgerufen werden.

John Doe

Na dann hast du aber mächtig Probleme wenn du Quicksort() verstehen sollst.

mfg JJ

Vellas

Hi!

@John Doe:
Es gibt keine negative Fakultät. Würde -1 oder 0 zurückgeben, um so einen Fehler zu signalisieren. Habe dazu mal SirLants-Lösung modifiziert:

int fac (int i)
{
    return (i > 1) ? fac (i-1) : (i<0) ? 0 : 1;
}

Code-Hacker

Taurin

Und warum nicht einfach

unsigned fac(unsigned n)
{
  return fac <= 1 ? 1 : n * fac(n-1);
}

Taurin

Laserstrahl schrieb:

Was aber das Prob bei mir ist, ich seh das im Code irgendwie nicht, wieso nach return 1 wieder die funktionen von 1 bis n aufgerufen werden.

Bei den meisten Rekursionen verwirrt es nur, wenn man versucht, sich alle Aufrufe
vorzustellen. Überlege dir einfach: Was macht ein Aufruf?

Angenommen, du willst die n! berechnen und kennst (n-1)!. Das Ergebnis ist dann
doch offensichtlich n! = n * (n-1)!, es sei denn, n ist 1 oder 0, dann ist
n! = 1. Mehr steht da nicht.

Wenn du das geschluckt hast, kannst du anfnagen, dir über Bücherstapel Gedanken
zu machen: Wir haben nämlich nur angenommen, wir würden (n-1)! kennen. Tun
wir aber gar nicht. Dann müssen wir das eben berechenen. Wir berechnen also
(n-1)!, und weil sich das blöd schreibt, (n-1)! = m!. Und dann stehen wir wieder
Und wenn wir nu m! berechnet haben (in dem wir uns selbst aufgerufen haben; dabei vergessen wir, dass es mal um n! ging und kümmern uns nur um m!),
können wir auch n! berechnen.

Vellas

Hi!

Ja, ist natürlich besser gleich gar keine negativen Zahlen zuzulassen, ansonsten sollte man diesen Fall allerdings abfangen.

Code-Hacker

Mis2com

Guten morgen,

ich versuch Mal ein Beispiel hinzuschreiben.
Wie gesagt:
n! = n*(n-1)!, wobei ! natürlich einen höheren Rang als * hat.

5! wird also zu:

5*4!

und 4! wird zu:

4*3!

also wird 5! zu:

5*4*3!

daraus ergibt sich auf Dauer:

5*4*3*2

MfG Eisflamme

#include <iostream>

using namespace std;

double fac(double n)
{
  return n > 1 ? n*fac(n-1) : true;
}

int main()
{
  cout << fac(6) << endl; // Warum 720  und nicht 1 ?
}

warum wird hier 720 zurückgegeben und nicht 1(true) ?

SirLant

hmm ? schrieb:

#include <iostream>

using namespace std;

double fac(double n)
{
  return n > 1 ? n*fac(n-1) : true;
}
 
 
int main()
{
  cout << fac(6) << endl; // Warum 720  und nicht 1 ?
}

warum wird hier 720 zurückgegeben und nicht 1(true) ?

Weil 6! 720 ist, weshalb sollte da ne 1 ausgeben werden?

Online

double fac(double n)
{
  return n > 1 ? n*fac(n-1) : true;
}

da sieht man wieder wie schön die typentrennung misachtet wird.

übrigens kommt da nur ne 1 raus wenn n nicht größer als 1 ist und das nur deshalb weil true für ne 1 steht in c++ ...so nen code sollte man sich nicht angewöhnen!