[Anfänger] Rekursion (StackOverflow)

miniC# · Beiträge: 75 Wiin XP Home C# VS Express 2008

Hallo,

ich bin zu bleed. diesen grundlegende einsicht ist im moment mal wieder hochaktuell bei mir. ich habe den code ein wenig gekürzt, ich hoffe ich habe nichts elementares gelöscht.

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:

// --- Snipp --- 
        private Random _r;
        private int maxdeepth // ist 5;
        private int curdeepth // ist zu beginn 0;
// --- Snipp --- 

        private List<CNode> CreateTree(int mincount, int maxcount)
        {
            List<CNode> output = new List<CNode>();
            int count = _r.Next(mincount, maxcount);

            for (int i = 0; i < count; i++)
            {
                if (_r.Next(2) == 1)
                    output.Add(new CStringNode("Node " + i + " [" + curdeepth + "]", _r));
                else
                    output.Add(new CDoubleNode("Node " + i + " [" + curdeepth + "]", _r));

                curdeepth++;
                if (curdeepth <= maxdeepth)
                    output[output.Count - 1]._subnodes = CreateTree(mincount, maxcount);
                curdeepth = 0;
            }
            return output;
        }

        public abstract class CNode
        {
            internal string _name;
            internal List<CNode> _subnodes;
            //...
        }

die methode soll eine baumstruktur erstellen nach folgendem schema :

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

Node 0 [0] - 97,532                              // Node Nummer [Tiefe] - Nodeinhalt
  Node 0 [1] - bcdb
  Node 1 [2] - ddbd

Node 1 [0] - bada
  Node 0 [1] - bcbc
    Node 0 [2] - 64,879
Node 2 [0] - 77,863
  Node 0 [1] - 9,925
Node 3 [0] - abbd

sie gibt produziert aber stackoverflows, erzeugt bäume mit mehr zweigen als mit maxcount angegeben und gibt soetwas aus :

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

Node 0 [0] - 97,532
  Node 0 [1] - bcdb
    Node 0 [2] - ddbd

Node 1 [0] - bada
  Node 0 [1] - bcbc
    Node 0 [2] - 64,879
Node 1 [0] - baba
  Node 0 [1] - 19,019
Node 1 [0] - 77,863
  Node 0 [1] - 9,925
Node 1 [0] - abbd

soweit, dass es ein problem mit der schleife gibt bin ich auch, ich verstehe jeodch nicht ganz den grund. kurz kommentierter pseudocode.

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

        public void ErzeugeNodes()
        {
            for (int i = 0; i < count; i++)          // hier beginnt die schleife
            {
                ErzeugeNode();                       // ein node wird hinzugefügt
                curdeepth++;                         // die knotentiefe wird um eins hochgesetzt
                if ((curdeepth <= maxdeepth))
                    Node.Subnodes = ErzeugeNodes();  // wenn die knotentiefe noch nicht max ist, dann beginnt die rekursion für die subnodes
                curdeepth = 0;                       // curdeepth > maxdeepth, die rekursion sollte sich hier aufdröseln, deshalb wird die 
                                                     // tiefe zurückgesetzt, da ein neuer hauptknoten entsteht 
            }
        }

wieso 'vergisst' c# scheibar die variable i aus den durch die rekursion unterbrochenen schleifen ? ich beende meine wirren kommentare ersteinmal hier und hoffe auf eure hilfe

gruß,
miniC#

_________________
Zitat MDSN : " ... C# (gesprochen: "si scharp") "

jaenicke · Verfasst: Di 13.01.09 14:26

Ich hab jetzt leider keine Zeit mir das genauer anzusehen. Ein Stackoverflow ist z.B. das Symptom einer nicht abgebrochenen Rekursion, die ich in deinem Fall aber erstmal nicht sehe.

Ich fände es einfacher, wenn du ein lauffähiges Beispiel anhängen könntest, wenn das nicht zu viel Aufwand wäre. Dann könnte ich sicher schneller sehen was schief geht. (Ich würde es mir nachher nochmal ansehen, wenn ich wieder da bin.)

Aber vielleicht sieht ja jemand auch direkt was passiert. ;-)

// EDIT:

miniC# hat folgendes geschrieben :

wieso 'vergisst' c# scheibar die variable i aus den durch die rekursion unterbrochenen schleifen ?

i ist eine lokale Variable, die gilt nicht in der neu aufgerufenen Methode (sondern nur in der for-Schleife der aktuellen Methode), außerdem wird sie dort ja auch bei "int i = 0" nicht nur neu erzeugt sondern auch auf 0 gesetzt.

Kha · Verfasst: Di 13.01.09 14:36

miniC# hat folgendes geschrieben :

die methode soll eine baumstruktur erstellen nach folgendem schema :

Könntest du das noch ein bisschen näher beschreiben? Der Fehler liegt wohl am curdeepth = 0 statt curDepth-- (mit curdeepth als Parameter würdest du dir das Leben einfacher machen), aber solange ich nicht weiß, was die Methode machen soll, kann ich dazu nicht mehr sagen.

_________________
>λ=

miniC# · Beiträge: 75 Wiin XP Home C# VS Express 2008

danke für eure hilfe. ich habe das ganze umgeschrieben. und nun funktioniert es ganz gut (für meine bescheidnen verhältnisse). kritik sofern vorhanden, ist natürlich erwüscht. muss immer fleissig lernen. ich habe das ganze von der CNode klasse her aufgerollt, jetzt kennt jeder node sein parent, bzw der verkettungslogik ist in CNode selbst festgelegt. ist wahrscheinlich wahnsinnig ineffizient, aber nuja irgendwie muss ich ja mein rechner runterwirtschaften

. die unterschiedlichen nodes habe ich zwecks übersicht herrausgenommen.

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:

    public class CTree
    {
        public CTree(int maxdeepth, int min, int max)
        {
            _r = new Random();
            _tree = new List<CNode>();
            _result = new StringBuilder();
            _tree.Add(new CDoubleNode(true));
            _tree[0]._subnodes = CreateTree(min, max, maxdeepth, _tree[0]);
            Render(_tree);
        }
        public abstract class CNode
        {
            internal string _key;
            internal string _whitespace;
            internal int _z;
            internal CNode _parent;
            internal List<CNode> _subnodes;
        }
        public class CDoubleNode : CNode
        {
            public CDoubleNode(int count, CNode parent)
            {
                _key = parent._key + "." + count.ToString();
                _whitespace = parent._whitespace + "   ";
                _z = parent._z + 1;
                _parent = parent;
                _subnodes = new List<CNode>();

            }
            public CDoubleNode(bool root)
            {
                _key = "Node 0";
                _whitespace = "";
                _z = 0;
                _parent = null;
                _subnodes = new List<CNode>();
            }
            public override string ToString()
            {
                if (_parent != null)
                {
                    return _whitespace + _key;
                }
                else
                    return "Root";
            }
        }

        private Random _r;
        private List<CNode> _tree;
        private StringBuilder _result;
        public string Result
        { get { return _result.ToString(); } }

        private List<CNode> CreateTree(int min, int max, int maxdeep, CNode parent)
        {
            List<CNode> output = new List<CNode>();
            int steps = _r.Next(min, max + 1);
            int deepth = parent._z + 1;

            for (int i = 0; i < steps; i++)
            {
                output.Add(new CDoubleNode(i, parent));
                if (deepth <= maxdeep)
                    output[i]._subnodes = CreateTree(min, max, maxdeep, output[i]);
            }
            return output;
        }
        private void Render(List<CNode> tree)
        {
            foreach (CNode n in tree)
            {
                _result.AppendLine(n.ToString());
                if (n._subnodes != null)
                    Render(n._subnodes);
            }
        }
    }

Kha hat folgendes geschrieben :

miniC# hat folgendes geschrieben :

die methode soll eine baumstruktur erstellen nach folgendem schema :

Könntest du das noch ein bisschen näher beschreiben? Der Fehler liegt wohl am curdeepth = 0 statt curDepth-- (mit curdeepth als Parameter würdest du dir das Leben einfacher machen), aber solange ich nicht weiß, was die Methode machen soll, kann ich dazu nicht mehr sagen.

hm, jetzt wo das erwähnst mit curdeepth--, klingt erschreckend logisch, ich werde das gleich mal ausprobieren

was du allerdings mit "mit curdeepth als Parameter würdest du dir das Leben einfacher machen" meinst verstehe ich leider nicht ganz. zu deiner frage bezüglich des zweckes der methode : sie soll einen zufällige baumstruktur aufbauen, aus den parametern maxschritttiefe und min/max anzahl unterknoten pro überknoten. wesentlich genaueres fällt mir leider nicht ein.

das produziert der code momentan (Werte - MaxTiefe 2, Min 1, Max 3):

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

Root
   Node 0.0
      Node 0.0.0
         Node 0.0.0.0
         Node 0.0.0.1
   Node 0.1
      Node 0.1.0
         Node 0.1.0.0
         Node 0.1.0.1
         Node 0.1.0.2
      Node 0.1.1
         Node 0.1.1.0
   Node 0.2
      Node 0.2.0
         Node 0.2.0.0
         Node 0.2.0.1
         Node 0.2.0.2
      Node 0.2.1
         Node 0.2.1.0
         Node 0.2.1.1
         Node 0.2.1.2
      Node 0.2.2
         Node 0.2.2.0
         Node 0.2.2.1
         Node 0.2.2.2

_________________
Zitat MDSN : " ... C# (gesprochen: "si scharp") "

miniC# · Beiträge: 75 Wiin XP Home C# VS Express 2008

jaenicke hat folgendes geschrieben :

// EDIT:

miniC# hat folgendes geschrieben :

wieso 'vergisst' c# scheibar die variable i aus den durch die rekursion unterbrochenen schleifen ?

i ist eine lokale Variable, die gilt nicht in der neu aufgerufenen Methode (sondern nur in der for-Schleife der aktuellen Methode), außerdem wird sie dort ja auch bei "int i = 0" nicht nur neu erzeugt sondern auch auf 0 gesetzt.

das ist / war mir schon klar. das problem war jedoch, dass die methode folgendes ausgab.

markieren

Quelltext

1:
2:
3:
4:
5:
6:

node 0
   node 0
node 1
   node 0
node 1
   node 0

bis zeile 4 ist der baum korrekt, aber in zeile 5 müsste es dann node 2 heissen. oder anders formuliert der obige block wird durch vier schleifen erzeugt. eine für die nodes oberste ebene und drei für die drei subnodes. dass bei den subnodes eine neue schleife beginnt und damit auch ein neues i, ist gewollt. unverständlich ist mir jedoch, warum in zeile 5 i=1 ist, da bereits in zeile 3 i=1 war (zeile 4 ist dann die ausgelöste rekursion und es ensteht ein neues i, welches wie gewünscht 0 ist).

hier nochmal der pseudocode, auf den ich mich beziehe :

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

        public void AddNodes(List<Nodes> liste, int count)
        {
            for (int i = 0; i < count; i++)
            {
                list.AddNode();
                curdeepth++;
                if ((curdeepth <= maxdeepth))
                    AddNodes(list[i].Subnodes, count); 
                curdeepth = 0;
            }
        }

wahrscheinlich müsste die methode so aussehen, wie user profile icon

Kha es mir erklärt hat.

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

        public void AddNodes(List<Nodes> liste, int count, int deepth)
        {
            for (int i = 0; i < count; i++)
            {
                list.AddNode();
                if ((deepth+1 <= maxdeepth))
                    AddNodes(list[i].Subnodes, count, deepth+1); 
            }
        }

btw : dabei wird mir grade klar, was du mit parameter gemeint hast user profile icon

Kha

.

_________________
Zitat MDSN : " ... C# (gesprochen: "si scharp") "

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme