Alternativen zu Rekursiven Funktionsaufrufen



  • Hallo zusammen
    Dies ist eine Frage, die mich schon seit längerem sehr interessiert. Gibts sowas wie rekursive Schleifen ?

    Lg Ishildur



  • Wenn du Schleifen verwendest, bist du idR nicht rekursiv 😉 (Aber natürlich ist es auch möglich, daß eine Funktion Schleifen und rekursive Aufrufe miteinander kombiniert)



  • Ishildur schrieb:

    Dies ist eine Frage, die mich schon seit längerem sehr interessiert. Gibts sowas wie rekursive Schleifen ?

    Mal davon abgesehen, dass das vom Konzept her Quatsch ist: Was versprichst Du Dir davon (also, Vorteile im Vergleich zu rekursiven Funktionen)?



  • Einfache "tail recursion" lässt sich auf ne Schleife umbauen. Wenn 2 rekursive Aufrufe benötigt werden (z.B. Quicksort) kann einer durch ne Schleife ersetzt werden, der 2. muss rekursiv bleiben.

    http://en.wikipedia.org/wiki/Tail_recursion



  • hustbaer schrieb:

    Einfache "tail recursion" lässt sich auf ne Schleife umbauen.

    Eben, und daher sollte man das dem Compiler überlassen (und hoffen, dass er das tut) und sich auf lesbaren Code konzentrieren. Tail recursion ist ja eigentlich etwas, das ein moderner Compiler beherrschen sollte.



  • Ich bin mir nicht sicher, ob er das bei sowas wie nem Quicksort sieht. In der STL-Implementierung die ich nutze ist die Schleife von Hand hingeschrieben.



  • @Konrad Rudolf

    Was versprichst Du Dir davon (also, Vorteile im Vergleich zu rekursiven Funktionen)

    Naja, von der Funktionalität her eigentlich gar nichts, ich finde es nur nicht schön:

    1. Ich habe einen kurzen Codeblock innerhalb einer Funktion. Nun muss ich noch eine zusätzliche Hilfsfunktion machen, weil ich bspw. einen Baum durchlaufen will...

    2. In API aufrufen finde ich es auch nicht so toll, wenn ich bspw. eine Methode ShowTree habe, dann muss ich dieser ja Parameter übergeben ala ShowTree(Leaf leaf) und der Benutzer muss dann ShowTree(0x00) übergeben, weil Sie aus Sicht des Benutzers der API eigentlich gar keine Parameter benötigt, sondern eben nur dann, wenn diese von sich selbst rekursiv aufgerufen wird.

    Lg Ishildur

    P.S.
    Ist natürlich nicht dringend, war mehr so ein Gedanke, obs da möglicherweise auch andere Ansätze gibt, von denen mir bisher nichts zu Ohren gekommen ist...



  • Geht das auch nochmal auf Deutsch? Was genau hast du vor?

    Ishildur schrieb:

    2. In API aufrufen finde ich es auch nicht so toll, wenn ich bspw. eine Methode ShowTree habe, dann muss ich dieser ja Parameter übergeben ala ShowTree(Leaf leaf) und der Benutzer muss dann ShowTree(0x00) übergeben, weil Sie aus Sicht des Benutzers der API eigentlich gar keine Parameter benötigt, sondern eben nur dann, wenn diese von sich selbst rekursiv aufgerufen wird.

    Lg Ishildur

    P.S.
    Ist natürlich nicht dringend, war mehr so ein Gedanke, obs da möglicherweise auch andere Ansätze gibt, von denen mir bisher nichts zu Ohren gekommen ist...

    Du könntest z.B. Default-Parameter verwenden ala ShowTree(Leaf l = 0x00); . Oder du versteckst die rekursive Funktion hinter einem Wrapper ShowMyTree(void . Oder...



  • @CStoll

    Geht das auch nochmal auf Deutsch? Was genau hast du vor?

    Möchte einen Baum durchlaufen, ohne dafür wieder extra eine Hilfsfunktion hinkrakeln zu müssen. Abgesehen davon habe ich einen sehr hohen Verbrauch an Stackspeicher, da der Baum sehr gross ist.

    Du könntest z.B. Default-Parameter verwenden

    Das habe ich bisher genauso gemacht, aber ist natürlich etwas umständlich. 😉



  • CStoll schrieb:

    Oder du versteckst die rekursive Funktion hinter einem Wrapper ShowMyTree(void . Oder...

    Meinst Du sowas? 😉

    int fibonacci_number(int n)
    {
        struct rec_t {
            std::pair<int, int> accu;
            rec_t() : accu(0, 1) { }
    
            int operator ()(int n) {
                if (--n == 0) return accu.second;
                accu = std::make_pair(accu.second, accu.first + accu.second);
                return (*this)(n);
            }
        } rec;
        return rec(n);
    }
    


  • @hustbaer

    list *f(list *input){
      list *head;
    
      if(input == NULL) {
        head = NULL;
      } else {
        head = malloc(sizeof(list));
        head->value = input->value;
        head->next = f(input->next);
      }
    
      return head;
    }
    

    Das ist jetzt ein Witz oder? 😉

    Wie ich eine Liste iterativ durchlaufe ist mir schon klar! 🤡



  • Die Rekursion kannst du auch aufbohren und von Hand nachprogrammieren:

    void print(Leaf l)
    {
      queue<Leaf> rest;//oder stack<Leaf>
      rest.push(l);
    
      while(!rest.empty()
      {
        Leaf& p=rest.top();
        if(p.left) rest.push(*p.left);
        if(p.right)rest.push(*p.right);
        cout<<p.data;
        rest.pop();
      }
    }
    

    (aber ob das günstiger für den Speicherverbrauch ist??)



  • Ishildur schrieb:

    @hustbaer
    Wie ich eine Liste iterativ durchlaufe ist mir schon klar! 🤡

    Offensichtlich nicht. Das ist nämlich rekursiv, nicht iterativ.



  • @hustbaer
    Ja, das Beispiel im Code ist natürlich rekursiv. Was ich sagen will, ist, dass ich weis, wie ich im Allgemeinen resp. auch eben diesen Code iterativ implementieren kann.
    Was aber eben nicht so einfach resp. unmöglich? ist, ist das iterative durchlaufen eines Baumes.

    Sollte nicht ein Angriff sein! Take it easy! 🙂



  • Ishildur, wenn du keine "Anfänger-Links" haben willst solltest du vielleicht lernen Fragen so zu formulieren dass man dich nicht für einen kompletten noob halten muss.

    Und wenn du auch nur ein bisschen Ahnung hast, wieso stellst du diese Frage jetzt bitte überhaupt? Wenn du Rekursion verstehst, dann musst du auch wissen was damit geht und was nicht, bzw. wie man Rekursion "umbauen" kann.

    Klar kannst du einen Baum ohne Rekursion durchlaufen, macht bloss meistens keinen Sinn, und ist im Endeffekt auch nix anderes als mit Rekursion, bloss eben anders programmiert (expliziter Stack statt Rekursion halt).

    Und mich schief von hinten anzulabern vonwegen "Das ist jetzt ein Witz oder?" IST ein Angriff ganz egal was du sonst noch dazuschreibst. Ich kann nicht wissen was du weisst und was nicht, daher gehe ich nachdem was du schreibst, und das Kopfposting war auf dem Level eine 12 Jährigen der mit 11 mal von weitem einen Computer gesehen hat. Von daher...

    1. Ich habe einen kurzen Codeblock innerhalb einer Funktion. Nun muss ich noch eine zusätzliche Hilfsfunktion machen, weil ich bspw. einen Baum durchlaufen will...

    Lol.
    Ja, ganz schlimm, ich ärger mich auch jedes mal wenn ich noch eine Funktion brauche.
    Siehs mal andersrum: es ist sogar BESSER wenn du das in 2 Funktionen zerlegst, da dann die 2 Teilaufgaben "Baum durchlaufen" und "Was auch immer machen" getrennt sind. Das ist gut. Aber das weisst du natürlich alles schon, sorry.

    2. In API aufrufen finde ich es auch nicht so toll, wenn ich bspw. eine Methode ShowTree habe, dann muss ich dieser ja Parameter übergeben ala ShowTree(Leaf leaf) und der Benutzer muss dann ShowTree(0x00) übergeben, weil Sie aus Sicht des Benutzers der API eigentlich gar keine Parameter benötigt, sondern eben nur dann, wenn diese von sich selbst rekursiv aufgerufen wird.

    // ganz toller Tip: du kannst hier auch "private" nehmen ;) ;) ;)
    static void ShowTree(Tree* t, Node* n)
    {
        //...
    }
    
    void Tree::ShowTree()
    {
        ShowTree(this, &m_rootNode);
    }
    

    Das war jetzt mächtig schwer, gebe ich zu, ja.



  • Das lasse ich mir nicht bieten, Sie Cretain! Ich sehe Sie draussen, zum virtuellen Pistolenduell! 😉



  • Ishildur schrieb:

    Was aber eben nicht so einfach resp. unmöglich? ist, ist das iterative durchlaufen eines Baumes.

    Guck mal da oben - es IST möglich, einen Baum iterativ zu durchlaufen (und wenn nur, indem du die rekursiven Aufrufe in der Funktion kapselst). Aber imho ist es den Aufwand nicht wert, so etwas umgehen zu wollen.



  • @CStoll
    Ja, da bin ich einer Meinung mit dir! Ich habe mir das schon gedacht, aber man kann ja nie wissen! 😉



  • Ishildur schrieb:

    Das lasse ich mir nicht bieten, Sie Cretain! Ich sehe Sie draussen, zum virtuellen Pistolenduell!

    Ok, ich geb W/O, du bist der bessere Fechter, du hast mehr Humor als ich. 👍 🙂

    Aber... hab ich nicht Wahl der Waffen? Obwohl egal, ich mag eh keine Säbel/Messer/..., Pistolen ist also OK.

    (BTW: mein erstes Posting war weder als Scherz NOCH als "Spitze" oder Beleidigung gemeint, kann ja nicht wissen was du weisst und was nicht...)


Log in to reply