[C#] Nieznany mi wyjątek w algorytmie znajdowania drogi

Witam, jestem dość nowy w C# i wciąż miewam dziwne problemy z tym językiem. Ostatnio próbowałem napisać algorytm znajdujący trasę z punktu A do B.

Oto jak wygląda sam algorytm:

private route Way(place b, route r,int i)

        {

            if (r.LastPlace==b)

                return r;

            if (r.LastPlace.Container.Count > i)

            {

                r.GoTo(r.LastPlace.Container[i]);

                return Way(b, r, 0);

            }

            else

            {

                r.GoBack();

                MessageBox.Show("fsad");

                return Way(b, r, ++i);

            }

        }

a tak wygląda moja struktura route:

public struct route

    {

//-----------------------------------------------------------------------------------------------variables

        uint distance;

        LinkedList places;

        place start;

        //-----------------------------------------------------------------------------------------------properties

        public int NumeberOfPlaces

        {

            get { return places.Count+1; } //+1 - starting place

        }

        public int NumberOfRoads

        {

            get { return places.Count; }

        }

        public uint Distance

        {

            get { return distance; }

        }

        public place LastPlace

        {

            get 

            {

                if (distance == 0)

                    return start;

                else

                    return places.Last.Value.Destination;

            }

        }

        public place StartingPlace

        {

            get { return start; }

        }

        //-----------------------------------------------------------------------------------------------methods

        public route(place start)

        {

            this.start = start;

            distance = 0;

            places = new LinkedList();

        }

        public void GoTo(road p)

        {

            distance += p.Distance;

            places.AddLast(p);

        }

        public void GoBack()

        {

            if (distance > 0)

            {

                distance -= places.Last.Value.Distance;

                places.RemoveLast();

            }

        }

    }

Generalnie algorytm wydaje się być względnie w porządku, bo dla krótkich tras działa bez zarzutu, ale gdy wybiorę odrobinę dłuższą (np. przez 4 miejsca), podświetla mi się

return places.Last.Value.Destination;

we właściwości LastPlace i mówi, że mam wyjątek: Cannot evaluate expression because the current thread is in a stack overflow state.} System.Exception {System.StackOverflowException}

czy coś z tym można zrobić?

Tak - użyć debuggera i sprawdzić co się dzieje. ;] Prawdopodobnie dzieje się dokładnie to, co mówi wyjątek - następuje przepełnienie stosu. Struktury w C# - w przeciwieństwie do klas - są alokowane na stosie. A Ty wołasz rekurencyjnie Way, które struktur route generuje sporo. Pewnie place i road to też struktury, prawda? Możesz powiedzieć dlaczego struktury a nie klasy? Tak na marginesie już - okropnie zaprojektowany kod. Dlaczego umieszczasz start poza LL places?

Musisz zmniejszyć ilość rekurencyjnych wywołań metod(Way?), gdyż nie mieszczą się już one na stosie. Gdy debugger Ci przerwie działanie rzuć okiem na CallStack - powinieneś mieć masę wywołań jednej metody.

Do grupowania kodu w plikach stosuje się #region, nie komentarze :wink:

Do znajdywania drogi jest znacznie szybszy i powszechnie znany algorytm Dijkstry.

Szukanie drogi przez przeglądanie wszystkich możliwych wariantów jest już nie wykonalne (w ciągu życia jednego człowieka, na jednym komputerze) dla zaledwie 15 miast.

no ja wiem o algorytmie Dijkstry, ale miałem problemy z ogarnięciem jego działania, więc chciałem rekurencyjnie sprawdzić wszystkie możliwe kombinacje, biorąc pod uwagę, że mapa, którą dostałem jest dość mocno uproszczona i zakładam, że tych kombinacji nie ma tak niesamowicie wiele

jeżeli masz 4 miasta to ilość dróg od jednego do drugiego jest nieskończona.

A-[b-C-]-D

odcinek B-C może powtarzać się niesknoconą ilość razy, właśnie dla tego twój algorytm dal 4ch miast lub więcej w końcu przepełni każdy stos.