rekursive Definition

Neue Frage »

Marduk Auf diesen Beitrag antworten »
rekursive Definition
Guten morgen zusammen!

Mein Studium der Wirtschaftsinformatik beginnt und es tauchen erste Fragen auf smile ). Ich denke also ich werde mich hier öfters blicken lassen!


Um gleich konkret zu werden, es geht um die rekursive Definition der Addition. Sie lautet:

ADD(x,0) = x
ADD(x,y+1) = ADD(x,y)+1


Klar, die erste Zeile ist sozusagen die "Austrittsbedingung", also dann soll die Rekursion beendet werden. Aber die 2. Zeile sagt mir jetzt noch nicht so wirklich was. Wie sehen denn dann die schritte aus, wenn ich z.B. 1+2 rechne?
Ich weiß, dass das noch nicht so schwer sein soll, aber ich hab wohl ne blockade bzw. bin mit rekursion noch nicht so ganz vertraut smile

Ich danke schon mal für jede Antwort
Tobias Auf diesen Beitrag antworten »

Ein Beispiel wirkt Wunder:

ADD(x,0) = x
ADD(x,y+1) = ADD(x,y)+1

Wir nehmen 5+4:

ADD(5, 4) = ADD(5, 3+1) = ADD(5,3)+1
ADD(5,3) = ADD(5, 2+1) = ADD(5,2)+1
ADD(5,2) = ADD(5, 1+1) = ADD(5, 1)+1
ADD(5,1) = ADD(5, 0+1) = ADD(5, 0)+1
ADD(5,0) = 5

Dann rauscht die Rekursion rückwärst, indem alle ADDs ersetzt werden:

ADD(5,4) = ((((5+1)+1)+1)+1) = 9.

Die Zeile ADD(x,y+1) = ADD(x,y)+1 ist äquivalent zu

ADD(x,y) = ADD(x,y-1)+1

wenn du zusätzlich y>0 forderst.
DGU Auf diesen Beitrag antworten »

also entspricht das ADD der nachfolgerfunktion aus den peano axiomen?
Tobias Auf diesen Beitrag antworten »

Formal nicht. Aber anschaulich ja:

Die Summe aus x und y ist der y-te Nachfolger von x.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »