Tree data structure search

Peter_Mueller

Hallo,

die Tiefensuche kann man ja rekursiv formulieren.

z.B. hier in Java

private static void printTree(Node node, String appender) {
   System.out.println(appender + node.getId());
   for (Node child: node.getChildren()) {
       printTree(child, appender + appender); // keine Ahnung warum hier 2 mal  
                                              // appender steht
   }
}

Geht das auch bei der Breitensuche ?

Gruss!

SideWinder

Klar, siehe https://de.wikipedia.org/wiki/Breitensuche#Algorithmus_.28formal.29

MfG SideWinder

SeppJ

Generell kannst du alle iterativen Formulierungen auch rekursiv ausdrücken. Die Transformation ist sogar mittels Kochrezept möglich.

Skym0sh0

SeppJ schrieb:

Generell kannst du alle iterativen Formulierungen auch rekursiv ausdrücken. Die Transformation ist sogar mittels Kochrezept möglich.

Lustigerweise dachte ich in meiner Anfangszeit als Programmierer, dass Rekursion nicht so viel kann wie Iteration.

I could never be so wrong...

SeppJ

Skym0sh0 schrieb:

SeppJ schrieb:

Generell kannst du alle iterativen Formulierungen auch rekursiv ausdrücken. Die Transformation ist sogar mittels Kochrezept möglich.

Lustigerweise dachte ich in meiner Anfangszeit als Programmierer, dass Rekursion nicht so viel kann wie Iteration.

I could never be so wrong...

Liegt vielleicht da dran, dass die typischen Lehrbeispiele für Rekursion solche sind, die man trivial (und wesentlich besser!) als Schleife implementieren könnte.

* Ich schaue da die Fakultät böse an *

Ein Glück war mein Einführungsbeispiel das Zeichnen von Fraktalen. Das als Schleife zu implementieren ist nur möglich, indem man quasi den Callstack nachprogrammiert, was auch nur Rekursion auf einer anderen Ebene ist. Dann wird schnell klar, dass Rekursion einen Mehrwert gegenüber Schleifen bietet.

(Wobei es bei mir peinlicherweise eine Weile gedauert hat, bis mir klar wurde, dass jede Schleife auch eine Rekursion ist)

Peter_Mueller

von fraktalen hab ich keine Ahnung. In meinem Informatik Studium wurde das nie behandelt.

Peter_Mueller schrieb:

von fraktalen hab ich keine Ahnung. In meinem Informatik Studium wurde das nie behandelt.

kannst ja mal die Koch Kurve ansehen, dass ist ein nettes Fraktal dass man auch schnell mal nachprogrammieren kann: https://de.wikipedia.org/wiki/Koch-Kurve
Man wendet bei Fraktalen halt einfache geometrische Regeln rekursiv an - das heißt, die Figuren besitzen die selben Muster in sehr verschiedenen Größen.