Diese Rekursion...



  • Moin 🙂
    hab ein glaub ich für euch denkbar kleines problem. Und zwar dieser code:

    int funk(int n)
    {
        if(n > 7) return 1;
    
        return funk(n+1)+funk(n+2);
    }
    int main()
    {
        printf("%d ", funk(3));
        return 0;
    }
    

    Kann mir mal jemand erklären wieso hier -13- herauskommt. Ich stelle und zeichne mir so eine Art binären Baum auf nur kommt bei mir immer eine viel größere Zahl heraus. Wäre wirklich dankbar für eine Erklärung.
    Grüße



  • Ich gehe mal vom Rekursionsabbruch aus los:
    func(8) = func(9) = 1
    func(7) = func(8)+func(9) = 2
    func(6) = func(7)+func(8) = 3
    func(5) = func(6)+func(7) = 5

    Das ganze hat was von der Fibonacci-Folge, nur daß die Rekursion in die andere Richtung geht.



  • Das was der Computer da rechnet wird wohl stimmen. Demnach ist das Ergebnis von 13 korrekt.

    Ich habs trotzdem auch mal aufgemalt und durchgerechnet:
    http://www.imgupload.org/images/823_baum.png

    Müsste hinhauen, denn ich komme auch auf 13.



  • Danke für deine Skizze so hatte ich es ca auch nur kann ich keine 13 herauslesen, worauf beziehen die sich bzw. wie seh ich hier 13 heraus? Oder anders gesagt wenn ich die Lösung nicht kenne wie komme ich auf 13?



  • ich habe angefangen aufzuschreiben:

    3 + 1 und 3 + 2

    dann habe ich zunächst mit 3 + 1 weitergemacht und die Blätter 4 + 1 und 4 + 2 angehangen. Und auch hier das gleiche wiederholt.

    Irgendwann kommt man dann zu einem Punkt, wo das Ergebnis größer als 7 ist und braucht keine Blätter mehr einzeichnen.

    Wenn man das alles gemacht hat, dann fängt man unten an und schreibt das Ergebnis auf. Bei 7 + 1 ist das 1, da hier die Abbruchbedingung erfüllt ist und 1 zurückgegeben wird. Ebenso bei 7 + 2. Beides wird addiert, da ja:

    funk(n+1)+funk(n+2)
    

    Also ergibt sich als Ergebnis für 6 + 1 die 2. Bei 6 + 2 ist wieder die Abbruchbedingung erfüllt, also ergibt sich hier nur 1. Addiert man beides wieder zusammen hat man 3 und das ist das Ergebnis von 5 + 1... Und so geht das immer weiter und am Ende bleibt eben nur noch 8 und 5 über, was zusammen das Endergebnis 13 ergibt. Leider kann ich nicht so gut mit der Maus zeichnen, sonst wäre der Baum etwas leserlicher.



  • wow nein das ist super also bezieht sich das ganze im grunde genommen auf "die Anzahl der Funktionsaufrufe" bzw. weil ja immer 1 zurückgeben wird. Alle zusammenzählen wie auf deiner Skizze schön ersichtlich ist und das sind dann 13. Super jetzt hab ichs. Fettes DANKE !!



  • Dave01 schrieb:

    wow nein das ist super also bezieht sich das ganze im grunde genommen auf "die Anzahl der Funktionsaufrufe" bzw. weil ja immer 1 zurückgeben wird. Alle zusammenzählen wie auf deiner Skizze schön ersichtlich ist und das sind dann 13. Super jetzt hab ichs. Fettes DANKE !!

    Die Anzahl der Funktionsaufrufe ist aber nicht 13. Ich habe noch mal versucht den Baum besser darzustellen:
    http://www.imgupload.org/images/1_baum2.png

    Die rote Zahl bedeutet, dass das Ergebnis dieses Blattes 1 ist, da die Abbruchbedingung erreicht wurde. Und da gibt die Funktion laut des Codes ja eben 1 zurück. Und dann hangelt man sich von da an rückwärts hoch und muss eben noch die Summe bilden, da der Code ja sagt: return funk(n+1)+funk(n+2);



  • Oh, da ist ein Fehler. Der Strich vom grünen ganz oben in der Mitte müsste natürlich bei der 5 enden.



  • Danke dir, so eine kleine Grafik hilft schon um einiges weiter um es verständlich nachvollziehen zu können und auf die richtige Lösung zu kommen



  • Als weitere Übung kannst du ja mal testen, ob du es nun schaffst für diese Funktion (für n = 3) selber einen Baum zu erstellen:

    int funk(int n)
    {
        if(n > 6) return 2;
    
        return funk(n+2) + funk(n+3) - 1;
    }
    

    Da die Abbruchbedingung und die Berechnung anders sind muss man da aufpassen, das man sich nicht vertut. 😉

    Der entstehende Baum ist übrigens vergleichsweise klein. Solltest du dann auch merken warum der so klein ist. 🙂

    Lösung: http://www.imgupload.org/images/574_baum3.png



  • Nun möchte ich etwas weitergehen und muss ein mein Programm "Palindrome" auf eine Rekursive Art umschreiben.(oT12TO, gilt als Palindrome) Nach langen herumprobieren komme ich leider auf keine Lösung. Ich hoffe ihr könnt mir weiterhelfen.

    So sieht das Grundkonzept aus:

    #include <stdio.h>
    #include <stdlib.h>
    
    /*Filtert alle Sonderzeichen raus*/
    void filter(char *s)
    {
        int i=0;
        int j=0;
        while(s[i] != '\0')
        {
            if((s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= 'a' && s[i] <= 'z') )
            {
                s[j]=s[i];
    
                j++;
            }
            i++;
        }s[j]='\0';
    }
    /*Macht kleinbuchstaben zu großbuchstaben*/
    void toUpper(char *s)
    {
        int i=0;
    
        while(s[i] != '\0')
        {
            if(s[i] >= 'a' && s[i] <= 'z')
            {
                s[i]-=32;
            }
            i++;
        }
    }
    
    int ja_nein(int anzahl, char *s, int temp) /*überprüfe auf Palindrome*/
    {
        int i,j;
    
        for(i=0, j=anzahl; i < anzahl+1, j >= 0 ; i++, j--) /*i------><------j*/
        {
            if(s[i] != s[j])  
            {
                temp++;
            }
        }
        return temp;
    }
    
    int main()
    {
        char *ptr;
        int i,j=0;
        int a=0;
        char buffer[100];
        int tmp=0;
        int uebernahme;
    
        printf("\t\t\t\t=================\n");
        printf("\t\t\t\tPointerPalindrome\n");
        printf("\t\t\t\t=================\n\n\n");
    
        ptr=buffer;
    
        printf("Eingabe: ");
        gets(ptr);
    
        filter(ptr);
    
        toUpper(ptr);
    
        a=strlen(ptr)-1;
    
        uebernahme=ja_nein(a, ptr, tmp);
    
        printf("\n");
    
        if(uebernahme == 0)
        {
            printf("Your entered string is a PALINDROME!\n");
        }
        else
        {
            printf("Your entered string is - NOT - a PALINDROME!\n");
        }
    
        return 0;
    }
    


  • Ich geb dir mal nen Tipp, die ToUpper Funktion würde so aussehen:

    void ToUpper(char *s)
    {
      if (*s)
      {
        if(*s >= 'a' && *s <= 'z')
        {
          *s -= 32;
        }
        ToUpper(s + 1);
      }
    }
    

    Wobei ich Rekursion in den meisten Fällen offen gesagt recht hässlich finde, wie auch hier. Warum nicht einfach so?

    void ToUpper(char *s)
    {
      while (*s)
      {
        if (*s >= 'a' && *s <= 'z')
          *s -= 32;
        ++s;
      }
    }
    

    Edit: Und weiter: die "Laufvariablen" übergibst du einfach der Rekursiven Funktion. Die Funktionssignatur könnte dann zB. so aussehen:

    int IsPalin(char *s, int i, int j)
    


  • Was spricht eigentlich dagegen, die Funktionen der <ctype.h> einzusetzen? (toupper() und isalpha()/isalnum())

    Ansonstens zu deiner Funktion ja_nein(): (ich nehme mal an, die willst du rekursiv verwenden)
    Was für einen Sinn hat denn der Parameter temp, den du dort übergibst? Das könnte genausogut eine lokale Variable sein.
    Und die rekursive Definition eines Palindroms lautet in etwa: Ein Palindrom ist ein leeres Wort, ein einbuchstabiges Wort oder die Verkettung x p x für ein Palindrom p und einen Buchstaben x. In Code:

    bool palindrom(char* wort, int len)
    {
      if(len<=1)
        return true;
      else
        return wort[0]==wort[len-1] && palindrom(wort+1,len-2);
    }
    

    Allerdings gehen die meisten Menschen eher den umgekehrten Weg und versuchen aus einem rekursiven Programm ein iteratives zu bauen.



  • CStoll schrieb:

    Was spricht eigentlich dagegen, die Funktionen der <ctype.h> einzusetzen? (toupper() und isalpha()/isalnum())

    Eigentlich nichts, aber vielleicht der Lerneffekt 😃

    CStoll schrieb:

    bool palindrom(char* wort, int len)
    {
      if(len<=1)
        return true;
      else
        return wort[0]==wort[len-1] && palindrom(wort+1,len-2);
    }
    

    Hm.. schöne Lösung, aber seit wann kennt C denn bool und true? 😃



  • cooky451 schrieb:

    Hm.. schöne Lösung, aber seit wann kennt C denn bool und true? 😃

    Da habe ich den Überblick verloren, ich dächte einer der neueren C-Standards hätte es eingeführt. Zur Not kannst du aber auch int und 1 dort verwenden, wenn dir das lieber ist 😉



  • VERDAMMT, hab ich jetzt mal deine ToUpper und die ispalindrome eingebaut und das funktioniert ja wie ne eins.. nur leider fehlt mir einfach die Übung um auf das draufzukommen 😞



  • Die Funktion ToUpper von euch habe ich mittlerweile verstanden, danke! bei der ispalindrome bin ich etwas verwirrt. Ich möchte ja dazulernen und habe deshalb mal meine etwas von euch abgeänderte Funktion geschrieben, so schaut es für mich als "leihe" sehr verständlicher aus. Bei einem Palindrome wird mir 1 ausgegeben, bei keinem Palindrome wird glaub ich eine Adresse ausgegeben auf jeden Fall mehrere Zahlen. Soll das so sein 😕

    int ispalr(char *s, int i, int len) /*Bsp für Aufruf:printf("%d", ispalr("OTTO", 0, 3));*/
    {
        if(len<=1)
        {
            return 1;
        }
        if(s[i] == s[len])
        {
            return ispalr(s, i+1, len-1);
        }
    }
    

    EDIT: Fehler gefunden: kann es aber so als Rekursiv verwendet werden.. sieht doch etwas anders aus als eure Varianten..?

    int ispal(char *s, int i, int len)
    {
        if(len<=1)
        {
            return 1;
        }
        else
        {
            if(s[i] == s[len])
            {
               return ispal(s, i+1, len-1);
            }
            else
            {
                return 0;
            }
        }
    }
    


  • Dave01 schrieb:

    Die Funktion ToUpper von euch habe ich mittlerweile verstanden, danke! bei der ispalindrome bin ich etwas verwirrt. Ich möchte ja dazulernen und habe deshalb mal meine etwas von euch abgeänderte Funktion geschrieben, so schaut es für mich als "leihe" sehr verständlicher aus. Bei einem Palindrome wird mir 1 ausgegeben, bei keinem Palindrome wird glaub ich eine Adresse ausgegeben auf jeden Fall mehrere Zahlen. Soll das so sein 😕

    Wenn die Eingabe kein Palindrom ist, werden beide if()-Anweisungen übersprungen und du verlässt die Funktion ohne einen Rückgabewert anzugeben. Das nennt sich dann "undefiniertes Verhalten" und sollte einem guten Compiler zumindest eine Warnung wert sein.

    EDIT: Fehler gefunden: kann es aber so als Rekursiv verwendet werden.. sieht doch etwas anders aus als eure Varianten..?

    int ispal(char *s, int i, int len)
    {
        if(len<=1)
        {
            return 1;
        }
        else
        {
            if(s[i] == s[len])
            {
               return ispal(s, i+1, len-1);
            }
            else
            {
                return 0;
            }
        }
    }
    

    Das ist nur optisch 😃 ich hatte anstelle der inneren if()-Anweisung einen Ausdruck gebildet, der das selbe aussagt (der nutzt die Tatsache, daß die Vergleichsoperatoren auch 0 bzw. 1 liefern, sowie die Kurzschlußauswertung von &&). Allerdings haben deine Parameter eine andere Bedeutung als bei meinem Beispiel und da würde als Rekursionsabbruch schon if(len-i<1) ausreichen.



  • Ok verstehe, ich habe die Funktion nun probiert graphisch darzustellen. Ich bin der Meinung das sollte so ungefähr stimmen.
    http://img4web.com/view/2QM6X4
    Wenn man sich den Aufwand anschaut, dann entspricht das doch ungefähr len/2 wenn ich das richtig verstanden habe.
    Zu guter letzt hätte wüsste ich gern, ob man so eine Funktion wie bei mir void Filter(), welche jedes Sonderzeichen rauslöscht, auch als rekursive Funktion darstellen kann bzw. ob das überhaupt geht weil ich ja ansich den string komplett verändern muss?



  • In dem Fall hast du in der Funktion ja nur einen rekursiven Aufruf, da wird aus dem Aufrufbaum eine lineare Liste. Was genau dein Bild darstellen könnte, bin ich mir nicht sicher.

    Die Filter-Funktion lässt sich sicher auch rekursiv definieren, aber ob das soviel Sinn macht, lasse ich mal im Raum stehen. Du benötigst dafür zwei Zeiger (quelle und ziel - am Anfang beide auf den Anfang des Strings gezielt) als Parameter und rufst die Funktion dann mit passend verschobenen Zeigern wieder auf.


Log in to reply