Zachowanie zmiennych w rekursji

0

Witam, wklejam na starcie kod programu w Pascalu:

function odpowiedz (d : drzewo) : Boolean;
var czy : Boolean;

  function ilew(d : drzewo, var czy : boolean) : Integer;
  begin
    if d<>nil then begin
      l:=ilew(d^.lsyn)+1;
      p:=ilew(d^.psyn)+1;
      if l=p then begin
        if l>0 then czy:=true;
      end
      else ilew:=l+p;
    end
    else ilew:=-1;
  end;

begin
  czy:=false;
  ilew(d);
  odpowiedz:=czy;
end;

W zadaniu chodzi o to, aby sprawdzić, czy istnieje w drzewie taki wierzchołek, którego lewe i prawe poddrzewa są niepuste i zawierają tyle samo węzłów.

Nie chodzi mi już o samo zadanie, ale o aspekt teoretyczny związany ze zmiennymi l oraz p w moim programie.
Otóż - powiedzmy, że jestem w jakimś węźle x. Mam już obliczoną liczbę wierzchołków w lewym poddrzewie węzła x - jest ona przechowywana w zmiennej l. Pozostało policzyć ile wierzchołków ma prawe poddrzewo x - aby to zrobić będę działać rekurencyjnie na prawym poddrzewie x. I teraz właściwe pytanie:
Co się dzieje ze zmienną l? Czy jest ona za każdym razem kopiowana do nowego rekordu aktywacji i kiedy obliczę wartość p i znajdę się z powrotem w wierzchołku x, to otrzymam właściwe wartości zarówno l jak i p? Czy też wszystkie działania na niej będą wykonywane podczas rekursji "na oryginale" przez to gdy wrócę do wierzchołka x, to otrzymam prawidłową zmienną p, zaś totalnie błędną zmienną l?

0

Co się dzieje ze zmienną l? Czy jest ona za każdym razem kopiowana do nowego rekordu aktywacji i kiedy obliczę wartość p i znajdę się z powrotem w wierzchołku x, to otrzymam właściwe wartości zarówno l jak i p?

Co to jest ten "nowy rekord aktywacji"?

Czy też wszystkie działania na niej będą wykonywane podczas rekursji "na oryginale" przez to gdy wrócę do wierzchołka x, to otrzymam prawidłową zmienną p, zaś totalnie błędną zmienną l?

Z tego co widzę (albo nie widzę), to zmienne l i p to zmienne globalne, więc cały czas operujesz na tej samej instancji, bez względu na zagłębienie rekurencji - nie ma żadnego kopiowania; A skoro operujesz na tej samej zmiennej, to ciągle ją nadpisujesz, więc jeśli takiego zachowania nie oczekiwałeś, to najpewniej dostaniesz błędny wynik; Tak się właśnie wychodzi na przyzwyczajeniach z pakowania góry zmiennych globalnych, zamiast używania parametrów;

Jeśli potrzebujesz w każdym kolejnym rekursyjnym wywołaniu operować na nowej kopii zmiennej, to przekazuj ją przez wartość - zmiany wartości takiego parametru po pierwsze będą w ogóle możliwe, a po drugie - widoczne będą jedynie lokalnie (w obrębie danej instancji funkcji);

A tak poza tym - testowałeś ten kod i nie wiesz, czy daje poprawny wynik? Czy jeszcze nie testowałeś?

0

Po pierwsze dzięki za odpowiedź! ;)

To jedno z wielu zadan przygotowawczych do egzaminu, dlatego piszę je tylko na kartce (bo chodzi o procedury) - gdybym miał to jeszcze testować, a przy okazji implementować tworzenie drzewa itd, to bym nie zdąrzył 1/3 zadan zrobić do egzaminu ;)

l, p to nie zmienne globalne - moje przeoczenie, że ich nie zdeklarowałem - pomyłka :P
Czyli jeżeli zdefiniowałbym zmienne l, p w funkcji odpowiedz, a potem przekazał je przez wartosc do funkcji ilew, to za kazdym razem gdy wywołuje rekurencję tworzona by była nowa kopia l,p ?

0

Sorry napisałem [CIACH!], już rozumiem :P
Dzięki ;)

1

Czyli jeżeli zdefiniowałbym zmienne l, p w funkcji odpowiedz, a potem przekazał je przez wartosc do funkcji ilew, to za kazdym razem gdy wywołuje rekurencję tworzona by była nowa kopia l,p ?

Tak, lokalna kopia parametru z poprzedniego wywołania; Więc tyle kopii parametru, ile rekursyjnych wywołań funkcji;

Zobacz na poniższy kod - realizuje on rekurencyjne odliczanie i wyświetlanie adresu parametru w postaci liczby heksadecymalnej:

uses
  SysUtils;

var
  intGlobalVariable: Integer = 0;

  procedure GlobalVariableTest();
  begin
    WriteLn('Variable addr: $', IntToHex(LongInt(@intGlobalVariable), 0));

    if intGlobalVariable < 3 then
    begin
      Inc(intGlobalVariable);
      GlobalVariableTest();
    end;
  end;

var
  intByRefVariable: Integer = 0;

  procedure ParamByRefTest(var AParam: Integer);
  begin
    WriteLn('Param addr: $', IntToHex(LongInt(@AParam), 0));

    if AParam < 3 then
    begin
      Inc(AParam);
      ParamByRefTest(AParam);
    end;
  end;

  procedure ParamByValueTest(AParam: Integer);
  begin
    WriteLn('Param addr: $', IntToHex(LongInt(@AParam), 0));

    if AParam < 3 then
    begin
      Inc(AParam);
      ParamByValueTest(AParam);
    end;
  end;

  procedure ParamByConstTest(const AParam: Integer);
  begin
    WriteLn('Param addr: $', IntToHex(LongInt(@AParam), 0));

    if AParam < 3 then
      ParamByConstTest(AParam + 1);
  end;

begin
  GlobalVariableTest();
  WriteLn;
  ParamByRefTest(intByRefVariable);
  WriteLn;
  ParamByValueTest(0);
  WriteLn;
  ParamByConstTest(0);
  ReadLn;
end.

Wyjście:

Variable addr: $409298
Variable addr: $409298
Variable addr: $409298
Variable addr: $409298

Param addr: $40929C
Param addr: $40929C
Param addr: $40929C
Param addr: $40929C

Param addr: $12FFA4
Param addr: $12FF88
Param addr: $12FF6C
Param addr: $12FF50

Param addr: $12FFA4
Param addr: $12FF88
Param addr: $12FF6C
Param addr: $12FF50

Procedura GlobalVariableTest operuje na globalnej zmiennej intGlobalVariable, inkrementuje ją i przekazuje do kolejnych wywołań; W każdym rekursyjnym wywołaniu procedury, nie jest tworzona żadna kopia - dostęp uzyskiwany jest bezpośrednio, więc bez względu na poziom rekurencyjnego zagłębienia, molestowana jest jedna zmienna;

Drugi przykład to procedura ParamByRefTest - ona także korzysta ze zmiennej globalnej, ale za pośrednictwem parametru; Zmienna przekazywana jest do kolejnych wywołań przez referencję, więc tak samo jak wcześniej - operuje tylko i wyłącznie na jednej instancji zmiennej, do której dostęp uzyskuje przez parametr;

Trzecia procedura to ParamByValueTest, która pobiera w parametrze liczbę przez wartość; Tworzona zostaje nowa "zmienna", dlatego że w takim przypadku, można przekazać samą wartość - nie musi to być zmienna; W każdym kolejnym wywołaniu tworzona jest kolejna zmienna, więc adres parametru w każdym rekurencyjnym wywołaniu będzie inny;

Ostatnia procedura to ParamByConstTest - ona przyjmuje liczbę w parametrze przez stałą; W tym przypadku także tworzona jest nowa kopia dla każdego rekursyjnego wywołania, dlatego też adresy parametru będą różne;


Wszystkie procedury działają inaczej i dają różne możliwości:

  • GlobalVariableTest - nie posiada parametrów, więc musi mieć dostęp do zmiennej; ponadto wprowadzone zmiany mają zasięg globalny,
  • ParamByRefTest - skoro pobiera liczbę przez referencję, trzeba podać jej zmienną, której sama widzieć nie musi; tak samo jak w powyższej - wprowadzone zmiany mają zasięg globalny,
  • ParamByValueTest - pobiera liczbę w parametrze przez wartość, więc nie potrzebuje zmiennej; w każdym kolejnym wywołaniu tworzy kopię parametru, a zmiany mają zasięg lokalny,
  • ParamByConstTest - pobiera liczbę przez stałą i tak samo nie potrzebuje zmiennej, też w każdym wywołaniu tworzy kopię parametru, jednak nie umożliwia modyfikowania jego wartości.
0

Dzięki wielkie! Na prawdę szacun, że chciało ci się tyle robić/pisać/ tłumaczyć, ale na prawdę jestem bardzo wdzięczny! Bardzo mi pomogłeś i jeszcze raz dzieki! :D

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