Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

Addieren auf Rückgabewert einer rekursiven Methode führt zur Erhöhung des Wert um ein Mehrfaches
inflames2k
myCSharp.de - Experte

Avatar #AARsmmPEUMee0tQa2JoB.png


Dabei seit:
Beiträge: 2358

Themenstarter:

Addieren auf Rückgabewert einer rekursiven Methode führt zur Erhöhung des Wert um ein Mehrfaches

beantworten | zitieren | melden

Hallo,

ich habe mal eine Frage, zu einem Problem das uns letzte Woche aufgefallen ist. In einem Programm, das Werte in einem Baum speichert, zählen wir einen eindeutigen Index zur Identifikation der Einträge. Dazu wird der rekursiv Baum durchlaufen und der größte Index ermittelt.

Funktioniert soweit super. Nun brauchen wir für einen neuen Eintrag den nächst höheren Index. Was liegt hier also näher als die Rückgabe der Methode mit 1 zu addieren.

Warum kommen bei den folgenden 2 Aufrufen jedoch verschiedene Werte heraus? (1. Aufruf gibt falschen Wert, 2. Aufruf den korrekten):


// liefert einen beliebigen Wert > als der maximale Index zurück (scheinbar in Zusammenhang mit den Rekursionen)
var nextIndex = this.GetMaxIndex(this._tree) + 1;

// liefert den korrekten Wert
var nextIndex = (this.GetMaxIndex(this._tree)) + 1;

Die Methode GetMaxIndex sieht wie folgt aus:


private int GetMaxIndex(Node node; Int32 iCurrentMax = -1)
{
     int iIndex = iCurrentMax ≥ 0 ? iCurrentMax : 0;

     if (node.Index > iIndex)
         iIndex = node.Index;

     if (node.Nodes.Count > 0)
     {
         foreach (Node child in node.Nodes)
         {
              iIndex = this.GetMaxIndex(child, iIndex);
         }
     }

     return iIndex;
}

Warum gibt es den Effekt? Es scheint so zu sein als würde das "+1" immer an das return angehängt.
Dieser Beitrag wurde 4 mal editiert, zum letzten Mal von inflames2k am .
Wissen ist nicht alles. Man muss es auch anwenden können.

PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager | Spielkartenbibliothek
private Nachricht | Beiträge des Benutzers
Sarc
myCSharp.de - Member



Dabei seit:
Beiträge: 426

beantworten | zitieren | melden

Hallo,

woher genau kommt die Variable node und wieso wird der Parameter parent nicht genutzt?
private Nachricht | Beiträge des Benutzers
inflames2k
myCSharp.de - Experte

Avatar #AARsmmPEUMee0tQa2JoB.png


Dabei seit:
Beiträge: 2358

Themenstarter:

beantworten | zitieren | melden

Sorry, Copy und Paste Fehler ins Forum. 8o Ist korrigiert.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von inflames2k am .
Wissen ist nicht alles. Man muss es auch anwenden können.

PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager | Spielkartenbibliothek
private Nachricht | Beiträge des Benutzers
Sarc
myCSharp.de - Member



Dabei seit:
Beiträge: 426

beantworten | zitieren | melden

Ist das denn die 1:1-Version der Methode die nicht funktioniert, oder hast du noch was weggelassen/geändert?
Du manipulierst ja in der Methode keine Zustände (Methode sollte daher auch statisch sein), somit muss die Methode idempotent sein.
Ich erkenne zumindest nicht, wieso das nachfolgende Aufrufen der Methode unterschiedliche Ergebnisse bringen sollte.
private Nachricht | Beiträge des Benutzers
inflames2k
myCSharp.de - Experte

Avatar #AARsmmPEUMee0tQa2JoB.png


Dabei seit:
Beiträge: 2358

Themenstarter:

beantworten | zitieren | melden

Jetzt ist es die 1:1- Version der Methode.
Zitat
Ich erkenne zumindest nicht, wieso das nachfolgende Aufrufen der Methode unterschiedliche Ergebnisse bringen sollte.

Ich auch nicht, das ist ja der Grund warum ich das Thema eröffnet habe.
Einziges was mir dabei eben aufgefallen ist, ist das das Ergebnis des ersten Aufrufs identisch mit dem wäre, wenn ich das +1 bereits in der Methode ausführen würde.

Also, folgendes Liefert das gleiche Ergebnis


var nextIndex = this.GetMaxIndex(this._tree) + 1;

wie:


var nextIndex = this.GetNextIndex(this._tree);

...

private int GetNextIndex(Node node; Int32 iCurrentMax = -1)
{
     int iIndex = iCurrentMax ≥ 0 ? iCurrentMax : 0;

     if (node.Index > iIndex)
         iIndex = node.Index;

     if (node.Nodes.Count > 0)
     {
         foreach (Node child in node.Nodes)
         {
              iIndex = this.GetNextIndex(child, iIndex);
         }
     }

     return iIndex + 1;
}

Was bedeuted, wenn der erste Wert direkt den größten Index hat, würde für den neuen Index immer ein Wert herauskommen, der bei n-Elementen größter Index + n-1 liefern würde. Was bei der addition innerhalb der Methode auch logisch ist. Warum aber außerhalb?

EDIT:
Von Zommi erhielt ich folgende Fragen per PN:
Zitat
Es scheint nicht, als ob du einen minimalcode erzeugt hättest, der den selben Fehler reproduziert.

Was ist node.Nodes für eine Collection?
Ist node.Index ein komplexes Property oder einfach ein Member?
Was ist mit this._tree?

In wie fern wäre in dem simplem Fall minimalcode notwendig? Der Code ist ja bereits nur ein paar Zeilen lang.

node.Nodes ist eine List<Node> und Index eine Property. "this._tree" ist quasi der Rootknoten. Alles in allem habe ich hier halt einen Baum von Instanzen der Klasse Node. Wobei jede Instanz eben einen Index hat. Der Index ist global für den ganzen Baum einmalig. - Daher die Ermittlung des nächst größeren Index.

Das korrekte Ergebnis für den größten Index erhalte ich allerdings eben nur wenn ich den Methodenaufruf in Klammern setze bevor ich +1 ausführe. Ein Beispiel wäre eben folgende Baum:
root Index = 1
     Index = 2
         Index = 3
         Index = 4
         Index = 6
         Index = 9
     Index = 5
         Index = 8             
     Index = 7

Gehe ich den Baum nun mit der im Eingangsbeitrag geposteten Methode durch, erhalte ich bei einfachem Aufruf von "GetMaxIndex" den korrekten Wert 9. Hänge ich die Addition ohne Klammerung der Methode an den Aufruf an, erhalte ich jedoch 12. Mit Klammerung vor der Addition erhalte ich wiederum korrekt wie ich es erwarte für den nächst höheren Index die 10.
Dieser Beitrag wurde 5 mal editiert, zum letzten Mal von inflames2k am .
Wissen ist nicht alles. Man muss es auch anwenden können.

PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager | Spielkartenbibliothek
private Nachricht | Beiträge des Benutzers
unconnected
myCSharp.de - Member

Avatar #avatar-3200.jpg


Dabei seit:
Beiträge: 862
Herkunft: Oerlinghausen/NRW

beantworten | zitieren | melden


Hmm und Du bist Dir sicher das Du das wirklich so aufrufst und nicht:

var nextIndex = this.GetMaxIndex(this._tree, + 1);


Hatte da was falsch gesehen..

Zitat
Jetzt ist es die 1:1- Version der Methode.

wirklich? Das kann nicht kompileren, da ist ein Semikolon hinter dem Parameter node.
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von unconnected am .
private Nachricht | Beiträge des Benutzers
inflames2k
myCSharp.de - Experte

Avatar #AARsmmPEUMee0tQa2JoB.png


Dabei seit:
Beiträge: 2358

Themenstarter:

beantworten | zitieren | melden

Zitat von unconnected
Hmm und Du bist Dir sicher das Du das wirklich so aufrufst und nicht:

var nextIndex = this.GetMaxIndex(this._tree, + 1);

Ja da bin ich mir sicher. - Allerdings muss ich dennoch noch einmal schauen, da ich es versucht habe minimal nachzubauen (Methode 1:1 wie im richtigen Projekt und kleine Initialisierungsmethode für den Baum) und dort der Fehler nicht auftritt.
Zitat
wirklich? Das kann nicht kompileren, da ist ein Semikolon hinter dem Parameter node.

Was der einzige Unterschied ist. - Hatte erst begonnen das ganze selbst einzutippern bevor ich kopiert habe, daher kamen die Unterschiede zustande. - Der Methoden-Body entspricht exakt dem im Projekt.
Wissen ist nicht alles. Man muss es auch anwenden können.

PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager | Spielkartenbibliothek
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Zitat von inflames2k
In wie fern wäre in dem simplem Fall minimalcode notwendig?

Um zu verstehen, was passiert. Wie du selbst siehst, passiert etwas unerwartetes. So simpel ist es also nicht.

Daher wäre ein minimales, vollständiges, kompilierbares Beispiel super hilfreich.

Ich habe versucht, selbst eins zu erstellen, schaffe es aber nicht dein Problem zu reproduzieren:

using System;
using System.Collections.Generic;

namespace Rextester {

class Tree
{
    private Node _tree;

    public Tree(Node tree)
    {
        this._tree = tree;
    }

    public void PrintNextIndex()
    {
        var nextIndex = this.GetNextIndex(this._tree) + 1;
        Console.WriteLine(nextIndex);
    }

    private int GetNextIndex(Node node, Int32 iCurrentMax = -1)
    {
         int iIndex = iCurrentMax ≥ 0 ? iCurrentMax : 0;

         if (node.Index > iIndex)
             iIndex = node.Index;

         if (node.Nodes.Count > 0)
         {
             foreach (Node child in node.Nodes)
             {
                  iIndex = this.GetNextIndex(child, iIndex);
             }
         }

         return iIndex;
    }

}

class Node
{
    public int Index {get; set;}
    public List<Node> Nodes {get; set;}
}

public class Program
{
    static Node N(int index, params Node[] nodes)
    {
        return new Node{Index=index, Nodes=new List<Node>(nodes)};
    }

    public static void Main(System.String[] args)
    {
        var tree = new Tree(N(1,
                                N(2,
                                    N(3),
                                    N(4),
                                    N(6),
                                    N(9)),
                                N(5,
                                    N(8)),
                                N(7)));
        tree.PrintNextIndex();
    }
}

}

Kannst du das Problem in einem solch minimalen Snippet reproduzierbar machen?

Zudem verwürfelst du oft "GetNextIndex" mit "GetMaxIndex" in deinen Beschreibungen. Rufen sich diese beiden Methoden eventuell gegenseitig rekursiv auf? Das würde irgendwie erklären, warum ein +1 in der einen auch ein +1 in der anderen entspricht - jedoch nicht das unterschiedliche Klammerverhalten.

beste Grüße
zommi
Dieser Beitrag wurde 5 mal editiert, zum letzten Mal von zommi am .
private Nachricht | Beiträge des Benutzers
inflames2k
myCSharp.de - Experte

Avatar #AARsmmPEUMee0tQa2JoB.png


Dabei seit:
Beiträge: 2358

Themenstarter:

beantworten | zitieren | melden

Hallo Zommi,

wie ich schrieb (bevor du gepostet hast) erhalte ich das Verhalten im Minimalbeispiel auch nicht, weshalb ich noch einmal tiefer reinschauen muss.

Es gibt nur eine Methode. GetNextIndex(Node, Int32) wie vorhin gepostet war nur um zu zeigen, was für ein Ergebnis ich bei GetMaxIndex(Node, Int32) erhalte wenn ich direkt 1 aufaddiere.

Nichts desto trotz schaue ich selber noch einmal durch, da ich es im Minimalbeispiel eben nicht reproduzieren kann.
Wissen ist nicht alles. Man muss es auch anwenden können.

PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager | Spielkartenbibliothek
private Nachricht | Beiträge des Benutzers
CoLo
myCSharp.de - Member



Dabei seit:
Beiträge: 232

beantworten | zitieren | melden

Hi, sorry, ich bin das nur kurz überflogen. Müsste da nicht


    foreach (Node child in node.Nodes)
         {
              iIndex = Math.Max(iIndex ,this.GetMaxIndex(child, iIndex));
         }
oder ähnlich stehen?

MfG CoLo
private Nachricht | Beiträge des Benutzers