Rekurencja - problem ze zrozumieniem

pytanie zadane 16 września 2015 w Algorytmy przez emSon Stary wyjadacz (10,480 p.)

Czesc. Mam problem z pojeciem myslenia rekurencyjnego. Wiem co to jest, na czym to polega , lecz nie potrafie sie przestawic na taki tok myslenia. Moglby ktos napisac pare przykladow w formie petli, a potem w rekursji? (w dowolnym jezyku) Podejrzewam , ze troche by mi to pomoglo. Dzieki.

7 odpowiedzi

odpowiedź 5 października 2015 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

Rekurencje można zrozumieć na różne sposoby. Ja przedstawie swój na podstawie silni:

int rekurencja ( int a ){
    if ( a == 1 ) return 1;
    else return rekurencja ( a - 1 ) * a;
}

Zakładamy, że chcemy obliczyć silnie z 5

Więc

rekurencja ( 5 ) = rekurencja ( 4 ) * 5   < - musze obliczyć tą rekurencja ( 4 )

to odpalam ją rekurencja( 4 ) = rekurencja ( 3 ) * 4   <- teraz muszę obliczyć rekurencja ( 3 )

rekurencja ( 3 ) = rekurencja ( 2 ) * 3

rekurencja ( 2 ) = rekurencja ( 1 ) * 2

rekurencja ( 1 ) = 1            <- wiemy ile wynosi ta funkcja ( pierwszy if )

Następnie program sobie wraca z dołu do góry mając wyliczone rekurencja ( 1 ), rekurencja ( 2 ).. i podstawia wyniki. Mam nadzieję, że troszkę rozjaśniłem :). Rekurencja to stosunkowo trudne zagadnienie i potrzeba na nie dużo czasu by zrozumieć, więc się nie przejmuj jak teraz nie ogarniasz

komentarz 5 października 2015 przez writen Nałogowiec (29,060 p.)
edycja 5 października 2015 przez writen

Twoja funkcja obliczająca silnię zawiera błąd.

komentarz 6 października 2015 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

Tak bo nie uwzględniam a==0 ale mi bardziej chodziło o wyjaśnienie

odpowiedź 16 września 2015 przez jeremus Maniak (59,720 p.)

bardzo przystępnie przedstawił to Miroslaw Zelent ( jak wszystko zresztą ) - poszukaj takiego odcinka w kursie c albo c++ juz nie pamiętam

komentarz 16 września 2015 przez emSon Stary wyjadacz (10,480 p.)

nie zeby cos, ale jestesmy na jego forum i nie pytal bym sie o nic uprzednio nie obejrzawszy jego filmu o takiej tematyce ;) zrozumialem sama zasade dzialania tego, ale nie potrafie przekonwertowac nic z petli iteracyjnej na funkcje referencyjna. dlatego prosze o pare przykladow

odpowiedź 16 września 2015 przez event15 Szeryf (93,790 p.)

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

int binary_search(int *tab, int x, int left, int right) {
    if(left == right) 
        if(tab[left] == x) return left;
        else return -1;
    else {
        int mid = (left + right)/2;
        if(tab[mid] == x) return mid;
        else 
            if (x < tab[mid]) return binary_search(tab, x, left, mid);
        else return binary_search(tab, x, left, right);
    }
}

komentarz 16 września 2015 przez emSon Stary wyjadacz (10,480 p.)

dzieki za przyklady, chociaz chodzilo mi o cos prostego a zapisanego najpierw np. w petli for, a potem w funkcji rekursyjnej ;)

odpowiedź 16 września 2015 przez Szykem2 Nałogowiec (29,510 p.)

Praktyczne każdy kod iteracyjny da sie zapisać rekurencyjnie np:

long long fib_it(int n) {
        int prev = 1, curr = 1, next = 1;
        for (int i = 3; i <= n; i++) {
           next = cur + prev;
           prev = cur;
           cur = next;
        }
        return next;
    }

long long fib_rec(int n) {
    if(n ==1 || n == 2) {
        return 1;
    }
    return fib_rec(n-1) + fib_rec(n-2);
}

Czasem używając algorytmu rekurencyjnego można coś zaprojektować w znacznie czytelniejszej formie. Jeśli jesteś ciekaw zobacz na czym polega programowanie dynamiczne i zoptymalizuj metodę rekurencyjną.