Die Mathe-Redaktion - 23.07.2019 17:46 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 504 Gäste und 13 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matph
Informatik » Programmieren » C: Verstehe Rekursion am Beispiel der Fibonacci-zahlen nicht
Druckversion
Druckversion
Autor
Schule J C: Verstehe Rekursion am Beispiel der Fibonacci-zahlen nicht
Zrebna
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.09.2018
Mitteilungen: 187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-05-31


Hallo!

Zu erst poste ich hier meinen Code zur Darstellung von Fibonacci-Zahlen, den ich mittels iterativem Weg erstellt habe, um mein Problem später, besser klar zu machen:
C
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. unsigned int fibonacci(int x) {
  5. int i, erster_Summand = 0, zweiter_Summand = 1, summe;
  6.  
  7. if (x == 0) {
  8. return 0;
  9. }
  10. if (x == 1) {
  11. return 1;
  12. }
  13.  
  14. for(i = 2; i <= x; i++) {
  15. summe = erster_Summand + zweiter_Summand;
  16. erster_Summand = zweiter_Summand;
  17. zweiter_Summand = summe;
  18. }
  19. return summe;
  20. }
  21.  
  22. int main() {
  23. unsigned int n;
  24. printf("Bitte geben sie ihre gewuenschte Anzahl an Fibonacci-Folgen ein: \n");
  25. scanf("%d", &n);
  26.  
  27. printf("Das Ergebnis von fibonacci(%d) lautet: %d\n", n, fibonacci(n));
  28.  
  29. return 0;
  30. }

Ich habe eine Musterlösung zur rekursiven Lösung vorhanden und diese sieht so aus:
C
  1. #include <stdio.h>
  2.  
  3. long fibonacci(unsigned int index);
  4.  
  5. int main() {
  6. unsigned int n, i;
  7.  
  8. printf("Bitte geben Sie n für fibonacci(n) ein: ");
  9. scanf("%ud", &n);
  10.  
  11. printf("fibonacci(%d) = %ld\n", n, fibonacci(n));
  12.  
  13. return 0;
  14. }
  15.  
  16. long fibonacci(unsigned int n) {
  17. if(n == 0)
  18. return 0L;
  19. if(n == 1)
  20. return 1L;
  21.  
  22. return fibonacci(n-2) + fibonacci(n-1); // rekursive Aufrufe


Nun zu meinem Problem:
Bzgl. meiner iterativen Rechnung weiß ich genau, was rechnerisch geschieht und kann die Rechen-Abfolge mit Stift auf Papier niederschreiben.
Das selbe kann ich für rekursive Lösungen bzgl. einfacheren Beispielen, wie Faklutät.
Hier kann ich zumindest noch eine Rechnung erkennen bei
"return n* fakultät(n - 1)".
Hier kann ich zumindest noch eine Rechnung erkennen, die so oft wiederholt wird, bis die Abbruchbedingung erreicht ist.

Bei dem rekursivem Beispiel der Fibonacci-Aufgabe scheitert es aber direkt daran, dass ich die Abfolge nicht nachvollziehen kann - für mich sähe so aus:
Sagen wir n = 7:

1. run: 5 + 6 // kein return // oder ist es hier 7 + 6?
2. run: 3 + 5 // wird raufgestackt - kein return
3. run: 1 + 4// hier weiss ich schon nicht mehr was geschieht,
                 weil ja das linke Teilargument bereits eine der
                Abbruchedingungen erreicht hat, das andere
                  aber noch nicht.

Mir ist schon klar, dass ich Rekursion noch nicht richtig verstehe, aber die gängigen Beginnerbeispiele/Quellen haben mich soweit leider auch noch nicht wirklich weitergebracht...falls Jemand eine wirklich gute Quelle empfehlen kann, die es gut versteht - immer gerne her damit ^^




  Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 1455
Aus: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-05-31


Hallo,

vielleicht hilft dir dieser Gedanke schon weiter: jeder der beiden Funktionsaufrufe f(n-2) bzw. f(n-1) ruft natürlich selbst jeweils zweimal wieder sich selbst mit den entsprechenden Parametern auf. Im nächsten Schritt sind es theoretisch schon 8 Aufrufe, usw.

Das geht aber jeweils nur so lange, bis ein Wert zurückgeliefert wird. Dieser wird dann sukzessive durch den Stack zurückgereicht und dabei in jeder Stufe passend aufsummiert.

Um bei deinem Beispiel zu bleiben:

Ebene 1:
f(7)=f(5)+f(6)

Ebene 2:
f(5)=f(3)+f(4) , f(6)=f(4)+f(5)

Ebene 3:
f(3)=1+f(2) , f(4)=f(2)+f(3) , f(4)=f(2)+f(3) , f(5)=f(3)+f(4)

Ebene 4:
f(2)=0+1 , f(2)=0+1 , f(3)=1+f(2) , f(2)=0+1 , f(3)=1+f(2) , f(3)=1+f(2) , f(4)=f(2)+f(3)

Ebene 5:
f(2)=0+1 , f(2)=0+1 , f(2)=0+1 , f(3)=1+f(2)

Ebene 6:
f(2)=0+1

Dabei habe ich die Aufrufzweige, die bereits zurückgeliefert sind, jeweils ausgelassen. Ich hoffe, du kannst es dennoch nachvollziehen.


Gruß, Diophant




  Profil  Quote  Link auf diesen Beitrag Link
hgseib
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 04.04.2019
Mitteilungen: 120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-05-31


Hallo

Rekursionen sind gut für 'Selbstähnlichkeit'. Daher eher für Baumstrukturen anzuwenden.

Beispiele (sind immer misst :-) jeder Mensch hat eine Mutter und einen Vater. Diesen Algorithmus kannst du auf dich anwenden. Der selbe Algorithmus kannst du auf deine Eltern anwenden und die auf ihre Eltern usw. Damit kann eine Funktion rekursiv alle Menschen abarbeiten.

Sinngemäss kann man über eine Rekursion z.B. alle Nachkommen einer Person ansprechen. z.B: Je Person:
- führe diese Anweissung für jedes Kind der Person aus
- addiere die Rückmeldungen plus die Anzahl der Kinder
- gebe diese Anzahl zurück
Egal wie umfangreich der Stammbaum auch immer sein mag, mit diesem einfachen Programm lässt sich das bearbeiten.

Für 'keine Baumstruktur' sind Rekursionen übertrieben, da es jedesmal nur einen einzigen Nachfolger geben kann. Das macht man kostengünstiger** mit einer Schleife/ Iteration.

Fakultät und Fibonacci-Folgen werden schulmässig immer wieder als Rekursionen 'vergewaltigt' ;-) Das ist nicht falsch, aber auch nicht wirklich richtig.

Nützt dir das etwas?
mfg


EDIT:
** Der Beitrag von Diophant zeigt sehr schön, das immer mehr Funktionen == Daten gleichzeitig im Speicher gehalten werden müssen. Diese Datenstruktur auf und dann wieder abbauen zu müssen mach eine Rekursion für solche Aufgaben extrem teuer, da man das genausogut auch in einer Schleife abarbeiten kann.

Der Korrektheit wegen will ich aber auch erwähnen, das man Rekursionen (Baumstruktur) über Listen iterativ abarbeiten kann. Das ist dann nicht mehr so elegant wie eine Rekursion, ermöglicht aber eine leichte Verteilung der Rechenzeit und Einspahrung an Speicherplatz.



  Profil  Quote  Link auf diesen Beitrag Link
Zrebna
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.09.2018
Mitteilungen: 187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2019-05-31


@Diophant:
Vielen Dank, dein Post hat mir sehr geholfen und tatsächlich kommt am Ende der Wert 1 rauß, wenn man nun von hinten alles aufsummiert.
Also ich weiß nicht - es funktioniert, aber zumind. für mich millionenmal weniger menschlich intuitiv, als mit einer Iteration.

@hgseib:

Danke auch für deinen Post!

Bei deinem Eltern-Beispiel:
Was wäre hier die Abbruchbedingung?




  Profil  Quote  Link auf diesen Beitrag Link
hgseib
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 04.04.2019
Mitteilungen: 120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-05-31


Hallo

Das mit den Fibonacci-Zahlen finde ich wirklich als ungeeignet. a) lässt sich alles direkt berechnen und b) verstehe ich nicht, was überhaupt zurückgegeben werden soll?
Das jeweils doppelte Aufrufen der Rekursion ist auch kein sinnvolles Beispiel.

// javascript
// a,b, c=Tiefe
function fibo(a,b,c) {
   if (--c) {
      console.log(a,b, '('+c+')');
      var h = a;
      a = b;
      b += h;
      // n.te Fibonaccizahl durchreichen
      return fibo(a,b,c);
   }
   return a;
}
function init() {
   console.log(fibo(0,1,7));
}

Aber bitte, niemals dem Lehrer/ Dozenten wiedersprechen ;-)


2019-05-31 17:07 - Zrebna in Beitrag No. 3 schreibt:
Bei deinem Eltern-Beispiel:
Was wäre hier die Abbruchbedingung?
Was auch immer man ermitteln möchte.

Angenommen man will wissen, wie viele Vorfahren im Raum X geboren wurden und wieviele zugewandert sind. Dann wäre eine Jahreszahl die Abbruchbedingung.
Das ist aber auch egal. Wichtig ist nur 'Baumstruktur' und das jeder Aufruf (hier Eltern) nur sein lokales 'wisssen' benötigt. Und jedes Eltern glaubt, es steht an der Spitze der Berechnung, weil sie nichts voneinander wissen (müssen).

Es ging mir nur darum zu zeigen, das Rekursionen zum durchsuchen von Baumstrukturen geeignet sind. In der Hoffnung, das ein sinnvolles Beispiel eher verstanden werden kann als ein Beispiel, das nicht wirklich sinnvoll ist.

mfg

P.S.
Ein schönes und anschauliches Beispiel für Rekursionen ist z.B: Pfadsuche (Algorithmus u.a. A* (sprich a-stern)).
In einem schachbrettartigem Spielplan sind Felder als Mauer belegt. Eine Figur (ein Feld) kann sich waagrecht und senkrecht um jeweils ein Feld weiter bewegen. Gesucht ist der kürzeste Weg an A nach B.
Das macht man so:
- von A aus werden alle freien Felder gefüllt (als würde sich eine Flüssigkeit ausbreiten)
- Ist B erreicht, dann wird zurück gerechnet.

Betrachte nur das Füllen:
- Von einem Feld aus werden die 4 Nachbarfelder gefüllt (oben, unten, links, rechts)
- das rekursive von jedem aufgerufenen Feld aus.

Abbruchbedingungen:
- der Spielfeldrand, Mauern und Felder die bereits gefüllt sind und natürlich B.





  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2678
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-05-31


Bei der richtigen Betrachtungsweise ist Rekursion intuitiver als Iteration. Dazu muss man sicher allerdings davon lösen, den Prozess als Ganzes überblicken zu wollen. Im Falle der Fibonacci-Zahlen hat man doch schon von vornherein eine rekursive Definition: $a_0 = 0$, $a_1 = 1$, $a_n = a_{n-1}+a_{n-2}$ für $n\geq 2$. Der Code ist eine direkte Übersetzung: Für n=0 oder n=1 gib die jeweiligen Anfangswerte zurück, sonst berechne die vorherige und die vorvorherige Fibonacci-Zahl und gib ihre Summe zurück. Der aus meiner Sicht entscheidende Punkt ist dabei, dass man nicht fragen sollte, wie genau die vorherige und vorvorherige Fibonacci-Zahl berechnet werden -- man nimmt einfach an, dass man für kleinere n bereits eine Lösung berechnen kann.

Für Laufzeitüberlegungen und dergleichen braucht man natürlich trotzdem einen besseren Überblick, und am Ende ist eine rekursive Implementierung einer äquivalenten Implementierung, was Laufzeit- und Speicherverbauch angeht, oft unterlegen. Der Punkt ist, dass man -- wie gesagt, mit der richtigen Sichtweise -- die Lösung schneller findet und es einfacher zu sehen ist, dass diese korrekt ist. Man kann dann das Umformen in eine iterative Lösung als zweiten Schritt, als optionale Optimierung ansehen.

PS: Das gesagte gilt für die rekursive Fibonacci-Berechnung nur eingeschränkt, denn diese hat tatsächlich eine furchtbare Laufzeit und ist sicher nicht geeignet, jemandem Rekursion zu verkaufen.


-----------------
⊗ ⊗ ⊗



  Profil  Quote  Link auf diesen Beitrag Link
Zrebna
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.09.2018
Mitteilungen: 187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-06-01


Danke an beide Antworten und Erläuterungen - ich lass das mal alles sacken und denke mehr darüber nach.



  Profil  Quote  Link auf diesen Beitrag Link
Zrebna hat die Antworten auf ihre/seine Frage gesehen.
Zrebna hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]