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

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.

Hallo,

woher genau kommt die Variable node und wieso wird der Parameter parent nicht genutzt?

Sorry, Copy und Paste Fehler ins Forum. 8o Ist korrigiert.

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.

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

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:

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.

Hatte da was falsch gesehen..

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

wirklich? Das kann nicht kompileren, da ist ein Semikolon hinter dem Parameter node.

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.

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.

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

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.

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