Rekursiv-Funktion

Moin,

kurze Frage:
Kann man jede rekursive Funktion auch "ausschreiben"?

Ich versuche mir gerade vorzustellen wie folgende Funktion ausgeschieben aussehen müsste:

//Anz. der Blaetter im Baum zaehlen
static int getSize(struct sTree *node)
{
if(node==NULL)
return(0);
else
return(getSize(node->l) +1+ getSize(node->r));
}

Aber irgendwie krieg ich das nicht hin.
Für eine Erklärung wäre ich sehr dankbar!

Martin Richter

Ja kann man. Allerdings bneötigst Du dazu evtl. einen Stackmechanismus.

static int getSize(struct sTree *node) 
{ 
 if(node==NULL) 
   return(0); 

 int count=0;
 std::list<sTree*> nodes;
 nodes.push_back(node);
 do 
 {
    ++count;
    node = nodes.front();
    nodes.pop_front();
    if (node->l)
      nodes.push_back(node->l);
    if (node->r)
      nodes.push_back(node->r);
 }
 while (node.size()!=0)
 return count; 
}

c.rackwitz

linear rekursive funktionen (eine linie von calls) kann man "ausschreiben" (als schleife mit state), mehrfach verzweigende/rekursive (ein baum von calls) nicht.

mit nem stack geht natuerlich alles, aber dann kann man sich das ja gleich schenken und die faehigkeiten der sprache verwenden und rekursive calls benutzen.

Hey, ich danke Euch beiden herzlich!
Jetzt sieht das ganze schon viel einfacher aus!

(muss ich mir gleich irgendwo speichern )

mit nem stack geht natuerlich alles, aber dann kann man sich das ja gleich schenken und die faehigkeiten der sprache verwenden und rekursive calls benutzen.

Wenn sich Aufrufe so sehr verschachteln, dass der Stackspeicher nicht mehr reicht würde das evtl Sinn machen. Stell dir vor, du hast nen Graphen mit 100 Knoten und willst das Problem eines Handlungsreisenden "lösen" (= Bruteforce)

Bashar

pla schrieb:

Wenn sich Aufrufe so sehr verschachteln, dass der Stackspeicher nicht mehr reicht würde das evtl Sinn machen. Stell dir vor, du hast nen Graphen mit 100 Knoten und willst das Problem eines Handlungsreisenden "lösen" (= Bruteforce)

Gut getrollt