Rekurencja normalna a z parametrem dodatkowym

Witam

Postanowiłem postudiować algorytmikę. Na pierwszy ogień poszła rekurencja.
Wiem o tym, że normalne wywołania rekurencyjne działają w sposób taki, że wywołują funkcję i są zatrzymywane do czasu zwrócenia wyniku, który wraca po tej samej drodze od ostatniego wywołania do pierwszego.

Dzisiaj poczytałem o rekurencji z parametrem, który ponoć działa tak, że dla n-wywołań funkcji wynik z ostatniego wywołania przechodzi od razu do pierwszego. Pytanie: Jak możliwe jest omijanie pośrednich poziomów wywołań? Mógłby ktoś bardziej szczegółowo opisać proces jaki zachodzi wtedy?

Wyobraz sobie, ze przekazujesz wskaznik na jakies miejsce w pamieci do pierwszego wywolania. A on jest potem uzywany do zapisania wyniku przez n-te wywolanie. I funkcja rekurencyjna jako taka nic nie zwraca (void). Dzieki temu niejako od razu do pierwszego wywolania masz przekazany wynik - bezposrednio do pamieci, na ktora wskaznik przekazales.

No dobra, ale skąd program wie kiedy się tak zachować? Przecież nie wie czy po wywołaniu funkcji nie nastąpi jakieś działanie modyfikujące wartość zwracaną.

Ty go napiszesz, sam się nie napisze. Poczytaj o rekurencji ogonowej.

OK. Rozumiem, ale jak napisać taką funkcję samemu? Jakie warunki muszą być spełnione, żeby kompilator faktycznie uznał że należy zwrócić ostatni wynik?

Mam dwa przykłady rekurencji na podstawie algorytmu obliczania silni.

silnia(n)
{
  if(n==0)
    return 1;
  else
    return n*silnia(n-1);
}

silnia(n,w=1)
{
  if(n==0)
    return w;
  else
    return silnia(n-1, n*w);
}

Pierwsza jest to zwykła rekurencja, druga ogonowa. Ja nie wiem na jakiej podstawie kompilator wie, że wartość zwracana, przez wszystkie funkcje będzie taka sama... Ciężko mi to zrozumieć. Może ktoś może przedstawić jakiś inny problem do rozwiązania obydwiema rekurencjami?

Napisz troche programow w Prologu -> srodowisko SWI-Prolog

Ciekawe doswiadczenie, i zapewniam Cie ze bedziesz mistrzem rekurencji :-)

Na takiej, ze return jest na koncu. Jesli wszystkie wczesniejsze (a to dosc logiczne) weszly w return funkcja(), to oczywiste jest, ze nic innego po powrocie z wywolania nie beda robic. Zatem juz na poziomie kompilacji jest jasne, ze mozna zwrocic wynik najnizszej funkcji, ktora nie weszla w kolejny poziom, od razu do najwyzszego - bo wszystkie wyzej sa na etapie: return funkcja().

Dzięki.
Musze sobie to poukładać jakoś, przespać się z tym.
Muszę to ogarnąć bo to dopiero początek...

W prologu też się chętnie pobawię :)

Ogarnąłem to :) Ale mam jeszcze pytanie...

Mam algorytm przeszukiwania binarnego w postaci funkcji rekurencyjnej:

int search(int x, int *t, int left, int right)
{
    if(left > right)
        return -1;
    else
    {
        int mid = (left + right) / 2;

        if(t[mid] == x)
            return mid;
        else
        {
            if(x < t[mid])
                return search(x, t, left, mid-1);
            else
                return search(x, t, mid+1, right);
        }
    }
}

Działa bez zarzutu.
Ten sam algorytm ale z małą modyfikacją ostatecznie zwraca śmieci:

int search(int x, int *t, int left, int right)
{
    if(left > right)
        return -1;
    else
    {
        int mid = (left + right) / 2;

        if(t[mid] == x)
            return mid;
        else
        {
            if(x < t[mid])
                search(x, t, left, mid-1);  //zabrane return
            else
                search(x, t, mid+1, right);  //zabrane return
        }
    }
}

Pytanie, dlaczego?
Przecież funkcja rekurencyjna ogonowa zwraca wynik z ostatniego wywołania do pierwszego, a ta przecież nią jest.
Jeśli byłaby to zwykła rekurencja wynik w ogóle nie powinien być zwrócony, a jednak program kończy działanie.

Żeby ci to lepiej uzmysłowić wyobraź sobie że w ciele funkcji jest zdeklarowana zmienna int powrót; która przechowuje wyjściowy wynik funkcji a return to powrót =

W momencie kiedy zabrałeś return funkcja zwraca wartość nieprzewidywalną tak jak dla int x; a kolejne wywołania search nie działają już jak funkcje tylko procedury.

Popraw na coś takiego i powinno banglać

int search(int x, int *t, int left, int right)
{
    if(left > right)
        return -1;
    else
    {
        int mid = (left + right) / 2;

        if(t[mid] == x)
            return mid; // twoja_zmienna = int x = mid;
        else
        {
            int xxx;
            if(x < t[mid])
                xxx = search(x, t, left, mid-1);  //zabrane return
            else
                xxx = search(x, t, mid+1, right);  //zabrane return
            return xxx;
        }
    }
}

No dokładnie. C++ nie pluje się jak nie ma returna w funkcji która ma coś zwracać i wtedy zwraca śmieci (tzn jak da się opuścić funkcję bez zwracania wartości). W Javie np Twój kod z zabranym returnem nie skompilowałby się.

Dzięki, rozwialiście wszystkie moje wątpliwości :)

Czasem pisze aplikacje w Javie na telefon i faktycznie kapryśny ten kompilator :).
W sumie C++ też mógłby mieć takie zabezpieczenia. Teraz miałem przypadek w którym z dobrej funkcji zrobiłem złą. Ale jeśli bym nieświadomie nie napisał "return" to pewnie zanim bym znalazł błąd to bym ładnie się naszukał...

Nie jest kapryśny, tylko musi spełniać pewne założenia, dotyczące także bezpieczeństwa. Bo np co gdy w funkcji która zwraca referencję nie damy return i zwróci nam ona śmieci? Java jest deterministyczna - zmienne i tablice zawsze inicjowane są na tą samą wartość (tzn da się ją przewidzieć), itp itd

lukasz93 napisał(a)

W sumie C++ też mógłby mieć takie zabezpieczenia. Teraz miałem przypadek w którym z dobrej funkcji zrobiłem złą.

To używaj sensownego kompilatora i opcji kompilacji? CL z Visuala od razu rzuca ostrzeżeniem, że nie wszystkie ścieżki wykonywania się returnem kończą. Gcc wymaga dodania -Wall.