-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRecursion.html
More file actions
884 lines (868 loc) · 53.6 KB
/
Recursion.html
File metadata and controls
884 lines (868 loc) · 53.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
<!DOCTYPE html><html lang="de"><head>
<title>Variationen zum Thema: Algorithmen</title>
<meta name="title" content="Variationen zum Thema: Algorithmen">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta charset="UTF-8">
<meta name="description" content="Eine Einführung anhand von Beispielen">
<meta name="keywords" content="Java,Algorithmen,Datenstrukturen">
<meta name="author" content="Ralph P. Lano">
<meta name="robots" content="index,follow">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="stylesheet" type="text/css" href="book.css">
</head>
<body><center>
<div id="wrap">
<ul class="sidenav">
<p><a href="index.html">Variationen zum Thema</a><a href="index.html">Algorithmen</a></p>
<li><a href="Introduction.html">Introduction</a></li>
<li><a href="Lists.html">Lists</a></li>
<li><a href="Maps.html">Maps</a></li>
<li><a href="Recursion.html" class="active">Recursion</a></li>
<li><a href="Algorithms.html">Algorithms</a></li>
<li><a href="Sorting.html">Sorting</a></li>
<li><a href="Trees.html">Trees</a></li>
<li><a href="Graphs.html">Graphs</a></li>
<li><a href="Text.html">Text</a></li>
<li><a href="Techniques.html">Techniques</a></li>
</ul>
<div class="content"><p>
<img src="images/RecursiveKarel2.png" style="display: block; margin-left: auto; margin-right: auto; width: 171px; height: 197px;" /></p>
<h1>
Recursion</h1>
<p>
Das Wort <em>Rekusion</em> kommt von dem lateinischen "recurrere" was "zurückkehren" bedeutet. Für uns heißt es soviel wie laufen wir mal los bis wir auf etwas stoßen, das wir schon kennen, und dann <em>kehren wir zurück</em> zu dem was wir vorher machen sollten. Rekursion ist eine weit verbreitete Technik zur Lösung aller möglichen Probleme. Im Vergleich zur <em>Iteration</em>, ist sie zwar häufig etwas langsamer, aber in der Regel viel eleganter. Fast alle Probleme lassen sich sowohl durch Iteration als auch durch Rekusion lösen.</p>
<p>
.</p>
<h2>
<img alt="" src="images/Palindrome.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />Palindrome</h2>
<p>
Ein sehr schönes Beispiel für Rekursion sind <em>Palindrome</em> [1]: also Worte oder Sätze die das Gleiche bedeuten, egal ob man sie von links nach rechts oder rechts nach links liest:</p>
<ul>
<li>
rentner</li>
<li>
lagerregal</li>
<li>
racecar</li>
<li>
was it a car or a cat i saw</li>
<li>
Saippuakippokukkakivikakkukoppikauppias (Finisch für "Soap-bowl-flower-stone-cake-box seller") [2]</li>
</ul>
<p>
Man kann ein Palindrom folgendermaßen definieren:</p>
<ol>
<li>
ein Wort das null oder einen Buchstaben lang ist, ist immer ein Palindrom;</li>
<li>
ein Wort ist dann ein Palindrom, wenn der erste und letzte Buchstabe gleich sind, und wenn das Wort ohne die beiden auch ein Palindrom ist.</li>
</ol>
<p>
Das ist das typische Muster für Rekursion: wir haben immer einen <em>recursive case</em>, hier Schritt 2, in dem wir das Problem durch eine einfachere Version von sich selbst ausdrücken, und einen <em>base case</em>, hier Schritt 1, der dafür sorgt, dass die Rekursion irgendwann aufhört, deswegen nennt man es auch die Abbruchbedingung. Denn die häufigste Bug bei rekursiven Programmen ist, dass sie nie aufhören, so wie beim Infinite Loop aus dem letzten Semester.</p>
<p>
Natürlich wollen wir das gleich in Java umsetzen: wir wollen eine Methode namens <em>isPalindrome(String s)</em> schreiben, die feststellt ob ein gegebener String ein Palindrom ist:</p>
<pre style="margin-left: 40px;">
private boolean <span style="color:#0000ff;">isPalindrome</span>(String s) {
if (s.length() <= 1) { // base case
return true;
} else { // recursive case
if (s.charAt(0) == s.charAt(s.length() - 1)) {
return <span style="color:#0000ff;">isPalindrome</span>(s.substring(1, s.length() - 1));
} else {
return false;
}
}
}</pre>
<p>
Übrigens gibt es Palindrome auch in der Musik, und interessanterweise auch in unserer DNA: anscheinend speichert unserer Immunsystem die RNA von Viren sowohl vorwärts als auch rückwärts um böse Viren zu erkennen.</p>
<p>
.</p>
<h2>
<img alt="" src="images/Factorial.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />Factorial</h2>
<p>
Kommen wir zu einem anderen Klassiker der sich sehr schön mittels Rekursion lösen lässt, die Fakultät einer Zahl. In der Schule haben wir gelernt, dass man die Fakultät von vier wie folgt berechnet:</p>
<pre style="margin-left: 40px;">
4! = 4 * 3 * 2 * 1</pre>
<p>
Wenn wir das als Programm schreiben wollen, dann bietet sich eine Schleife an:</p>
<pre style="margin-left: 40px;">
int fac = 1;
for (int i=1; i<=4) {
fac = fac * i;
}
</pre>
<p>
Das ist die iterative Art und Weise die Fakultät einer Zahl zu berechnen. Es gibt aber noch eine andere, die rekursive. Dazu beobachten wir, dass: </p>
<pre style="margin-left: 40px;">
<span style="color:#0000ff;">4!</span> = 4 * 3 * 2 * 1 = 4 * <span style="color:#0000ff;">3!</span></pre>
<p>
Wir können also 4! durch vier mal 3! ausdrücken. Im Allgemeinen gilt sogar</p>
<pre style="margin-left: 40px;">
n! = n * (n-1)!</pre>
<p>
Immer wenn wir eine derartige Beziehung finden, also dass eine Funktion in <em>f(n)</em> durch eine Funktion in <em>f(n-1)</em> ausgedrückt werden kann, dann haben wir eine rekursive Lösung für unser Problem.</p>
<p>
Setzen wir das gleich mal in Code um:</p>
<pre style="margin-left: 40px;">
int <span style="color:#0000ff;">factorial</span>(int n) {
return n * <span style="color:#0000ff;">factorial</span>( n-1 );
}
</pre>
<p>
Wir haben also eine Methode die sich selbst aufruft: das ist Rekursion.</p>
<p>
Unser Code hat allerdings ein kleines Problem: er hört nicht auf zu laufen, weil wir die Abbruchbedingung, den <em>base case</em>, vergessen haben. Bei der Fakultät ist das die Tatsache, dass per definitionem</p>
<pre style="margin-left: 40px;">
0! = 1</pre>
<p>
Damit sieht unser Java dann wie folgt aus:</p>
<pre style="margin-left: 40px;">
int factorial(int n) {
if ( n == 0 )
return 1;
else
return n * factorial( n-1 );
}
</pre>
<p>
Wir sehen also man kann die Fakultät einer Zahl sowohl durch Iteration als auch durch Rekursion berechnen.</p>
<p>
.</p>
<h2>
<img alt="" src="images/7f5aa121-0f79-43b2-b788-73a707690b1e.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 128px; float: right;" />Tower of Hanoi</h2>
<p>
Das Rekursion nicht nur mit Wörtern oder Zahlen zu tun hat, sondern sehr häufig hübsche grafische Anwendungen hat, soll das Beispiel <em>Tower of Hanoi</em> zeigen [3]. Im Kindergarten hat eigentlich schon mal fast jeder mit dem Spiel <em>Türme von Hanoi</em> zu tun gehabt. Dabei geht es darum einen Stapel Scheiben, meist aus Holz, von dem Stab auf er linken Seite auf den Stab auf der rechten Seite zu verschieben. Dabei gilt es allerdings folgende Regeln zu beachten:</p>
<ol>
<li>
man kann immer nur eine Scheibe verschieben;</li>
<li>
es kann immer nur die oberste Scheibe eines Stapels verschoben werden;</li>
<li>
es darf nie ein größere Scheibe auf einer kleineren zu liegen kommen.</li>
</ol>
<p>
Man denkt, das kann doch gar nicht so schwer sein, aber beim ersten Mal ist es gar nicht so einfach. </p>
<p>
Interessant für uns ist, dass es eine überraschend elegante rekursive Lösung für das Problem gibt: Angenommen, wir haben einen Stapel mit sieben Scheiben. Und nehmen wir an wir wüssten wie man einen Stapel mit sechs Scheiben verschieben kann. Dann ist die Lösung für unser Problem ganz einfach: Schiebe zunächst die sechs Scheiben auf den mittleren Stab. Dann nimm die übriggebliebene siebte Scheibe (die weiße) und verschiebe sie auf den rechten Stab. Und jetzt verschieben wir den Stapel mit den sechs Scheiben auf den rechten Stab. Das Problem mit sieben Scheiben ist gelöst. Wir können also das 7 Scheiben Problem lösen, wenn wir das 6 Scheiben Problem lösen können. Und das ist eine rekursive Lösung. Bleibt die Frage nach dem Abbruchkriterium: das ist ganz einfach: einen Stapel mit einer Scheibe können wir immer bewegen.</p>
<p>
<img alt="" src="images/TowerOfHanoiGraphic.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />Also sieht unser Algorithmus wie folgt aus:</p>
<pre style="margin-left: 40px;">
private void <span style="color:#0000ff;">moveTower</span>(int n, int source, int destination, int temp) {
if (n > 0) {
<span style="color:#0000ff;">moveTower</span>(n - 1, source, temp, destination);
moveOneDisk(source, temp);
<span style="color:#0000ff;">moveTower</span>(n - 1, destination, source, temp);
}
}
</pre>
<p>
Und das kann man auch sehr hübsch animieren.</p>
<p>
Eine kleine Anmerkung zum <em>Tower of Hanoi</em> Problem: schon für relativ wenige Scheiben, dauert es sehr lange die Scheiben zu verschieben. Z.B., wenn man annimmt, das es eine Sekunde dauert eine Scheibe zu verschieben, dann dauert es 12 Tage um einen Stapel mit nur 20 Scheiben zu verschieben. Und für einen Stapel mi 60 Scheiben würde man mehr Zeit benötigen als unser Universum alt ist [3]!</p>
<p>
.</p>
<hr />
<h1>
Review</h1>
<p>
Mittels Rekursion lassen sich sehr viele Probleme elegant lösen. Sehr vielen Algorithmen denen wir begegnen werden bedienen sich daher eines rekursiven Ansatzes. Der folgt immer den folgenden zwei Schritten:</p>
<ol>
<li>
ein Problem kann durch eine einfachere Version von sich selbst ausgedrückt werden;</li>
<li>
es gibt ein Abbruchkriterium, also irgend einen einfachen Fall von dem man die Antwort kennt.</li>
</ol>
<p>
Sehr, sehr viele Problem lassen sich durch Rekursion lösen.</p>
<p>
.</p>
<hr />
<h1>
Projekte</h1>
<p>
Man mag sich vielleicht die Frage stellen, muss ich mir die Rekursion wirklich antun? Nach den folgenden Beispielen kann jeder die Frage für sich selbst beantworten. Für mich ist die Antwort aber ziemlich eindeutig: Rekursion ist cool.</p>
<p>
.</p>
<h2>
<img alt="" src="images/RecursiveKarel.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 200px; float: right;" />RecursiveKarel</h2>
<p>
In dem Projekt geht es darum Rekursion zu visualisieren. Dazu nehmen wir ein Bild von Karel, welches wir schrittweise immer kleiner machen, und die einzelnen Bilder ineinander zeichnen. Wir beginnen mit dem großen Karel:</p>
<pre style="margin-left: 40px;">
drawKarel(4.0, 10, -40);</pre>
<p>
In der drawKarel() Methode, zeichnen wir dann ein GImage, skaliert wie gewünscht,</p>
<pre style="margin-left: 40px;">
private void <span style="color:#0000ff;">drawKarel</span>(double scale, int x, int y) {
GImage karel = new GImage("Karel0.png");
karel.scale(scale);
add(karel, (SIZE-karel.getWidth())/2 + x, (SIZE-karel.getHeight())/2 + y);
if (karel.getWidth() < 2) { // base case
return;
} else { // recursive case
<span style="color:#0000ff;">drawKarel</span>(scale / 2, x+=(5*scale), y-=(2.5*scale));
}
}</pre>
<p>
und rufen danach uns selbst wieder auf, allerdings soll das Bild dieses mal nur halb so groß sein, und etwas verschoben.</p>
<p>
Hier handelt es sich um eine ganz einfaches Beispiel von Selbstähnlichkeit, viele Fraktale beruhen auf einem ganz ähnlichen Prinzip.</p>
<p>
.</p>
<h2>
<img alt="" src="images/Tree2.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 174px; float: right;" />Tree</h2>
<p>
Bäume zu zeichnen ist eines von den Beispielen, die ganz einfach sind mit Rekursion, aber ziemlich knifflig werden wenn man es mit Iteration versucht. Ein Baum besteht aus Ästen, und wir zeichnen diese rekursiv, einen nach dem anderen. Wir schreiben wieder ein GraphicsProgram und beginnen damit den ersten Ast (also den Stamm) zu zeichnen:</p>
<pre style="margin-left: 40px;">
drawBranch(x, y, angle, length);</pre>
<p>
dabei sind <em>x</em> und <em>y</em> die Position wo ein Ast beginnt, <em>angle</em> ist der Winkel mit dem sich der Ast neigt, und <em>length</em> ist die Länge des Astes. In jeder <em>drawBranch()</em> Methode zeichnen wir also zunächst einen Ast als GLine,</p>
<pre style="margin-left: 40px;">
private void drawBranch(double x0, double y0, double angle,
double length) {
double x1 = x0 - Math.cos(angle) * length;
double y1 = y0 - Math.sin(angle) * length;
<span style="color:#0000ff;">drawLine(x0, y0, x1, y1, length);</span></pre>
<p>
Danach wollen aber rekursive jeweils zwei neue Zweige zeichnen, die ein klein bischen kürzer sein sollen, und sich auch zufällig ein bischen mehr nach links und rechts neigen sollen:</p>
<pre style="margin-left: 40px;">
// base case
if (length < 10)
return;
// recursive case
double bendAngle = Math.toRadians(rgen.nextDouble(-10, 10));
double branchAngle = Math.toRadians(rgen.nextDouble(-30, 30));
<span style="color:#0000ff;">drawBranch</span>(x1, y1, angle + bendAngle - branchAngle,
length * rgen.nextDouble(0.6, 0.8));
<span style="color:#0000ff;">drawBranch</span>(x1, y1, angle + bendAngle + branchAngle,
length * rgen.nextDouble(0.6, 0.8));
}</pre>
<p>
Wir brauchen natürlich auch ein Abbruchkriterium, und das ist sobald die Äste kürzer als zehn Pixel sind hören wir auf.</p>
<p>
.</p>
<h2>
<img alt="" src="images/ArithmeticExpression.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />ArithmeticExpression</h2>
<p>
Die Berechnung von arithmetischen Ausdrücken ist auch etwas was sich sehr schön mittels Rekursion lösen lässt. Betrachten wir dazu einen Ausdruck wie</p>
<pre style="margin-left: 40px;">
1 + 3 * 5</pre>
<p>
als Beispiel. Zunächst einmal ist das ein String den wir vom Nutzer erhalten</p>
<pre style="margin-left: 40px;">
String expression = readLine("Enter an expression:");
println( <span style="color:#0000ff;">evaluate</span>( expression ) );</pre>
<p>
und <em>evaluate()</em> ist die rekursive Methode die den eingegeben String auswerten soll.</p>
<p>
Beginnen wir mit dem <em>base case</em>: der tritt dann ein wenn unser String keine Operatoren enthält, dann ist es einfach eine Zahl, und wir können die einfach in einen <em>int</em> umwandeln:</p>
<pre style="margin-left: 40px;">
private int evaluate(String expression) {
// base case
if (!expression.contains("+") && !expression.contains("-") && !expression.contains("*")
&& !expression.contains("/")) {
return <span style="color:#0000ff;">Integer.parseInt(expression.trim())</span>;
}
...
}
</pre>
<p>
Kommen wir zum <em>recursive case</em>: wir wissen zwar nicht wie wir "1 + 3 * 5" ausrechnen können, aber wenn wir wüssten was "1" ist und was "3*5" ist, dann könnten wir es. D.h., wir berechnen erst einmal diese beiden, und kehren dann zurück (recur) zur Addition dieser beiden Terme. Deswegen spliten wir erst einmal den String beim '+',</p>
<pre style="margin-left: 40px;">
int i = expression.indexOf('+');
String o1 = expression.substring(0, i);
String o2 = expression.substring(i + 1, expression.length());
</pre>
<p>
und berechnen dann rekursiv:</p>
<pre style="margin-left: 40px;">
int result = evaluate(o1) + evaluate(o2);</pre>
<p>
d.h. der rechte Term beinhaltet <em>evaluate("1")</em> und der rechte <em>evaluate("3*5")</em>. Die werden jetzt beide wiederum rekursiv ausgewertet, bis wir jeweils beim <em>base case</em> ankommen. So motiviert betrachten wir den <em>recursive case</em>:</p>
<pre style="margin-left: 40px;">
// recursive case
int i = findPlusAndMinus(expression);
if (i < 0) {
i = findTimesAndDivideBy(expression);
}
String o1 = expression.substring(0, i);
String o2 = expression.substring(i + 1, expression.length());
int result = 0;
switch (expression.charAt(i)) {
case '+':
result = evaluate(o1) + evaluate(o2);
break;
case '-':
result = evaluate(o1) - evaluate(o2);
break;
case '*':
result = evaluate(o1) * evaluate(o2);
break;
case '/':
result = evaluate(o1) / evaluate(o2);
break;
}
return result;
}
</pre>
<p>
Wir suchen als erstes nach einem Plus oder einem Minus. Falls wir eines finden, dann schneiden wir den String auseinander, und je nachdem ob es ein Plus oder ein Minus ist, addieren oder sutrahieren wir das Ergebnis der <em>evaluate()</em> Methode mit den jeweilgen linken und rechten Teilstrings. Falls es kein Plus oder Minus gibt suchen wir nach einem Mal oder Geteilt-Durch, und machen dann das Gleiche.</p>
<p>
Obwohl es ja Punkt-vor-Strich heißt, und man naiv erwarten würde, dass man erst nach Mal und Geteilt-Durch sucht, und danach erst nach Plus und Minus, ist es in der Rekursion genau umgekehrt. Das hat damit zu tun, dass eben die rekursiven Schritte in umgekehrter Reihenfolge ausgeführt werden. Daran muss man sich erst gewöhnen, und das macht die Rekursion auch manchmal etwas gewöhnungsbedürftig.</p>
<p>
Interessanterweise, passiert dieses Zurückkehren glech nochmal: wenn wir "3*5/2" betrachten, dann soll von links nach rechts ausgewertet werden, also erst "3*5" und dann "15/2" (ergibt 7 in Ganzzahl-Arithmetik). Das bedeutet aber, da wir ja rekursiv arbeiten, dass wir in der <em>findTimesAndDivideBy()</em> Methode nicht von links nach rechts nach '*' oder '/' suchen, sondern von rechts nach links:</p>
<pre style="margin-left: 40px;">
private int findTimesAndDivideBy(String expression) {
int i;
<span style="color:#0000ff;">for (i = expression.length() - 1; i >= 0; i--) {</span>
if (expression.charAt(i) == '*' || expression.charAt(i) == '/') {
break;
}
}
return i;
}</pre>
<p>
Das Gleiche gilt auch für die <em>findPlusAndMinus()</em> Methode. Am besten man probiert es mal aus und sieht, dass es funktioniert. Dann kann man ja mal die naive Version versuchen, und wird feststellen, dass da was Falsches rauskommt. Und dann geht man am besten einfach Schritt-für-Schritt das einfache Beispiel "1 + 3 * 5" durch um zu sehen, wie das mit der Rekusion funktioniert. Danach hat man dann die Rekursion wirklich verstanden!</p>
<p>
.</p>
<h2>
<img alt="" src="images/Permutations.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />Permutations</h2>
<p>
Die Berechnung von Permutationen [4] ist auch ein Problem das sehr elegant mit Rekursion gelöst werden kann. Als Beispiel betrachten wir die Buchstabenkombination "abc". Wir wollen alle möglichen Permutationen dieser Buchstabenkombination auflisten, als da sind:</p>
<pre style="margin-left: 40px;">
abc, acb, bac, bca, cab, cba</pre>
<p>
Wichtig bei Permutationen ist, dass es auf die Reihenfolge der Buchstaben ankommt.</p>
<p>
Wir beginnen also indem wir den ersten Buchstaben festlegen, und permutieren dann die übrigen. Das sieht nach einem rekursiven Algorithmus aus: wir haben das größere Problem, permutiere eine Wort mit drei Buchstaben, auf ein einfacheres Problem, permutiere eine Wort mit zwei Buchstaben, zurückgeführt. Bleibt das Abbruchkriterium, und das sind Wörter die nur einen Buchstabe enthalten, da gibt es nur eine Permutation, der Buchstabe selbst.</p>
<pre style="margin-left: 40px;">
private void <span style="color:#0000ff;">permute</span>(String picked, String remaining) {
// base case
if (remaining.length() == 1) {
print(picked + remaining + ", ");
}
// recursive case
for (int i = 0; i < remaining.length(); i++) {
char pick = remaining.charAt(i); // pick a letter
String front = remaining.substring(0, i);
String back = remaining.substring(i + 1);
<span style="color:#0000ff;">permute</span>(picked + pick, front + back);
}
}</pre>
<p>
Was wir noch gerne wissen würden ist, wieviele Permutationen gibt es insgesamt?</p>
<p>
.</p>
<h2>
<img alt="" src="images/Subsets.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />Subsets</h2>
<p>
Bei Subsets [5] geht es um Untermengen: wir betrachten wieder die Buchstabenkombination "abc". Wir wollen alle möglichen Untermengen dieser Buchstabenkombination auflisten, auch das ist keine Raketenwissenschaft:</p>
<pre style="margin-left: 40px;">
abc, ab, ac, bc, a, b, c</pre>
<p>
Bei Untermengen spielt die Reihenfolge der Buchstaben keine Rolle. </p>
<p>
Die rekursive Lösung für dieses Problem ist nicht ganz offensichtlich, deswegen sehen wir uns erst mal den Code an, und versuchen ihn dann zu verstehen:</p>
<pre style="margin-left: 40px;">
private void <span style="color:#0000ff;">subset</span>(String picked, String remaining) {
// base case
if (remaining.length() == 0) {
print(picked + ", ");
// recursive case
} else {
char pick = remaining.charAt(0); // pick first letter
<span style="color:#0000ff;">subset</span>(picked + pick, remaining.substring(1));
<span style="color:#0000ff;">subset</span>(picked, remaining.substring(1));
}
}</pre>
<p>
Als Beispiel betrachten wir das Wort "abc": am Anfang enthält <em>picked</em> den Leerstring und <em>remaining</em> enthält "abc". Beim ersten Durchlauf, wird die Methode <em>subset()</em> zweimal aufgerufen, dabei einmal mit <em>picked="a"</em> und einmal mit <em>picked=""</em>, aber beide male mit <em>remaining="bc"</em>. Das kann man recht übersichtlich als Baum darstellen:</p>
<h2 style="margin-left: 40px;">
<img alt="" src="images/SubsetTree.png" style="margin-left: 10px; margin-right: 10px; width: 474px; height: 71px;" /></h2>
<p>
links steht immer der Wert von <em>picked</em>, und rechts der Wert von <em>remaining</em>. Wir sind fertig, wenn in <em>remaining</em> nichts mehr steht.</p>
<p>
Unser Code liefert auch den Leerstring als mögliches Subset. Das ist eine überaus nicht-triviale Entscheidung, sie hat nämlich mit den Gödelschen Unvollständigkeitssätzen zu tun [23]: In einer Stadt (ist nicht Nürnberg), in der es nur einen Herrenfriseur gibt, gibt es eine Verordnung die besagt, dass jeder Mann der sich nicht selbst rasiert vom Friseur rasiert wird. Hat der Friseur einen Bart? Das ist die Frage die die Grundfesten der Mathematik erschüttert hat, und von der sich selbige bis heute nicht erholt hat.</p>
<p>
Was wir noch gerne wissen würden ist, wieviele Subsets gibt es insgesamt?</p>
<p>
.</p>
<h2>
<img alt="" src="images/PascalTriangle.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />PascalTriangle</h2>
<p>
Das Pascalsche Dreieck [6] ist auch ein sehr anschauliches Beispiel für Rekursion. Wenn wir irgendeine Zahl in dem Dreieck nehmen, z.B. die 4, dann ist sie die Summe der beiden Zahlen links und rechts in der Zeile darüber, also 1+3. Das gilt für alle Zahlen in dem Dreieck. Dass das eine rekursive Beziehung ist sehen wir daran, dass 3, wiederum die Summe der beiden Zahlen 1 und 2 ist, in der Zeile darüber. Wir nummerieren die Zeilen mit <em>n</em>, und die Spalten mit <em>k</em>, dann gilt also</p>
<pre style="margin-left: 40px;">
private int pascalRecursion(int n, int k) {
// recursive case
return pascalRecursion(n - 1, k - 1) + pascalRecursion(n - 1, k);
}</pre>
<p>
Was ist das Abbruchkriterium? Wir sehen dass an den Seiten immer eine 1 steht. Für die linke Seite gilt immer <em>k==0</em> und für die rechte Seite gilt immer <em>k==n</em>. Also,</p>
<pre style="margin-left: 40px;">
private int pascalRecursion(int n, int k) {
if (k == 0 || k == n) { // base case
return 1;
} else { // recursive case
return pascalRecursion(n - 1, k - 1) + pascalRecursion(n - 1, k);
}
}</pre>
<p>
Damit lässt sich jetzt jede Zahl im Pascalsche Dreieck berechnen. Wenn wir noch über die Zeilen und Spalten iterieren, können wir das gesamt Dreieck darstellen.</p>
<p>
Kommen wir zur Bedeutung des Pascalschen Dreiecks: es hat mit den Binomialkoeffizienten zu tun. Zur Erinnerung, was sind die Binomialkoeffizienten:</p>
<pre style="margin-left: 40px;">
(a + b)¹ = <span style="color:#0000ff;">1</span>*a + <span style="color:#0000ff;">1</span>*b
(a + b)² = <span style="color:#0000ff;">1</span>*a² + <span style="color:#0000ff;">2</span>*a*b + <span style="color:#0000ff;">1</span>*b²
(a + b)³ = <span style="color:#0000ff;">1</span>*a³ + <span style="color:#0000ff;">3</span>*a²*b + <span style="color:#0000ff;">3</span>*a*b² + <span style="color:#0000ff;">1</span>*b²</pre>
<p>
das sind die blauen Zahlen vor den Termen, und wenn wir diese mit den Zahlen im Pascalsche Dreieck vergleichen sollten wir erkennen, dass die sich sehr ähnlich sehen. Also stellt das Pascalsche Dreieck eine sehr einfache Art und Weise dar die Binomialkoeffizienten auszurechnen.</p>
<p>
Interessant ist auch die Beziehung zwischen dem Pascalschen Dreieck und den Fibonacci-Zahlen [6].</p>
<p>
.</p>
<h2>
<img alt="" src="images/Combinations.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />Combinations</h2>
<p>
Das Pascalsche Dreieck ist nicht nur hübsch und hat alle möglichen interessanten mathematischen Eigenschaften, es hat auch eine durchaus praktische Anwendung, mit der wir nicht selten zu tun haben werden: manchmal sollen wir alle möglichen Paare aus einer Menge von z.B. vier Personen auflisten [7]. In dem Fall sagen wir, wir wollen alle möglichen Zweier-Kombination aus den vier Personen finden, man sagt auch 2 aus 4. Nehmen wir an die vier Personen heißen a, b, c und d, dann gibt es folgende Paarkombinationen:</p>
<pre style="margin-left: 40px;">
ab, ac, ad, bc, bd, cd</pre>
<p>
Auch hier können wir wieder eine rekursive Beziehung erkennen:</p>
<pre style="margin-left: 40px;">
private void <span style="color:#0000ff;">combinations</span>(int n, int k, String picked, String remaining) {
// base case
if (k == 0) {
print(picked + ", ");
} else if ((k == n)) {
print(picked + remaining + ", ");
// recursive case
} else {
char pick = remaining.charAt(0); // pick first letter
<span style="color:#0000ff;">combinations</span>(n - 1, k, picked, remaining.substring(1));
<span style="color:#0000ff;">combinations</span>(n - 1, k - 1, picked + pick, remaining.substring(1));
}
}.</pre>
<p>
Der Code ist ähnlich zu dem von Subsets, allerdings durch die <em>n</em> und <em>k</em>, etwas komplizierter. Am besten wir betrachten wieder die Darstellung als Baum:</p>
<h2 style="margin-left: 40px;">
<img alt="" src="images/CombinationsTree.png" style="margin-left: 10px; margin-right: 10px; width: 541px; height: 99px;" /></h2>
<p>
von links nach rechts stehen die Werte von <em>n</em>, <em>k</em>, <em>picked</em> und <em>remaining</em>. Nehmen wir an wir wollen alle Zweierkombination aus dem Wort "abcd". Dann ist <em>n=4</em> die Länge des Worts, <em>k=2</em> steht für Zweierkombinationen, und <em>picked</em> ist am Anfang leer, und <em>remaining</em> enthält "abcd". </p>
<p>
Im ersten Schritt haben wir die Möglichket 'a' zu wählen (rechts) oder nicht zu wählen (links). Wenn wir 'a' gewählt haben, können wir als nächstes 'b' wählen (wieder rechts) oder 'b' nicht wählen (wieder links). Wenn wir 'b' gewählt haben, sind wir fertig, da wir ja schon zwei Buchstaben ('a' und 'b') gewählt haben. Wenn wir 'b' nicht gewählt haben, dann bleiben noch zwei Möglichkeiten: wir können 'c' wählen (rechts), oder 'c' nicht wählen (links). Wenn wir 'c' wählen, sind wir fertig weil wir 'a' und 'c' gewählt haben. Wenn wir 'c' nicht gewählt haben, sind wir auch fertig, weil es nur noch 'd' zu wählen gibt um einer Zweierkombination zu bilden, ansonsten wäre es nämlich eine Einserkombination.</p>
<p>
Und was hat das jetzt mit dem Pascalsche Dreieck zu tun? Es sagt uns wieviele Kombinationen es gibt. Nehmen wir unser Beispiel mit 2 aus 4: 4 ist n, also die Zeile, und 2 ist k, also die Position in der Zeile. Wenn wir nachsehen, dann ist in der vierten Zeile an der zweiten Position die 6. (Wie üblich beginnen wir mit 0 zu zählen.) Und das ist auch was wir gefunden haben: 6 Zweierkombinationen.</p>
<p>
.</p>
<h2>
<img alt="" src="images/SierpinskiTriangle.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 231px; float: right;" />Sierpinski Triangle</h2>
<p>
Das Sierpinski-Dreieck [8] ist ein anderes visuelles Beispiel für Rekursion. Dabei beginnt man mit dem ganz großen Dreieck, darin zeichnet man dann drei kleine Dreiecke, und in jedes dieser kleinen wieder drei kleine, und so weiter. </p>
<pre style="margin-left: 40px;">
void drawSierpinski(double x, double y, double w, double h) {
drawTriangle(x, y, w, h);
// base case
if ((w < 2.0) || (h < 2.0)) {
return;
}
// recursive case
double h2 = h / 2;
double w2 = w / 2;
drawSierpinski(x, y, w2, h2);
drawSierpinski(x + w2 / 2, y + h2, w2, h2);
drawSierpinski(x + w2, y, w2, h2);
}</pre>
<p>
Die <em>drawTriangle()</em> benutzt eine GPolygon um ein Dreieck beginnend an der Position x,y mit der Breite w und der Höhe h zu zeichnen.</p>
<p>
Beim Sierpinski-Dreieck handelt es sich um ein typisches Fraktal. Fraktale haben die Eigenschaft der Selbstähnlichkeit, d.h. sie bestehen aus kleineren Teilen von sich selbst, die sich immer wieder wiederholen. Es gibt übrigens eine interessante Beziehung zwischen dem Tower of Hanoi Problem und dem Sierpinski Dreieck [9], und auch das Pascalsche Dreieck hat mit dem Sierpinski Dreieck verwandschaftliche Beziehungen. </p>
<p>
.</p>
<h2>
<img alt="" src="images/Mondrian.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 200px; float: right;" />Mondrians</h2>
<p>
Piet Mondrian [10] war ein niederländischer Maler dessen späteren Werke vor allem der Rekursion gewidmet waren. Bewiesen haben das Eric Roberts und Julie Zelenski [11]. Der Beweis geht wie folgt:</p>
<ol>
<li>
im ersten Schritt haben wir drei Optionen:
<ol>
<li>
wir teilen die Leinwand horizontal in zwei kleinere Leinwände oder</li>
<li>
wir teilen die Leinwand vertikal in zwei kleinere Leinwände oder</li>
<li>
wir tun gar nichts;</li>
</ol>
</li>
<li>
für jede der kleineren Leinwände wenden wir wieder Schritt 1 an, bis die Leinwände zu klein sind.</li>
</ol>
<p>
In Java sieht das dann so aus:</p>
<pre style="margin-left: 40px;">
private void drawMondrian(int i, int j, int width, int height) {
// base case
if ((width < MIN_SIZE) || (height < MIN_SIZE)) {
return;
}
// recursive case
int choice = rgen.nextInt(0, 2);
switch (choice) {
case 0: // divide canvas horizontally
drawMondrian(i, j, width / 2, height);
drawMondrian(i + width / 2, j, width / 2, height);
break;
case 1: // divide canvas vertically
drawMondrian(i, j, width, height / 2);
drawMondrian(i, j + height / 2, width, height / 2);
break;
default: // do nothing
drawRectangle(i, j, width, height);
break;
}
}</pre>
<p>
Dabei zeichnet <em>drawRectangle()</em> ein GRect mit einer zufälligen Farbe. Damit das aber dann wie ein Mondrian aussieht, sollte man sich bei den Farben auf weiß, blau, gelb und rot beschränken. Nicht alle Mondrians werden was, man muss das ein paar Mal laufen lassen. Aber ab und zu kommen echte Originale raus.</p>
<p>
.</p>
<h2>
<img alt="" src="images/Maze2.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 222px; float: right;" />Maze</h2>
<p>
Es gibt zig Algorithmen um Labyrinthe zu erzeugen. Einer der einfacheren ist ein rekursiver, der aus einem Rechteck ein Labyrinth erzeugt [12]:</p>
<ol>
<li>
wähle einen zufälligen Punkt innerhalb des großen Rechtecks und zeichne zwei Wände durch diesen Punkt, eine horizontal, die andere vertikal, es ergeben sich vier kleine Rechtecke;</li>
<li>
die beiden Wände die wir gerade eingezogen haben, teilen sich gegenseitig in je zwei Hälften, deswegen haben wir jetzt vier innere Wände. In drei dieser Wände machen wir ein Loch an einer zufälligen Position;</li>
<li>
für jedes der vier kleinen Rechtecke wiederholen wir Schritt 1 solange bis die Breite oder Höhe der Rechtecke gleich der Zellbreite ist.</li>
</ol>
<p>
Als erstes benötigen wir eine Methode, die unser großes Rechteck mit je zwei Wänden zerteilt:</p>
<pre style="margin-left: 40px;">
divisionByTwoWalls(0, SIZE, 0, SIZE);</pre>
<p>
In dieser Methode checken wir als erstes den <em>base case</em>:</p>
<pre style="margin-left: 40px;">
private void divisionByTwoWalls(int x0, int x1, int y0, int y1) {
// base case
if ((x1 - x0) < 2 * MIN_WIDTH || (y1 - y0) < 2 * MIN_WIDTH) {
return;
}
...</pre>
<p>
dabei ist <em>MIN_WIDTH</em> die Zellbreite. Kommen wir zum <em>recursive</em> case. Hier wählen wir einen zufälligen Punkt innerhalb unseres Rechtecks (der aber quantisiert sein sollte):</p>
<pre style="margin-left: 40px;">
int x = rgen.nextInt(x0 + MIN_WIDTH, x1 - MIN_WIDTH) / MIN_WIDTH * MIN_WIDTH;
int y = rgen.nextInt(y0 + MIN_WIDTH, y1 - MIN_WIDTH) / MIN_WIDTH * MIN_WIDTH;</pre>
<p>
dann sollen wir zwei Wände einzeichnen. Es ist aber besser vier halbe Wände einzuzeichnen:</p>
<pre style="margin-left: 40px;">
int noHole = rgen.nextInt(0, 3);
drawLineWithRandomOpening(x, y0, x, y, noHole == 0);
drawLineWithRandomOpening(x, y, x, y1, noHole == 1);
drawLineWithRandomOpening(x0, y, x, y, noHole == 2);
drawLineWithRandomOpening(x, y, x1, y, noHole == 3);</pre>
<p>
von denen eine kein Loch bekommt. Bleibt nur noch, dass wir uns selbst wieder für jedes der vier kleinen Rechtecke rekursiv aufrufen:</p>
<pre style="margin-left: 40px;">
divisionByTwoWalls(x0, x, y0, y);
divisionByTwoWalls(x, x1, y0, y);
divisionByTwoWalls(x0, x, y, y1);
divisionByTwoWalls(x, x1, y, y1);
}</pre>
<p>
Die Methode <em>drawLineWithRandomOpening()</em>, die eine Wand mit einem zufälligen Loch zeichnet sieht wie folgt aus:</p>
<pre style="margin-left: 40px;">
private void drawLineWithRandomOpening(int x0, int y0, int x1, int y1,
boolean withNoOpening) {
if (withNoOpening) {
drawLine(x0, y0, x1, y1);
} else {
if (x0 == x1) { // vertical
int y = rgen.nextInt(y0, y1 - MIN_WIDTH) / MIN_WIDTH
* MIN_WIDTH;
drawLine(x0, y0, x1, y);
drawLine(x0, y + MIN_WIDTH, x1, y1);
} else {// horizontal
int x = rgen.nextInt(x0, x1 - MIN_WIDTH) / MIN_WIDTH
* MIN_WIDTH;
drawLine(x0, y0, x, y1);
drawLine(x + MIN_WIDTH, y0, x1, y1);
}
}
}</pre>
<p>
Eigentlich müsste das ein Fünfzeiler sein, mir ist aber einfach keine einfachere Lösung eingefallen.</p>
<p>
.</p>
<h2>
<img alt="" src="images/Lightning.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 200px; float: right;" />Lightning</h2>
<p>
Im Internet bin ich zufällig über eine interessante Anwendung für Rekursion gestoßen, einen Blitzgenerator [13]. Er verwendet den sogenannten Midpoint-Displacement Algorithmus [14] um Blitze zu zeichnen. Der Mittelpunktverschiebungs-Algorithmus funktioniert folgendermaßen:</p>
<ol>
<li>
wir beginnen mit zwei Punkten, die wir mit einer Linie verbinden wollen;</li>
<li>
aber anstelle die Linie direkt zu zeichnen, halbieren wir die Strecke, und verschieben den Mittelpunkt der Strecke senkrecht zur Strecke um einen gewissen Betrag, das <em>Displacement</em>;</li>
<li>
mit den beiden Hälften wiederholen wir das Verfahren, dabei wird der Betrag des <em>Displacements</em> jedesmal halbiert;</li>
<li>
wir hören auf, wenn das <em>Displacement</em> kleiner als ein bestimmter Wert ist.</li>
</ol>
<p>
In Java sieht das Ganze dann so aus:</p>
<pre style="margin-left: 40px;">
private void drawLightning(double x1, double y1, double x2, double y2,
double displace) {
// base case
if (displace < 2) {
drawLine(x1, y1, x2, y2);
// recursive case
} else {
double mid_x = (x2 + x1) / 2.0;
double mid_y = (y2 + y1) / 2.0;
mid_x += (Math.random() - 0.5) * displace;
mid_y += (Math.random() - 0.5) * displace;
drawLightning(x1, y1, mid_x, mid_y, displace / 2);
drawLightning(x2, y2, mid_x, mid_y, displace / 2);
}
}</pre>
<p>
Man könnte es jetzt in unserer CityAtNight aus dem ersten Semester blitzen lassen...</p>
<p>
.</p>
<h2>
<img alt="" src="images/PlasmaFractal.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 222px; float: right;" />PlasmaFractal</h2>
<p>
Den Mittelpunktverschiebungs-Algorithmus [14] kann man nicht nur auf Linien, sondern auch auf Ebenen anwenden [15]. Man beginnt mit einem Rechteck, legt die Farben der Eckpunkte fest, und gibt dem Mittelpunkt des Rechtecks eine zufällige Farbe. Man teilt das Rechteck dann in vier kleinere Rechtecke und beginnt mit dem Prozess von Vorne. Das macht man solange, bis die Rechtecke kleiner als ein Pixel sind. Das Verfahren eignet sich sehr gut um Wolken zu generieren, dann sollte man natürlich verschiedene Blautöne als Farben wählen. Man kann es aber auch zur Generierung von Terrains verwenden, dann entsprechen die Farbewerte den Höhen im Terrain.</p>
<p>
.</p>
<hr />
<h1>
Challenges</h1>
<p>
.</p>
<h2>
<img alt="" src="images/SierpinskiCarpet.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 231px; float: right;" />SierpinskiCarpet</h2>
<p>
Der Herr Sierpinski hat sich nicht nur mit Dreiecken sondern auch mit Teppichen beschäftigt [16]. Es handelt sich auch wieder um eine fraktale Struktur. Um einen Sierpinski Teppich herzustellen folgt man diesen Anweisungen:</p>
<ol>
<li>
teile das Rechteck in neun gleich große Rechtecke;</li>
<li>
entferne das mittlere, und wiederhole den ersten Schritt mit den acht übrig gebliebenen Rechtecken.</li>
</ol>
<p>
Es gibt auch eine dreidimensionale Version des Sierpinski Teppichs, die auch unter dem Namen Menger-Schwamm bekannt ist [17].</p>
<p>
.</p>
<p>
.</p>
<p>
.</p>
<h2>
<img alt="" src="images/TSquare.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 224px; float: right;" />TSquare</h2>
<p>
Ähnlich wie die Sierpinski Dreiecke und Teppiche ist auch das TSquare ein Fraktal. Die Konstruktion ist eigentlich auch ganz einfach:</p>
<ol>
<li>
beginne mit einem Quadrat, das halb so groß ist wie die Fläche die zur Verfügung steht, und platziere es in die Mitte;</li>
<li>
an jeder Ecke diese Quadrats platziere mittig je ein neues Quadrat, das halb so groß ist wie das ursprüngliche;</li>
<li>
wiederhole den Vorgang solange, bis die Quadrat die Größe eines Pixels haben.</li>
</ol>
<p>
Man kann so etwas natürlich auch mit Dreiecken, Fünfecken, usw. machen.</p>
<p>
.</p>
<p>
.</p>
<h2>
<img alt="" src="images/QuadraticCross.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 237px; float: right;" />QuadraticCross</h2>
<p>
Das Quadratic Cross, auch Vicsek Fraktal genannt, ist ähnlich zum TSquare. Aber anstelle Quadrate hinzuzufügen, werden welche weggenommen. Wir beginnen also mit einer schwarzen Fläche. Dann folgen wir diesen Schritten:</p>
<ol>
<li>
teile das Quadrat in neun gleich große Quadrate, und entferne die Eckquadrate;</li>
<li>
tue das gleich mit den übrig gebliebenen fünf Quadraten.</li>
</ol>
<p>
Dabei kommt dann etwas zum Vorschein, dass ein bischen wie ein Kreuz aussieht. Antennen in Handys werden von diesem Fraktal inspiriert [20].</p>
<p>
.</p>
<p>
.</p>
<p>
.</p>
<p>
.</p>
<h2>
<img alt="" src="images/HTree.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 231px; float: right;" />HTree</h2>
<p>
Später wenn wir mit Bäumen arbeiten, dann werden wir den H-Baum brauchen [21]. Im Moment beschränken wir uns darauf, dass er ganz einfach zu konstruiren ist. Die Konstruktionsvorschrift geht folgendermaßen:</p>
<ol>
<li>
zeichne eine Linie in die Mitte, die halb so lange ist wie die Breite die zur Verfügung steht;</li>
<li>
dann zeichne zwei Linien an den jeweiligen Endpunkten, die senkrecht sind, und deren Länge 1/√2 mal so lange ist;</li>
<li>
wiederhole Schritt 2 solange bis die Länge kleiner als z.B. 15 ist.</li>
</ol>
<p>
.</p>
<p>
.</p>
<p>
.</p>
<p>
.</p>
<h2>
<img alt="" src="images/KochSnowflake.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 231px; float: right;" />KochSnowflake</h2>
<p>
Kommen wir zum letzten Projekt in diesem Kapitel, der Koch-Kurve [22], die etwas an eine Schneeflocke erinnert. Auch bei der Koch-Kurve handelt es sich um ein Fraktal. Die Koch-Kurve beginnt als Dreieck:</p>
<ol>
<li>
zeichne ein gleichseitiges Dreieck;</li>
<li>
teile jedes der drei Seitenteile in drei gleiche Teile;</li>
<li>
entferne das mittlere dieser drei Teile, und ersetze es durch ein gleichseitiges Dreieck das nach außen zeigt;</li>
<li>
entferne die Basis dieses neuen Dreiecks;</li>
<li>
wiederhole Schritt 2.</li>
</ol>
<p>
Auf der Seite der Wikipedia gibt es eine Animation in der man in die Koch-Kurve "hineinfliegt", eine sehr schöne Verdeutlichung was Selbstähnlichkeit wirklich bedeutet.</p>
<p>
.</p>
<p>
.</p>
<hr />
<h1>
Research</h1>
<p>
In diesem Kapitel gibt es mal was richtig Interessantes zu erforschen.</p>
<p>
.</p>
<h2>
Gödel's Unvollständigkeitssatz</h2>
<p>
Für die Mathematiker ging die Welt unter, den Rest der Menschheit hat es eigentlich nicht interessiert: der Gödelsche Unvollständigkeitssatz [23]. Die traurige Geschichte beginnt mit der <em>Principia Mathematica</em> [24] von Russell und Whitehead, führt dann zu <em>Russell's Paradox</em> [25], und endet mit <em>Gödel's Unvollständigkeitssatz</em>. Wenn einer keine traurigen Geschichten mag, sollte er das vielleicht nicht nachlesen, wen aber Horror pur leidenschaftlich anzieht, dem wird die Geschichte gefallen. Im Ernst, es ist schockierend wie wenige Leute jemals über die Erschütterung (und Zerstörung) der Grundfeste der Mathematik etwas gehört haben. Spricht für unser Bildungssystem...</p>
<p>
.</p>
<hr />
<h1>
Fragen</h1>
<ol>
<li>
Der folgende Code ist ein Beispiel für die Berechnung der Fakultät einer Zahl. Aber etwas stimmt nicht mit diesem Code. Was ist es?<br />
<pre style="margin-left: 40px;">
public int factorial(int n) {
return n * factorial( n-1 );
}</pre>
</li>
<li>
Beschreiben Sie in griben Zügen ein Programm, das einen Baum rekursiv zeichnet.<br />
</li>
<li>
Ist der folgende Algorithmus ein rekursiver oder ein iterativer Algorithmus?<br />
<pre style="margin-left: 40px;">
private int choose(int n, int k) {
if ( (k == 0) || (k == n) ) {
return 1;
} else {
return choose(n-1, k) + choose(n-1, k-1);
}
}</pre>
</li>
<li>
Was ist ein rekursiver Algorithmus, was sind seine Vorteile, was sind seine Nachteile?<br />
</li>
<li>
Schreiben Sie zwei Methoden namens <em>powerIteration(double x, int n)</em> und <em>powerRecursion(double x, int n)</em>. Die erste Funktion sollte die Leistung der Zahl x auf die Leistung n iterativ berechnen, die zweite rekursiv.<br />
</li>
<li>
Rekursion folgt immer dem gleichen Muster. Nennen Sie die beiden Schritte die nötig sind, um einen Algorithmus rekursiv umzusetzen.<br />
</li>
<li>
Schreiben Sie eine rekursive Methode public boolean <em>isPalindrome(String s)</em> die prüft, ob eine gegebene Zeichenkette ein Palindrom ist. ("otto" und "rentner" sind zwei Beispiele für Palindrome.)<br />
</li>
<li>
In der Vorlesung und auch den Labs haben wir “Mondrians” gezeichnet. Skizzieren (malen) Sie grob wie diese aussehen.<br />
</li>
<li>
In der Vorlesung und auch den Labs haben wir Sierpinski Dreiecke (Sierpinski Triangles) gezeichnet. Skizzieren (malen) Sie grob wie diese aussehen.<br />
</li>
<li>
Was ist ein "divide and conquer" Algorithmus? Erklären Sie, wie diese funktionieren.</li>
</ol>
<p>
.</p>
<hr />
<h1>
Referenzen</h1>
<p>
Das wunderbare Buch "Einführung in die Programmierung in Java" von Robert Sedgewick und Kevin Wayne hat eine wunderbare Sammlung von Rekursionsalgorithmen: http://www.cs.princeton.edu/introcs/23recursion/. Das ist eigentlich Pflichtlektüre. </p>
<p>
[1] Palindrome, <a href="https://en.wikipedia.org/wiki/Palindrome">https://en.wikipedia.org/wiki/Palindrome</a></p>
<p>
[2] The long and short of it, The Economist, Johnson Language, <a href="http://www.economist.com/blogs/johnson/2010/06/short_and_long_words">www.economist.com/blogs/johnson/2010/06/short_and_long_words</a></p>
<p>
[3] Tower of Hanoi, <a href="https://en.wikipedia.org/wiki/Tower_of_Hanoi">https://en.wikipedia.org/wiki/Tower_of_Hanoi</a></p>
<p>
[4] Permutation, <a href="https://en.wikipedia.org/wiki/Permutation">https://en.wikipedia.org/wiki/Permutation</a></p>
<p>
[5] Subset, <a href="https://en.wikipedia.org/wiki/Subset">https://en.wikipedia.org/wiki/Subset</a></p>
<p>
[6] Pascalsches Dreieck, <a href="https://de.wikipedia.org/wiki/Pascalsches_Dreieck">https://de.wikipedia.org/wiki/Pascalsches_Dreieck</a></p>
<p>
[7] Combination, <a href="https://en.wikipedia.org/wiki/Combination">https://en.wikipedia.org/wiki/Combination</a></p>
<p>
[8] Sierpinski triangle, <a href="https://en.wikipedia.org/wiki/Sierpinski_triangle">https://en.wikipedia.org/wiki/Sierpinski_triangle</a></p>
<p>
[9] Tower of Hanoi, <a href="https://en.wikipedia.org/wiki/Tower_of_Hanoi">https://en.wikipedia.org/wiki/Tower_of_Hanoi</a></p>
<p>
[10] Piet Mondrian, <a href="https://en.wikipedia.org/wiki/Piet_Mondrian">https://en.wikipedia.org/wiki/Piet_Mondrian</a></p>
<p>
[11] Programming Abstractions in C++, Eric S. Roberts and Julie Zelenski, Stanford University</p>
<p>
[12] Maze generation algorithm, <a href="https://en.wikipedia.org/wiki/Maze_generation_algorithm">https://en.wikipedia.org/wiki/Maze_generation_algorithm</a></p>
<p>
[13] Lightning Generator, <a href="https://krazydad.com/bestiary/bestiary_lightning.html">https://krazydad.com/bestiary/bestiary_lightning.html</a></p>
<p>
[14] Diamond-square algorithm, <a href="https://en.wikipedia.org/wiki/Diamond-square_algorithm">https://en.wikipedia.org/wiki/Diamond-square_algorithm</a></p>
<p>
[15] Plasma Fractal, Justin Seyster, <a href="http://jseyster.github.io/plasmafractal/">http://jseyster.github.io/plasmafractal/</a></p>
<p>
[16] Sierpinski carpet, <a href="https://en.wikipedia.org/wiki/Sierpinski_carpet">https://en.wikipedia.org/wiki/Sierpinski_carpet</a></p>
<p>
[17] Menger sponge, <a href="https://en.wikipedia.org/wiki/Menger_sponge">https://en.wikipedia.org/wiki/Menger_sponge</a></p>
<p>
[18] T-square, <a href="https://en.wikipedia.org/wiki/T-square_(fractal)">https://en.wikipedia.org/wiki/T-square_(fractal)</a></p>
<p>
[19] Vicsek fractal, <a href="https://en.wikipedia.org/wiki/Vicsek_fractal">https://en.wikipedia.org/wiki/Vicsek_fractal</a></p>
<p>
[20] Fractal antenna, <a href="https://en.wikipedia.org/wiki/Fractal_antenna">https://en.wikipedia.org/wiki/Fractal_antenna</a></p>
<p>
[21] H tree, <a href="https://en.wikipedia.org/wiki/H_tree">https://en.wikipedia.org/wiki/H_tree</a></p>
<p>
[22] Koch snowflake, <a href="https://en.wikipedia.org/wiki/Koch_snowflake">https://en.wikipedia.org/wiki/Koch_snowflake</a></p>
<p>
[23] Kurt Gödel, <a href="https://en.wikipedia.org/wiki/Kurt_Gödel">https://en.wikipedia.org/wiki/Kurt_Gödel</a></p>
<p>
[24] Principia Mathematica, <a href="https://en.wikipedia.org/wiki/Principia_Mathematica">https://en.wikipedia.org/wiki/Principia_Mathematica</a></p>
<p>
[25] Russell's paradox, <a href="https://en.wikipedia.org/wiki/Russell%27s_paradox">https://en.wikipedia.org/wiki/Russell%27s_paradox</a></p>
<p>
.</p>
<p class="footer">
Copyright © 2016-2021 <a href="http://www.lano.de">Ralph P. Lano</a>. All rights reserved.
</p>
</div>
</center>
</div>
</body>
</html>