Recursive nested loops - jak rozumieć

Witam,
mam pewien problem ze zrozumieniem rekursji w C# ale jeśli chodzi o rekursywne zagnieżdżone pętle. Rozumiem ideę rekursji (odwołanie funkcji do siebie samej, przekazanie wartości do siebie samej itp) ale może mi ktoś wytłumaczy jakim cudem po wprowadzeniu 2 dla Number of loops i 2 dla Number of iterations w poniższym przykładzie otrzyujemy 1 1, 1 2, 2 1, 2 2 jeżeli po spełnieniu warunku if mamy return i wyjście z funkcji a żeby otrzymać wartość 2 w tablicy musimy zwiększyć counter do wartości 2. Jak wygląda egzekucja tego kodu (przykład z książki)?

Pozdrawiam i bardzo dziękuję za jakiekolwiek wskazówki.

Kod:

class RecursiveNestedLoops
{
    static int numberOfLoops;
    static int numberOfIterations;
    static int[] loops;

    static void NestedLoops(int currentLoop)
    {
        if (currentLoop == numberOfLoops) 
        {
            PrintLoops();
            return;
        }

        for (int counter = 1; counter <= numberOfIterations; counter++)
        {
            loops[currentLoop] = counter;
            NestedLoops(currentLoop + 1); //recursion
        }
    }

    static void PrintLoops()
    {
        for (int i = 0; i < numberOfLoops; i++)
        {
            Console.Write("{0} ", loops[i]);
        }
        Console.WriteLine();
    }


    static void Main(string[] args)
    {
        Console.Write("Number of loops = ");
        numberOfLoops = int.Parse(Console.ReadLine());

        Console.Write("Number of iterations = ");
        numberOfIterations = int.Parse(Console.ReadLine());

        loops = new int[numberOfLoops];

        NestedLoops(0);
    }
}

No tak to działa. Masz tu tutaj rozwijanie i zwijanie stosu, gdy kolejne wywołania rekurencyjne się zaczynają i kończą.

Ja to tak rozumiem
11 : każda pętla for się odpaliła i wpisała jeden po czym wołany jest NestedLoops. Jak currentLoop == numberOfLoops to wypisujemy 11
12: powrót z najbardziej zagłębionej funkcji (gdzie currentLoop == numberOfLoops ) do funkcji dla ostatniego indeksu w pętli for. Wpisywane jest 2 po czym sytuacja analogiczna dla pierwszego punktu
21 masz dwa powroty currentLoop == numberOfLoops a potem for counter == 2, gdzie w kolejnej iteracji mamy 3 więc funkcja się kończy (czyli drugi powrót)
22: analogicznie co 12

Moja rada: dawaj wszędzie Console.Write. Nie zrozumiesz tego inaczej bez analizy co i jak się kiedy wywołuje

slsy napisał(a):

No tak to działa. Masz tu tutaj rozwijanie i zwijanie stosu, gdy kolejne wywołania rekurencyjne się zaczynają i kończą.

Ja to tak rozumiem
11 : każda pętla for się odpaliła i wpisała jeden po czym wołany jest NestedLoops. Jak currentLoop == numberOfLoops to wypisujemy 11
12: powrót z najbardziej zagłębionej funkcji (gdzie currentLoop == numberOfLoops ) do funkcji dla ostatniego indeksu w pętli for. Wpisywane jest 2 po czym sytuacja analogiczna dla pierwszego punktu
21 masz dwa powroty currentLoop == numberOfLoops a potem for counter == 2, gdzie w kolejnej iteracji mamy 3 więc funkcja się kończy (czyli drugi powrót)
22: analogicznie co 12

Moja rada: dawaj wszędzie Console.Write. Nie zrozumiesz tego inaczej bez analizy co i jak się kiedy wywołuje

Dziekuję za odpowiedź.
Właśnie chodzi mi o moment w którym mamy otrzymać wartości 1 2. Po otrzymaniu 1 1 czyli gdy zadziała pierwszy raz PrintLoops() mamy return co powoduje że następuje wyjście z funkcji NestedLoops i praktycznie powinno się na 1 1 zakończyć. Gdzie następuje ten powrót do ponownej egzekucji NestedLoops?
Pozdrawiam

2e3ftgwsfgtnfq napisał(a):

Gdzie następuje ten powrót do ponownej egzekucji NestedLoops?

Serio, dodaj sobie wszędzie printy: dla każdego wywołania rekurencyjnego (przed wywołaniem jak i po wywołaniu) jak i każdego obiegu pętli. Będziesz miał przejrzysty log, który mówi jak jest

    for (int counter = 1; counter <= numberOfIterations; counter++)
    {
        loops[currentLoop] = counter;
        NestedLoops(currentLoop + 1); //recursion
        // tutaj, counter ++
    }

W tym wypadku NestedLoops(currentLoop + 1); wywoła funkcję, która wypisze 11 po czym następuje return. Następnie przechodzimy do linii, którą dodałem w komentarzu

Powtórzę jeszcze raz: DODAJ printy. Zrób różne wersje, gdzie wwołania są w różnych miejscach i patrz jak program się zmienia. Przykładowo zobacz co się stanie, gdy zamienisz if i for miejscami, będziesz miał inny wynik.

Rekurencji nie da się wytłumaczyć. Ćwicz, obserwuj a intuicja przyjdzie. Pamiętaj, żeby zrozumieć rekurencję trzeba najpierw zrozumieć rekurencję

slsy napisał(a):

2e3ftgwsfgtnfq napisał(a):

Gdzie następuje ten powrót do ponownej egzekucji NestedLoops?

Serio, dodaj sobie wszędzie printy: dla każdego wywołania rekurencyjnego (przed wywołaniem jak i po wywołaniu) jak i każdego obiegu pętli. Będziesz miał przejrzysty log, który mówi jak jest

Kopiuj

    for (int counter = 1; counter <= numberOfIterations; counter++)
    {
        loops[currentLoop] = counter;
        NestedLoops(currentLoop + 1); //recursion
        // tutaj, counter ++
    }

W tym wypadku NestedLoops(currentLoop + 1); wywoła funkcję, która wypisze 11 po czym następuje return. Następnie przechodzimy do linii, którą dodałem w komentarzu

Powtórzę jeszcze raz: DODAJ printy. Zrób różne wersje, gdzie wwołania są w różnych miejscach i patrz jak program się zmienia. Przykładowo zobacz co się stanie, gdy zamienisz if i for miejscami, będziesz miał inny wynik.

Rekurencji nie da się wytłumaczyć. Ćwicz, obserwuj a intuicja przyjdzie. Pamiętaj, żeby zrozumieć rekurencję trzeba najpierw zrozumieć rekurencję

Zrobiłem test, mój for wygląda tak:

for (int counter = 1; counter <= numberOfIterations; counter++)
{

loops[currentLoop] = counter;
NestedLoops(currentLoop + 1); //recursion
Console.WriteLine(counter);

}

Poniżej screenshot i opis w krokach i moment którego kompletnie nie mogę zrozumieć.

Podajemy
Number of loops = 2
Number of iterations = 2

Egzekucja i kodu:

krok1.
NestedLoops(0) z sekcji Main

krok2.
static void NestedLoops(0)
if (currentLoop == numberOfLoops) czyli if(0 == 2) to jest FALSE, kod w if jest pomijany

krok3.
wchodzimy do for

for (int counter = 1; counter <= numberOfIterations; counter++)
{
loops[0] = 1;
NestedLoops(currentLoop + 1); //rekurencja, z powrotem do NestedLoops ale jako NestedLoops(1)
}

krok4.
static void NestedLoops(1)
if (currentLoop == numberOfLoops), czyli if (1 == 2), FALSE, kod w if pomijany

krok5.
wchodzimy do for
for (int counter = 1; counter <= numberOfIterations; counter++)
{
loops[1] = 1;
NestedLoops(currentLoop + 1); //rekurencja, z powrotem do NestedLoops ale jako NestedLoops(2)
}

krok6.
static void NestedLoops(2)
if (currentLoop == numberOfLoops) czyli if(2 == 2) to jest TRUE, kod w if jest wykonywany
{
PrintLoops();
return; <--- co robi to return?
}

I W TYM MOMENCIE JEST MOJE PYTANIE (nie rozumiem dalszego wykonywania kodu)

krok7
PrintLoops() wyświetla pierwszy wiersz: 1 1
Kończy się pętla w PrintLoops.... i co dalej?
Czy następuje jakaś równorzędna egzakucja kodu PrintLoops i return?
Co dzieje się po wykonianiu kodu w PrintLoops tj. po wyświetlaniu 1 1.
Zgodnie ze screenshotem wyświetlany jest counter: 1, czyli można założyć że jednocześnie następuje egzakucja PrintLoops i return?

Pozdrawiam

Proszę bardzo, dodałem wypisywanie w jakim wywołaniu NestedLoops jesteśmy i jak ustawiana jest tablica loops, mam nadzieję, że pomoże zrozumieć:

class Program
{
    private static int _numberOfLoops;
    private static int _numberOfIterations;
    private static int[] _loops = [];

    private static void NestedLoops(int currentLoop)
    {
        Console.WriteLine($"NestedLoops({currentLoop})");
        if (currentLoop == _numberOfLoops) 
        {
            PrintLoops();
            return;
        }

        for (int counter = 1; counter <= _numberOfIterations; counter++)
        {
            Console.WriteLine($"NestedLoops({currentLoop}): _loops[{currentLoop}] = {counter}");
            _loops[currentLoop] = counter;
            NestedLoops(currentLoop + 1); //recursion
        }
    }

    private static void PrintLoops() => Console.WriteLine("_loops: " + string.Join(" ", _loops));

    private static void Main()
    {
        Console.Write("Number of loops = ");
        _numberOfLoops = int.Parse(Console.ReadLine());

        Console.Write("Number of iterations = ");
        _numberOfIterations = int.Parse(Console.ReadLine());

        _loops = new int[_numberOfLoops];

        NestedLoops(0);
    }
}

wynik:

Number of loops = 2
Number of iterations = 2
NestedLoops(0)
NestedLoops(0): _loops[0] = 1
NestedLoops(1)
NestedLoops(1): _loops[1] = 1
NestedLoops(2)
_loops: 1 1
NestedLoops(1): _loops[1] = 2
NestedLoops(2)
_loops: 1 2
NestedLoops(0): _loops[0] = 2
NestedLoops(1)
NestedLoops(1): _loops[1] = 1
NestedLoops(2)
_loops: 2 1
NestedLoops(1): _loops[1] = 2
NestedLoops(2)
_loops: 2 2

Co do wykonania - nie ma tu mowy o żadnej asynchroniczności, równoległości itd. Jest kilkukrotne wywołanie rekurencyjne NestedLoops, pamiętaj, że każde takie wywołanie ma swoją wartość parametru (currentLoop) oraz korzysta ze wspólnych pól klasy (_loops, _numberOfIterations, _numberOfLoops).

krok6.
static void NestedLoops(2)
if (currentLoop == numberOfLoops) czyli if(2 == 2) to jest TRUE, kod w if jest wykonywany
{
PrintLoops();
return; <--- co robi to return?
}

return kończy obecne wywołanie NestedLoops, w tym wypadku NestedLoops(2) które poprzednio wypisało zawartość tablicy. Wykonanie programu wraca za miejsce wywołania metody, czyli za NestedLoops(currentLoop +1); i wykonuje się kolejny obrót pętli, lub zakończenie tej metody, jeżeli cała pętla już się wykonała.