C Aufrufbaum für Funktion - Rekursiv

[marivuko]

Ich will einen Aufrufbaum zum Funktionsaufruf A(1,4) skizzieren

Die Funktion:

int A (int m, int n) 
{ 
 int x,y; 
 if ( m == 0 ) return 2 * n; 
 else if ( m >= 1 && n == 0) return 0; 
 else if ( m >= 1 && n == 1) return 2; 
 else { 
x = A(m,n-1); 
y = A(m-1,x); 
return y; 
 } 
}

ich habe es versucht (siehe Anhang/Bild) nur leider bleib ich leider bei der Zeile y=A(m-1,x) hängen, liegt dran, dass ich nicht weiß wie ich auf das x kommen soll

 

[[GP] mino]

optimiere den code doch einfach zu:

std::int32_t A( const std::int32_t m, const std::int32_t n )
{
    if( (m < 0) || (n <= 0) )
    {
       return -1;  // fehler, negative oder null parameter: fuck you!
    }

    if ( !m )  // m == 0
    {
        return 2 * n;  // n << 1; wird vom compiler automatisch ersetzt
    }
    else if ( n == 1 )
    {
        return 2;
    }
    else
    {
/*
beachte, dass jeder rekursive aufruf den stack aufpumpt. in imperativen programmiersprachen
ist diese zeile die goldgrube für exploits - sprich kontrollierter stackoverflow. wenn du unbedingt eine funktion beliebig oft rekursiv aufrufen willst, nutze funktionale programmierung oder forme diesen ausdruck in eine schleife um. alternativ  kannst auch die lambda ausdrücke aus dem modernen C++ nutzen.
*/
        return A( m-1, A( m, n-1 ) );
    }
}

wie auch immer, dein "x" ist weg zeichne mal dein bäumchen nochmal und du wirst den rest von alleine erkennen.

 

[hroessler]

Hallo,
das magic Word heißt "Endrekursion". Das bedeutet, du Programmierst deine Funktion wie eine Rekursion, ausgeführt wird es allerdings wie wenn es als Schleife programmiert wäre.

Das ist eine Compileroptimierung, sprich der Compiler muss die Optimierung kennen und auch während des kompilieren durchführen. Das ist die eleganteste Möglichkeit und verbindet das beste aus beiden Welten.

Greetz
​hroessler

 

[asdfman]

Da bin ich aber mal gespannt, wie ihr zwei Spezialexperten die Ackermannfunktion iterativ formulieren wollt (ja, mit TCO wird ein iterativer Prozess erzeugt).

Und auch in funktionalen Programmiersprachen ist für einen rekursiven Prozess ein Stack nötig. Wie soll das denn bitte sonst funktionieren?