Frage von Alinchen24, 67

rekursion programmieren in c?

Gegeben ist folgendes Programmfragment:

float mystery_function(int *a, int b)

{

if (b <= 0)

return a[0];

else

return (a[b] + b * mystery_function(a, b-1)) / (b+1);

}

Die Funktion wird wie folgt aufgerufen:

int a[] = {3,6,4,12,5};

int laenge = 5;

ergebnis = mystery_function(a, laenge - 1);

Nun meine Frage : Wieso wird 6 zurückgegeben ? ^^

Antwort
von Mikkey, 39

Du kannst den Ablauf und damit die Funktion des Programmfragments im Debugger untersuchen. Dann kannst Du auch Deine Frage beantworten.

Antwort
von triopasi, 32

Nimm n Zettel und rechne Schritt für Schritt nach, da lernst du viel mehr als mit dem Debugger. Kannst zB ne Tabelle machen, in der du die Variablen nach jedem Rekursionsaufruf einträgst.

Antwort
von GedankenGruetze, 24

Nimm einen Bleistift und schreib dir einfach mal die unterste Zeile auf

1. 5 + 4 * mystery_function(a, 3)) / 5

2. 12 + 3....

3.

4.

Das Ganze machst du so lange, bis die Bedingung b <= 0 erfüllt ist und gehst dann die Zeilen wieder nach oben, nur das du für die myster_function dann den jeweiligen Wert einsetzt, bis du dann bei der oberen Zeile angekommen bist und dann eine Gleichung wie

1. 5 + 4*1/5 rausbekommst....

Antwort
von Roach5, 14

Geh es doch einmal durch, mit etwas Intuition und Gehirnschmalz solltest du rausbekommen, dass das Programm immer den Durchschnitt aller Arrayeinträge berechnet. Also (a[0] + a[1] + ... + a[n-1])/n.

Wenn der Array nur einen Eintrag hat, dann wird offensichtlich der Durchschnitt ausgegeben, da Eintrag/1 ausgegeben wird.

Wenn n+1 Einträge gegeben sind, dann wird n * mysteryfunction(a, n-1) zurückgerufen und damit weitergerechnet, das ist nach Induktionsvoraussetzung einfach nur a[0] + ... + a[n-1], also kommt am Ende raus: (a[0] + ... + a[n])/(n+1), also genau was wir haben wollten.

Wenn du deinen Beispielarray nimmst, dann rechnest du den Durchschnitt per Hand aus, also (3 + 6 + 4 + 12 + 5)/5 = 30/5 = 6.

LG

Keine passende Antwort gefunden?

Fragen Sie die Community