Rekurencja w C

0

Witam . Mam problem ze zrozumieniem tej funkcji rekurencyjnej w C:

void notail(int n) {
    if (n > 0) {
        notail(n-1);
        printf("%d\t", n);
        notail(n-1);
    }
}

Wynik dla n=3 jest: 1 2 1 3 1 2 1
'Pojedyncza' rekurencje rozumiem , jednak nie moge poradzic sobie z tym kodem gdzie wywolane sa jedna pod druga. Pomoze mi ktos to zrozumiec krok po kroku?

0

We wklejonym kodzie brakuje jednej klamry, więc nawet się nie skompiluje. Umiejscowenie tej klamry ma znaczenie podczas dochodzenia co się dzieje.

0

Racja, moj blad, juz poprawilem. Chodzi mi bardziej o zrozumienie rekurencji w tym przypadku krok po kroku. Z funkcja rekurencyjna obliczajaca silnie dalem sobie rade jednak z ta nie umiem sobie poradzic , dlaczego jest taki wynik a nie inny?

0

Dodaj wiecej printf (d*pa debugging) albo naucz sie odpalac debugger.

1

Szczerze pisząc ja też nie rozumiem po co dwa rekurencyjne wywołania na raz, we sensie nie rozumiem po co ktoś chciałby otrzymać taki wynik a nie inny. Przy większych liczbach to już w ogóle robi się miszmasz.

Zdecydowanie więcej sensu miałoby pojedyńcze wywołanie, zauważ że zakomentowanie wywołania przed printf da Ci inny wynik niż z zakomentowanym wywołaniem po printf.

0

Jest to tresc z wykladu ktory musze przeanalizowac i zrozumiec. Bawilem sie tym kodem i wiem ze zakomentowanie przed printfem da mi wynik 3 2 1 a po printfie 1 2 3 . Chodzi tu bardziej o zrozumienie dzialania algorytmu niz o jego wynik

8

Wyobraź sobie wywołania rekurencyjne jako drzewo:

            notail(4)            
            ^        ^           
           /          \          
          /            \         
        3-              -3       
        ^                ^       
       / \              / \      
      /   \            /   \     
    2-     -2        2-     -2   
    ^       ^        ^       ^   
   / \     / \      / \     / \  
 1-   -1 1-   -1  1-   -1 1-   -1

Gdzie pierwsze wywołanie rekurencyjne jest po lewej stronie, a drugie po prawej.
Twoja funkcja przechodzi in-order po takim drzewie

1

W obecnej postaci to cos w rodzaju jednowymiarowego fraktala, ktory jest symetryczny, a liczba odgalezien po lewej i prawej jest rowna n-1.
Mozna wyswietlac znaki zamiast cyfr o zmiennej jasnosci to moze bedzie lepiej widac (dla porownania mozna poszukac "mandelbrot ascii").

Przykladowa mapa znakow:
1: .
2: +
3: *
4: #

0
plx211 napisał(a):

Wyobraź sobie wywołania rekurencyjne jako drzewo:

            notail(4)            
            ^        ^           
           /          \          
          /            \         
        3-              -3       
        ^                ^       
       / \              / \      
      /   \            /   \     
    2-     -2        2-     -2   
    ^       ^        ^       ^   
   / \     / \      / \     / \  
 1-   -1 1-   -1  1-   -1 1-   -1

Gdzie pierwsze wywołanie rekurencyjne jest po lewej stronie, a drugie po prawej.
Twoja funkcja przechodzi in-order po takim drzewie

Dzieki wielkie duzo mi to rozjasnilo

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0