REKURSION +
ITERATION
Bemerkung:
Die in den folgenden Folien
angegebenen "Herleitungen" sind
keine exakten Beweise, sondern
Plausibilitätsbetrachtungen.
Die exakten Beweise wurden dazu
in einem anderen Dokument
gemacht.
Eine Anwendung aus der
Spieltheorie:
Optimale Strategie bei
einem Spiel.
Konkret: Kann man Schach,
Dame, Mühle, usw. so
spielen, daß man "immer"
gewinnt?
Wir untersuchen diese
Frage zuerst an einem
"einfacheren" Spiel
Das Nimm-Spiel
Auf dem Tisch liegt ein Haufen von
anzahl =5 Streichhölzern. Jeder Spieler
muss eine Anzahl zwischen 1 und 3
Streichhölzern vom Tisch nehmen. Wer
nicht mehr ziehen kann (weil kein
Streichholz mehr da ist) hat verloren.
Man kann das Spiel auch
verallgemeinern:
Statt maximal 3 Streichhölzer kann man
maximal k Streichhölzer nehmen.
Möglicher Spielverlauf:
Spieler1 zieht 2 Streichhölzer, also aktuelle
Anzahl = 5-2=3
Spieler2 zieht 1 Streichholz, also aktuelle
Anzahl = 3-1=2
Spieler1 zieht 2 Streichhölzer, also aktuelle
Anzahl = 2-2=0
wer hat verloren ?
Spieler 2 hat verloren
Frage
Wie geht das Spiel aus,
wenn der anziehende und
der nachziehende Spieler
jeweils den "besten Zug"
machen ?
5 Streichhölzer liegen auf einem
Haufen.
Erstellen Sie den dazugehörigen
Spielbaum.
(d.h. zeichnen Sie alle möglichen
Spielverläufe ein).
Hilfestellung:
Siehe angefangenen Spielbaum auf
der nächsten Folie...
5
2
4
3
0 1 0 1
0
2
1
2
3
0 01 0 01 0 1 2
0
0
Wichtig:
2, 3, 4 nennt man die Nachfolger von 5.
0,1 nennt man die Nachfolger von 2, usw.
0 01
0
Gewinnwermittlung:
Wie geht das Spiel aus,
wenn alle 2 Spieler optimal
spielen ?
Wir beginnen bei den
Blättern des Baums und
notieren in jedem Knoten
den Gewinn
(1: Gewinn, -1: Niederlage)
des Spielers, der gerade am
Zug ist:
5
2
3
Dort wo die 0 vorkommt, hat der anziehende
Spieler verloren, also
Gewinn (Auszahlung) = -1
4
0 1 0 1 2 1 2
3
-1
-1
0
0
0
1
0
0
1
0
1
2
-1
-1 -1 -1 -1 -1
0
0
0 01
-1
-1
-1 -1
0
-1
5
2
3
4
0 1 0 1 2 1 2
3
-1
-1
0
0
0
1
0
0
1
0
1
2
-1
-1 -1 -1 -1 -1
0
0
0 01
-1
-1
-1 -1 1
wenn hier verloren wurde, wie groß ist dann
0
die Auszahlung des davor ziehenden Spielers?
-1
5
Da der anziehende Spieler so ziehen kann, daß der
Nachfolgende verliert, ist sein maximaler Gewinn = 1
2
3
4
0 1 0 1 2 1 2
3
-1
-1
0
0
0
1
0
0
1
0
1
2
1
-1
-1 -1 -1 -1 -1
0
0
0 01
-1
-1
-1 -1 1
Was ist hier der optimale Zug für den
0
anziehenden Spieler? Was ist sein max. Gewinn?
-1
5
Da der anziehende Spieler so ziehen kann, daß der
Nachfolgende verliert, ist sein maximaler Gewinn = 1
2
3
4
0 1 0 1 2 1 2
3
-1
-1
0
0
0
1
0
0
1
0
1
2
-1
-1 -1 -1 -1 -1 1 1
0
0
0 01
-1
-1
-1 -1 1
Was ist hier der optimale Zug für den
0
anziehenden Spieler? Was ist sein max. Gewinn?
-1
5
Da der anziehende Spieler so ziehen
kann, daß der Nachfolgende verliert,
ist sein maximaler Gewinn = 1
2
3
4
0 1 0 1 2 1 2
3
-1
-1
0
0
0
1
0
0
1
0
1
-1
-1 -1 -1 -1 1 -1 1
0
0
0
Was ist hier der optimale -1
1
1
Zug für den anziehenden
Spieler? Was ist sein max.
Gewinn?
2
1
01
-1 1
0
-1
5
2
3
Da der anziehende Spieler so ziehen
kann, daß der Nachfolgende verliert,
ist sein maximaler Gewinn = 1
4
0 1 0 1 2 1 2
3
-1
-1
0
0
0
1
0
0
1
0
1
-1
-1 -1 1 -1 -1 1 -1 1
0
0
0
Was ist hier der optimale -1
1
1
Zug für den anziehenden
Spieler? Was ist sein max.
Gewinn?
2
1
01
-1 1
0
-1
5
Da der anziehende Spieler so ziehen kann, daß der
Nachfolgende verliert, ist sein maximaler Gewinn = 1
2
3
4
0 1 0 1 2 1 2
31
-1
-1
0
0
0
1
0
0
1
0
1
-1
-1 -1 1 -1 -1 1 -1 1
0
0
0
-1
-1
-1
Was ist hier der optimale Zug für den anziehenden
Spieler? Was ist sein max. Gewinn?
2
1
01
-1 1
0
-1
5
Da der anziehende Spieler so ziehen kann, daß der
Nachfolgende verliert, ist sein maximaler Gewinn = 1
2
3
4
0 1 0 1 2 1 21
31
-1
-1
0
0
0
1
0
0
1
0
1
-1
-1 -1 1 -1 -1 1 -1 1
0
0
0
-1
-1
-1
Was ist hier der optimale Zug für den anziehenden
Spieler? Was ist sein max. Gewinn?
2
1
01
-1 1
0
-1
5
Da der anziehende Spieler so ziehen kann, daß der
Nachfolgende verliert, ist sein maximaler Gewinn = 1
2
4
3
0 1 0 1 2
-1
-1
0
0
0
1
-1
-1 -1 1
0
-1
11
21
0 01 0
-1 -1 1 -1
0
-1
Was ist hier der optimale Zug für den anziehenden
Spieler? Was ist sein max. Gewinn?
31
1
2
1 1
0 01
-1 -1 1
0
-1
5
Da der anziehende Spieler so ziehen kann, daß der
Nachfolgende verliert, ist sein maximaler Gewinn = 1
2
4
3
0 1 0 1 21
-1
-1
0
0
0
1
-1
-1 -1 1
0
-1
11
21
0 01 0
-1 -1 1 -1
0
-1
Was ist hier der optimale Zug für den anziehenden
Spieler? Was ist sein max. Gewinn?
31
1
2
1 1
0 01
-1 -1 1
0
-1
5
Da der anziehende Spieler so ziehen kann, daß der
Nachfolgende verliert, ist sein maximaler Gewinn = 1
2
4
3
0 1 0 11 21
-1
-1
0
0
0
1
-1
-1 -1 1
0
-1
11
21
0 01 0
-1 -1 1 -1
0
-1
Was ist hier der optimale Zug für den anziehenden
Spieler? Was ist sein max. Gewinn?
31
1
2
1 1
0 01
-1 -1 1
0
-1
5
Da der anziehende Spieler so ziehen kann, daß der
Nachfolgende verliert, ist sein maximaler Gewinn = 1
2
4
3
0 1 0 11 21
-1 1 -1
0
0
0
1
-1
-1 -1 1
0
-1
11
21
0 01 0
-1 -1 1 -1
0
-1
Was ist hier der optimale Zug für den anziehenden
Spieler? Was ist sein max. Gewinn?
31
1
2
1 1
0 01
-1 -1 1
0
-1
5
Der nachfolgende Spieler gewinnt immer. Der maximale Gewinn des
anziehenden Spielers ist also -1
2
4
3
0 1 0 11 21
-1 1 -1
0
0
0
1
-1
-1 -1 1
0
-1
-1
11
21
0 01 0
-1 -1 1 -1
0
-1
Was ist hier der optimale Zug für den anziehenden
Spieler? Was ist sein max. Gewinn?
31
1
2
1 1
0 01
-1 -1 1
0
-1
5
Da der anziehende Spieler so ziehen kann, daß der Nachfolgende
verliert, ist sein maximaler Gewinn = 1
2
4
3
-1
1
0 1 0 11 21
-1 1 -1
0
0
0
1
-1
-1 -1 1
0
-1
11
21
0 01 0
-1 -1 1 -1
0
-1
Was ist hier der optimale Zug für den anziehenden
Spieler? Was ist sein max. Gewinn?
31
1
2
1 1
0 01
-1 -1 1
0
-1
5
Da der anziehende Spieler so ziehen kann, daß der Nachfolgende
verliert, ist sein maximaler Gewinn = 1
2
1
4
3
-1
1
0 1 0 11 21
-1 1 -1
0
0
0
1
-1
-1 -1 1
0
-1
11
21
0 01 0
-1 -1 1 -1
0
-1
Was ist hier der optimale Zug für den anziehenden
Spieler? Was ist sein max. Gewinn?
31
1
2
1 1
0 01
-1 -1 1
0
-1
51
2
1
3
1
4
-1
0 1 0 11 21 11 21
31
-1 1 -1
0
0
0
1
0
0
1
0
1
-1
-1 -1 1 -1 -1 1 -1 1
Da der anziehende Spieler so ziehen
kann, daß der Nachfolgende 0
verliert,
0
0
ist sein maximaler Gewinn
-1= 1
-1
-1
Was ist hier der optimale Zug für den anziehenden
Spieler? Was ist sein max. Gewinn?
2
1
01
-1 1
0
-1
Angenommen, man würde die
maximale Auszahlung (Gewinn,
payout) p1max, p2max, p3max
aller möglichen Spielzüge
(Nachfolgeknoten) des Gegners
kennen.
Wie berechnet man daraus die
maximale Auszahlung pmax des
Vorgängerknotens?
Der anziehende Spieler zieht so,
dass der nachfolgende Spieler eine
minimale Auszahlung bekommt.
Da dies ein Nullsummenspiel ist,
ist die maximale Spielauszahlung
des anziehenden Spielers, das
negative Minimum der
Auszahlungen aller nachfolgenden
Spieler.
Als Formel:
pmax = - Minimum(p1max, p2max, p3max)
abgekürzt:
pmax = g (p1max, p2max, p3max)
Man kann dieses Prinzip
der Rekursion (für die
entsprechenden Beispiele)
ganz allgemein durch einen
Baum darstellen:
ein Spielstand (hier Anzahl der Streichhölzer), dessen
maximaler Gewinn w = N(a) berechnet werden soll
a,N(a)
Dazu zerlegt man ihn in seine Bestandteile
(nachfolgende Spielstände a1, a2, a3), d.h. bildet
die Nachfolger im Baum
gilt für a ≥ 3
a-1,N(a-1) a-2,N(a-2)
a-2,N(a-3)
... und tut dann so, als ob die maximalen Gewinne w1=N(a-1),
w2=N(a-2) und w3=N(a-3) der Nachfolger a-1, a-2, a-3 bekannt
wären.
Wie kann man dann den maximalen Gewinn w = N(a) durch die
maximalen Gewinne N(a-1), N(a-2) und N(a-3) berechnen?
N(a) = - Minimum(N(a-1), N(a-2), N(a-3))
(a,N(a))
Das 2. Element im Tupel ist der Nachbar des 1.
Elements, also der Nachbar von a. Er wird hier
deshalb mit N (wie Nachbar) bezeichnet.
(a-1,N(a-1)) ( a-2,N(a-2)) ( a-2,N(a-3) )
N(a) = - Minimum(N(a-1), N(a-2), N(a-3))
Rekursion: N kommt links und rechts des
Gleichheitszeichens vor!
Des Weiteren: Hier handelt es sich nicht um einzelne Werte,
sondern um 2er-Pakete (Zweier-Tupel), die man mathematisch wie
folgt darstellt ...
Berechnung des maximalen
Gewinns (Auszahlung) bei
einem Haufen von a
Streichhölzern durch eine
Regelmenge
Erzeugung der Regeln:
Regelmenge, mit denen
man die Haufen (Anzahl
der Streichhölzer)
einschließlich ihrer
maximalen Gewinne
induktiv definieren kann.

-----(0,-1)

-----(1,1)

-----(2,1)
Regel 1, kurz R1 (Atom)
wenn 0 Streichhölzer da sind, hat der
anziehende Spieler verloren
Regel 2, kurz R2 (Atom)
Bei einem Haufen mit 1 Streichholz nimmt der
anziehende Spieler 1 Streichholz weg, dann hat er
gewonnen (unabhängig vom Zug des
nachfolgenden Spielers).
Regel 3, kurz R3 (Atom)
Bei einem Haufen mit 2 Streichhölzern nimmt der
anziehende Spieler 2 Streichhölzer weg, dann hat
er gewonnen (unabhängig vom Zug des
nachfolgenden Spielers).
4, kurz R4
{(a-1,w1), (a-2,w2), (a-3,w3)} Regel
wobei a ≥ 3
-------------------------------------(a, -min(w1,w2,w3))
abgekürzt:
{(a-1,w1), (a-2,w2), (a-3,w3)}
-------------------------------------(a, g(w1,w2,w3))
Aufgabe:
Geben Sie die Mengen
D0, D1, D2 an.
D0 = 
D1 =
{ (0,-1) ; (1,1) ; (2,1) }
Jetzt zur Berechnung von D2:
{(a-1,w1), (a-2,w2), (a-3,w3)}
-------------------------------------(a, g(w1,w2,w3))
angewendet auf:
was gibt g(-1.1.1), also
-min(-1,1,1) = 1
{(0 , -1), (1 , 1 ), (2 , 1 )}
----------------------------------(3 , g(-1, 1 , 1 ))
{(a1,w1), (a2,w2), (a3,w3)}
----------------------------------(a, g(w1,w2,w3))
angewendet auf:
{(0 , -1), (1 , 1 ), (2 , 1 )}
----------------------------------(3 , 1)
D2 =
{ (0,-1) ; (1,1) ; (2,1) ;
(3,1) }
Jetzt zur Berechnung von D3:
{(a-1,w1), (a-2,w2), (a-3,w3)}
--------------------------------------(a, g(w1,w2,w3))
angewendet auf:
was gibt g(1,1,1), also
-min(1,1,1) = -1
{(1 , 1 ), (2 , 1 ), (3 , 1 )}
----------------------------(4 , g(1 , 1 , 1 ))
{(a-1,w1), (a-2,w2), (a-3,w3)}
--------------------------------------(a, g(w1,w2,w3))
angewendet auf:
{(1 , 1 ), (2 , 1 ), (3 , 1 )}
----------------------------(4 , -1 )
D3 =
{ (0,-1) ; (1,1) ; (2,1) ;
(3,1) ; (4,-1) }
Wie früher gilt:
D = D0  D1  D2  D3  ...
Also:
Wie kann N(a) rekursiv
berechnet werden …?
Wie berechnet man N(z), wobei z
die 1. Komponente eines Atoms
(Tupel) ist ? Also z.B.
N(0) = -1 weil (0,-1) ein Atom ist
N(1) = 1 weil (1,1) ein Atom ist
N(2) = 1 weil (2,1) ein Atom ist
Wie kann dann N(a)
berechnet werden, wenn a
nicht 1. Komponente eines
Atoms ist, also a ≥ 3 ist?
Wie vorher kann man wieder die
Kandidatenmenge angeben, d.h.
die Menge der Kandidaten, die z.B.
die eine Menge von 8
Streichhölzern produziert haben
könnten.
K(8) = {(5,6,7)}
Angenommen, man will
N(8)
berechnen und man wüsste den
maximalen Gewinn bei der Anzahl
von 5, 6 und 7 Streichhölzern, also
die Werte N(5) , N(6) und N(7)
wären bekannt.
Wie wird dann
N(8) berechnet?
Indem man das negative Minimum
von N(5) , N(6) und N(7)
berechnet, also:
N(8) = - min(N(5) , N(6) , N(7))
Aufgabe:
Erstellen Sie die Funktion
N(int anz), die im Nimm-Spiel
den maximalen Gewinn des
anziehenden Spielers
berechnet.
#include "stdafx.h"
int negMin(int z1, int z2, int z3);
int N(int anz);
int main(){
int erg;
int i;
for(i=0;i<20; i++){
erg = N(i);
printf("i= %d erg =%d \n", i, erg);
}
return 0;
}
int negMin(int z1, int z2, int z3){
int min;
if(z1<z2)
min=z1;
else
min=z2;
if(z3<min)
min=z3;
return -min;
}
int N(int anz){
int maxGewinn;
if (anz==0)
maxGewinn = -1;
else if(anz==1)
maxGewinn = 1;
else if(anz==2)
maxGewinn = 1;
else
maxGewinn=
negMin(N(anz-3),N(anz-2),N(anz-1));
return maxGewinn;
}
Weiteres Beispiel für eine
Rekursion bzw.
Regelmenge
Berechnung des Werts
einer Zeichenkette bzw.
Terms
Alle folgenden Zeichenketten sollen
aus dem Alphabet
A=
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ) , ( , + , - }
bestehen.
D.h. eine beliebige Zeichenkette darf
nur aus diesen Zeichen bestehen.
Die Menge aller Terme, die aus dem
Alphabet A hergestellt werden,
bezeichnen wir mit X.
Unter einem mathematischen
Term verstehen wir hier einen
aus den Rechenzeichen + bzw.
-und den Ziffern bzw. den
Klammern zusammengesetzten
Ausdruck. Also:
1) Die Zeichen von 0 bis 9
2) Zeichenketten der Form:
(9+2), ((3-2)+3),
((5+7)+((4+(6-6))), usw.
Welche Werte haben die
folgenden Zeichenketten
bzw. Terme?
Diese Zeichenkette ist kein Term.
3+-7
45
(8-9
7
(9-2)
((3-2)+3)
((5+7)+((4+(6+6)))
Zahlen sind keine Terme (außer
Ziffern).
Dies ist kein Term.
7 ist eine Ziffer, also ein Term und soll den Wert 7 haben
Dies ist ein Term und hat den Wert 7
Dies ist ein Term und hat den Wert 4
Term mit Wert 28
Bemerkung:
Eigentlich müsste man z.B. zwischen
dem Term 7 und dem Wert 7 dieses
Terms unterscheiden (unterschiedliche
Bezeichnungen), also
Term: "7" (also eine Zeichenkette)
Wert: 7 (also eine Zahl)
Dies wird hier aus Gründen der
Vereinfachung nicht gemacht.
Erzeugung der Regeln:
(Regelmenge), mit denen
man Terme einschließlich
ihrer Werte induktiv
definieren kann.
Dies unterscheidet sich
etwas in der Notation zu
früher.
Warum ?
Früher bestand ein Element
nur aus z.B. einem Term.
Jetzt ist es ein Term und ein
Wert. Dies wird durch einen
Zweier-Tupel (kurz: Tupel)
dargestellt.
Hat eine Zeichenkette keinen Wert,
also keine Zahl (weil sie kein Term
ist), wird dieser Wert mit # dargestellt.
Ein Tupel beginnt mit der Klammer (
und endet mit der Klammer )
Die Klammern, die bei der
Termerzeugung - wie z.B. (3+5) benötigt werden, werden im
Gegensatz dazu mit schwarzer Farbe
dargestellt.
Für welche Werte stehen die
Fragezeichen ?
(3+7, ?)
(4-5, ?)
((3-9, ?)
(2, ?)
((9+2), ?)
(((3+2)-3), ?)
(((5+7)+(4+(6+6))), ?)
Zeichenkette (kein Term) mit Wert #
(3+7, #)
(4-5, #)
((3-9,#)
(2,2)
((9+2),11)
(((3+2)-3), 2)
(((5+7)+(4+(6+6))), 28)
Zeichenkette (kein Term) mit Wert #
Zeichenkette (kein Term) mit Wert #
Term 2 mit Wert 2
Term (9+2) mit Wert 11
Term ((3+2)-3) mit Wert 2
Term ... mit Wert 28
Aufgabe:
Geben Sie die Regeln
(Regelmenge) an, mit denen
man Terme induktiv
definieren, d.h. exakt
formalisieren kann.

-----(0,0)
...

-----(9,9)

-------(z, #)
Regel 1, kurz R1
Regel 10, kurz R10
R1 bis R11 sind die Regelaxiome.
Regel 11, kurz R11
wobei z X und z ist kein Term.
Der Wert # bedeutet, daß z kein
Term ist.
Regel 12, kurz R12
wobei T1 ein Term aus X und T2
auch ein Term aus X ist und w1
und w2 ganze Zahlen sind.
{(T1,w1);(T2,w2)}
----------------------------((T1+T2), add(w1,w2))
add(w1,w2) bedeutet die Summe von w1 und w2.
Warum schreibt man dann nicht einfach w1+w2 ?
Weil das + schon für die
Termbildung verwendet wird
und dort einfach nur ein
Zeichen bedeutet.
Ganz wichtig:
T1 und T2 sind Terme !!
Regel 13, kurz R13
wobei T1 ein Term aus X und T2
auch ein Term aus X ist und w1
und w2 ganze Zahlen sind.
{(T1,w1);(T2,w2)}
----------------------------((T1-T2), sub(w1,w2))
sub(w1,w2) bedeutet die Differenz von w1 und
w2. Warum schreibt man dann nicht einfach
w1-w2 ?
Weil das - schon für die
Termbildung verwendet wird
und dort einfach nur ein
Zeichen bedeutet.
Ganz wichtig:
T1 und T2 sind Terme !!
Aufgabe:
Geben Sie die Mengen
D0, D1, D2 an.
D0 = 
D1 =
{ (0,0);...;(9,9) } 
{(z,#) | zX  z ist kein Term}
D2 =
{ (0,0) ; ... ; (9,9) ; ((0+0),0) ; ((0+1),1) ;
((0+9),9) ; ...; ((9+9),18)} 
{ (0,0) ; ... ; (9,9) ; ((0-0),0) ; ((0-1),-1) ;
((0-9),-9) ; ...; ((9-9),0)} 
{(z,#) | zX  z ist kein Term}
oder in beschreibender
Mengenschreibweise:
D2 =
{ (1,1) ; ... ; (9,9) } 
{((d1+d2),add(d1,d2)) | d1Z und d2Z} 
{ (1,1) ; ... ; (9,9) } 
{((d1-d2),sub(d1,d2)) | d1Z und d2Z}
 {(z,#) | zX  z ist kein Term}
wobei Z = {0,1, ... , 9}
Wie früher gilt:
D = D0  D1  D2  D3  ...
Uns interessiert nun die 2. Der Nachbar von 7
Komponente eines Tupels, also den
Wert, d.h. den Nachbar eines Terms,
Der Nachbar von (9+2)
also z.B:
(7,7) man schreibt:
Der Nachbar von ((3+2)+3)
N(7) = 7
((9+2),11) man schreibt:
N( (9+2) ) = 11
(((3+2)+3),8) man schreibt:
N( ((3+2)+3) ) = 8
Wie kann N(z) rekursiv
berechnet werden …?
Wie vorher kann man wieder die
Kandidatenmenge angeben, d.h.
die Menge der Kandidaten, die z.B.
die Zeichenkette ((1+2)+(3+4))
produziert haben könnten.
K(((1+2)+(3+4))) = {(1+2) , (3+4)}
Beachte: Regel R12 verlangt, daß die
zerlegten Zeichenketten Terme sein
müssen.
Angenommen, man will
N(((1+2)+(3+4)))
berechnen und man wüsste den
Wert von (1+2) und von (3+4),
also die Werte N((1+2)) und
N((3+4)) wären bekannt.
Wie wird dann
N(((1+2)+(3+4)))
berechnet?
wobei dieses + das mathematische
Zeichen für die Addition ist
Indem man die Werte N((1+2)) und
N((3+4)) addiert, also:
N(((1+2)+(3+4))) =
add(N((1+2)), N((3+4)))
Wie berechnet man N(z), wobei z
die 1. Komponente eines Atoms
(Tupel) ist, wie z.B. N(6) ?
Indem man einfach die 2.
Komponente des Atoms nimmt!
Beispiele:
N(6) = 6
N(3++)+a) = #
weil (6,6)D1
weil (3++)+a,#)D1
Insgesamt ergibt dies die
folgende mathematische
Formel:
// Kandidatenmenge leer:
Fall: K(x) =  ==>
N(z) = #, falls z kein Term
N(z) = z, falls z eine Ziffer
// x kommt direkt nach dem Urknall:
Fall: K(T) ={(T1,T2)}   ==>
N(T) = gi(N(T1),N(T2))
wobei gi eine Funktion ist (wie z.B.
add oder sub), die von T abhängt.
Weniger mathematisch kann
man dieses Prinzip der
Rekursion (für die
entsprechenden Beispiele)
auch durch einen Baum
darstellen.
ein Term, dessen Wert w = N(T) berechnet werden soll
T,N(T2)
Dazu zerlegt man ihn in seine Bestandteile (Terme
T1 und T2 ), d.h. bildet die Nachfolger im Baum
Frage: Welcher Zusammenhang besteht
dann zwischen T, T1 und T2?
T1,N(T1)
T2 ,N(T2)
T = (T1+T2) oder T = (T1-T2)
... und tut dann so, als ob die Werte w1=N(T1) und w2=N(T2) der
Nachfolger T1 und T2 bekannt wären.
Wie kann man dann den Wert w = N(T) durch den Wert N(T1) von
T1 und den Wert N(T2) berechnen?
in Abhängigkeit der Zerlegung (T1+T2) oder (T1-T2) gilt dann:
N(T) = add(N(T1),N(T2)) oder N(T) = sub(N(T1),N(T2))
Beispiel
((5+(6-7))+8)
12
N( ((5+(6-7))+8) ) = add(N((5+(6-7))),N(8)) = 12
(5+(6-7)) , 8
4
N((5+(6-7))) = add(N(5),N((6-7))) == 4
8
N(8) = 8
5 , (6-7)
5
-1
N(5) = 5
N((6-7)) = sub(N(6),N(7)) = -1
6 , 7
6
N(6) = 6
7
N(7) = 7
Wie groß ist jeweils N(…), d.h. welchen Wert haben die roten Blätter ?
Also:
Wie kann N(z) rekursiv
berechnet werden …?
Zuerst braucht man eine Funktion,
die feststellt, ob eine Zeichenkette
ein Term ist. Das ist die von früher
bekannte Funktion eRek(..).
Zusätzlich soll diese Fuktion noch
(falls die Zeichenkette ein Term
ist) die 2 Teilterme zurückliefern,
in die der Terme zerlegt wurde.

17-3_Rekursion