hotti: Verschachtelte Liste ohne Rekursion darstellen

hi,

s. Thema. Ziel ist eine verschachtelte <ul>... Bisher habe ich eine Rekursion, die durch die Datenquelle läuft, die Anzahl der Kindknoten ermittelt und das dann entsprechend umsetzt. Von der Rekursion möchte ich wegkommen und suche einen anderen Ansatz. Wahrscheinlich muss ich die Datenquelle umarbeiten (nested) aber hier komme ich auch nicht weiter.

Bitte mal um Hinweise,
Hotti

--
Wenn der Kommentar nicht zum Code passt, kann auch der Code falsch sein.
  1. s. Thema. Ziel ist eine verschachtelte <ul>... Bisher habe ich eine Rekursion, die durch die Datenquelle läuft, die Anzahl der Kindknoten ermittelt und das dann entsprechend umsetzt. Von der Rekursion möchte ich wegkommen und suche einen anderen Ansatz. Wahrscheinlich muss ich die Datenquelle umarbeiten (nested) aber hier komme ich auch nicht weiter.

    Ich hab' keine Ahnung was du meinst :)

    http://suit.rebell.at/fileadmin/a-26/source.tar.gz - ja ist wieder PHP, aber die funktion "build_tree()" ruft sich selbst auf (Rekursion), während sie die Datenquelle durchläuft.

    Ich wüsste nicht wie man das sonst lösen könnte ohne eine endliche Tiefe hardcodiert zu verankern.

    1. Moin suit,

      Ich wüsste nicht wie man das sonst lösen könnte ohne eine endliche Tiefe hardcodiert zu verankern.

      Jede rekursive Lösung lässt sich auch iterativ abbilden. Rekursion und Iteration sind gleich mächtig. Notfalls baut man einen Stack nach, in dem alle Iterations-bedingten Variablen gespeichert werden.

      LG,
       CK

      1. Der Vorteil einer iterativen Lösung im Vergleich zur rekursiven Variante ist jedoch wenn überhaupt ein geringerer Speicherverbrauch. Rekursion kommt bei derartigen Problemen insbesondere der Lesbarkeit des Codes zugute.

        Gruß, LX

        --
        RFC 2324, Satz 7 (Sicherheit): Jeder, der zwischen meinem Kaffee und mir steht, gilt als unsicher.
        1. Der Vorteil einer iterativen Lösung im Vergleich zur rekursiven Variante ist jedoch wenn überhaupt ein geringerer Speicherverbrauch. Rekursion kommt bei derartigen Problemen insbesondere der Lesbarkeit des Codes zugute.

          Plan a: Die Rekursion "ins Reine" schreiben und gut?

          Hotti

      2. Jede rekursive Lösung lässt sich auch iterativ abbilden. Rekursion und Iteration sind gleich mächtig. Notfalls baut man einen Stack nach, in dem alle Iterations-bedingten Variablen gespeichert werden.

        Ja aber eine Funktion die sich selbst aufruft und so einer weitere Iteration von sich selbst durchführt ist eine Rekursion - oder verstehe ich dich jetzt falsch?

        1. Moin suit,

          Ja aber eine Funktion die sich selbst aufruft und so einer weitere Iteration von sich selbst durchführt ist eine Rekursion

          Ja.

          oder verstehe ich dich jetzt falsch?

          Keine Ahnung. Was hast du denn verstanden?

          LG,
           CK

          1. Ja aber eine Funktion die sich selbst aufruft und so einer weitere Iteration von sich selbst durchführt ist eine Rekursion

            Ja.

            oder verstehe ich dich jetzt falsch?

            Keine Ahnung. Was hast du denn verstanden?

            Was der unterschied zwischen einer sich selbst aufrufenden Funktion ist (die dadurch mehrfach durchlaufen, also iteriert, wird) und einer "Rekursion" :)

            1. Moin suit,

              Was der unterschied zwischen einer sich selbst aufrufenden Funktion ist (die dadurch mehrfach durchlaufen, also iteriert, wird) und einer "Rekursion" :)

              Ich glaube, hier gibt es eine Begriffs-Verwirrung. Es gibt rekursive Lösungen, da nennt man die einzelnen Durchläufe „Rekursions-Stufen.” Und es gibt iterative, also nicht-rekursive Lösungen, da nennt man die einzelnen Durchläufe „Iterationen.” Meine Aussage war: Zu jeder rekursiven Lösung gibt es eine iterative Lösung und vice versa.

              LG,
               CK

            2. hi Suit,

              Keine Ahnung. Was hast du denn verstanden?

              Was der unterschied zwischen einer sich selbst aufrufenden Funktion ist (die dadurch mehrfach durchlaufen, also iteriert, wird) und einer "Rekursion" :)

              Eine Funktion, die sich selbst aufruft, arbeitet rekursiv und nicht iterativ. Bei einer Iteration gehts in definierten Schritten linear durch die Menge, ohne dass sich die Funktion innerhalb der Iteration selbst aufruft.

              Wenn bei einer Iteration eine Zählvariable erforderlich ist, heißt die immer 'i' (ne Scherz).

              Du kannst eine Rekursion auch sichtbar machen: Stelle Dich zwischen zwei Spiegel und schau in den einen rein ;)

              Hotti

              1. Keine Ahnung. Was hast du denn verstanden?

                Was der unterschied zwischen einer sich selbst aufrufenden Funktion ist (die dadurch mehrfach durchlaufen, also iteriert, wird) und einer "Rekursion" :)

                Eine Funktion, die sich selbst aufruft, arbeitet rekursiv und nicht iterativ. Bei einer Iteration gehts in definierten Schritten linear durch die Menge, ohne dass sich die Funktion innerhalb der Iteration selbst aufruft.

                Wenn bei einer Iteration eine Zählvariable erforderlich ist, heißt die immer 'i' (ne Scherz).

                Bei einer Iteration kein Zähler erforderlich, es gibt genügend Schleifen-Funktionen in verschiedenen Sprachen die ohne Zähler arbeiten können und als Bedingung z.B. einfach auf ein EOF warten.

                Ich verstehe worauf ihr hinaus wollt, aber bei eine Funktion die sich selbst rekursiv aufruft und dabei eine Datenmenge durchläuft ist ebenso iterativ :)

                function foo($datenmenge, $ebene) {  
                  for($i = 0; $ <= $count($datenmenge); $i++) {  
                    foo($datenmenge, $i)  
                  }  
                }
                

                Ist das jetzt iterativ oder rekursiv?

                1. Hi,

                  Ist das jetzt iterativ oder rekursiv?

                  rekursiv. Wenn's iterativ wird, hast Du in der Schleife eine weitere Schleife.

                  Cheatah

                  --
                  X-Self-Code: sh:( fo:} ch:~ rl:| br:> n4:& ie:% mo:) va:) de:] zu:) fl:{ ss:) ls:~ js:|
                  X-Self-Code-Url: http://emmanuel.dammerer.at/selfcode.html
                  X-Will-Answer-Email: No
                  X-Please-Search-Archive-First: Absolutely Yes
                  1. Ist das jetzt iterativ oder rekursiv?

                    rekursiv. Wenn's iterativ wird, hast Du in der Schleife eine weitere Schleife.

                    Ja - und hier ist mir eben nicht klar, wie man dieses verhalten so programmieren soll, dass man nicht hardcodiert eine Beschränkung der Schleifentiefe einbauen muss.

                    Ich steh am Schlauch.

                    1. Yerf!

                      Ich steh am Schlauch.

                      Ist n gutes Stichwort. Ich würd sowas ähnliches nehmen: eine Liste. Und anstatt einen Selbstaufruf zu machen einfach das Element an das Ende der Liste anhängen. Damit erhöhe ich dann die Anzahl der Iterativen durchläufe und handle alles ab, ohne auf Rekursion zurückzugreifen.

                      Gruß,

                      Harlequin

                      --
                      RIP --- XHTML 2
                      nur die Besten sterben jung
                      1. Hi,

                        Ist n gutes Stichwort. Ich würd sowas ähnliches nehmen: eine Liste. Und anstatt einen Selbstaufruf zu machen einfach das Element an das Ende der Liste anhängen. Damit erhöhe ich dann die Anzahl der Iterativen durchläufe und handle alles ab, ohne auf Rekursion zurückzugreifen.

                        das wäre eine Art State Engine, quasi ein umgekehrter SAX-Parser. Ich glaube gerne, dass es Einsatzgebiete dafür gibt; allerdings möchte ich den erhöhten Aufwand und den Mangel an Struktur gegenüber einer Rekursion erst mal begründet sehen.

                        Cheatah

                        --
                        X-Self-Code: sh:( fo:} ch:~ rl:| br:> n4:& ie:% mo:) va:) de:] zu:) fl:{ ss:) ls:~ js:|
                        X-Self-Code-Url: http://emmanuel.dammerer.at/selfcode.html
                        X-Will-Answer-Email: No
                        X-Please-Search-Archive-First: Absolutely Yes
                        1. Yerf!

                          Es ging ja momentan ums Prinzip. In der Praxis würd ich auch eher eine Rekursion verwenden.

                          Gruß,

                          Harlequin

                          --
                          RIP --- XHTML 2
                          nur die Besten sterben jung
                2. Hallo,

                  function foo($datenmenge, $ebene) {

                  for($i = 0; $ <= $count($datenmenge); $i++) {
                      foo($datenmenge, $i)
                    }
                  }

                    
                  rekursiv.  
                    
                  Du kannst diese jedoch so umschreiben, dass der Selbstaufruf entfällt :-)  
                  Das, was Du hier vorstellst, ist \*keine\* iterative Lösung.  
                    
                  Lies nach bei Sedgewick ([Algorithmen](http://de.wikipedia.org/wiki/Sedgewick)).  
                    
                  Wie Christian Dir sagte, kannst Du das für \*jede\* Rekursion erreichen.  
                  Siehe beispielsweise [Wikipedia, iterative Wege, einen Baum zu durchwandern](http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal). Wenn Du einen Baum iterativ durchwandern kannst, dann kannst Du auch eine verschachtelte Liste iterativ durchwandern ...  
                    
                    
                    
                  Freundliche Grüße  
                  Vinzenz
                  
                  1. Wie Christian Dir sagte, kannst Du das für *jede* Rekursion erreichen.
                    Siehe beispielsweise Wikipedia, iterative Wege, einen Baum zu durchwandern. Wenn Du einen Baum iterativ durchwandern kannst, dann kannst Du auch eine verschachtelte Liste iterativ durchwandern ...

                    Jetzt ist wieder Druck am Schlauch[1] - Danke :)

                    [1] pun not intended

          2. @@Christian Kruse:

            nuqneH

            oder verstehe ich dich jetzt falsch?

            Keine Ahnung. Was hast du denn verstanden?

            Was gibt es da nicht zu verstehen? ;-)

            Qapla'

            --
            Gut sein ist edel. Andere lehren, gut zu sein, ist noch edler. Und einfacher.
            (Mark Twain)
            1. Moin Gunnar,

              oder verstehe ich dich jetzt falsch?

              Keine Ahnung. Was hast du denn verstanden?

              Was gibt es da nicht zu verstehen? ;-)

              Keine Ahnung. Was hast du denn verstanden?

              LG,
               C'Bis zum stack overflow!'K