Rekurencje - jak to zrozumieć, jak to sobie wyobrazić?

Question

int rec(int n)
{
    if (n < 2) {
        return  1;
    }

    return n*rec(n-1);
}

int main() {
    int silnia = rec(5);

    std::cout << silnia;
    return 0;
}

Hej, znalazłem w internecie powyższy przykład jako najlepszy przykład działania rekurencji. No i faktycznie wszystko działa ale nie moge uzmysłowić sobie jednej rzeczy.

Skoro w warunku mam przypadek domyślny jako return 1 to dlaczego w ogóle w zmiennej "Silnia" mam poprawną wartość? Patrzac na to wydaje mi się, że funkcja na sam koniec powinna zwrócić po prostu 1. 

Rozumiem to tak (poprawcie mnie jeśli się mylę):
Wykonująca się rekurencja nie zwraca żadnej wartości dopóki jej praca się nie dopełni.
W tym przypadku podstawia sobie  wartości do równania jakim jest mnożenie kolejnych liczba i dopiero na sam koniec, kiedy już zwraca wartość zamiast samej siebie, wykonuje mnożenie i wyrzuca wynik.

 

Jak to na spojrzec aby zrozumieć?

 

Answer 1

Najłatwiej wyobrazić sobie drzewko:
rec(5)  -->  return 5*rec(4)

   rec(4)  --> return 4*rec(3)    

       rec(3)  --> return 3*rec(2)

          rec(2)  --> return 2*rec(1)

                rec(1) --> return 1

I drzewko zaczyna się kurczyć, bo warunkiem zatrzymującym rekurencję jest n < 2:

                  rec(1)  <-- return 1

          rec(2)  <-- return 2*rec(1) czyli: return 2*1 = 2

       rec(3)  --> return 3*rec(2) czyli: return 3*2 = 6

   rec(4)  --> return 4*rec(3)  czyli: return 4*6 = 24

rec(5)  -->  return 5*rec(4) czyli: return 5*24 = 120

Answer 2

Funkcja zwraca 1 gdy wprowadzona wartość jest mniejsza od 2 lub wartość pomnożoną przez tą funkcje z argumentem o 1 mniejszym czyli

rec(5)

jest mniejsze niż 2? nie więc zwraca:

5 * rec(5-4) czyli 5 * rec(4)

na tym etapie jest:

5 * rec(4)

rec(4) rozbijasz dalej więc powstaje

5 * 4 * rec(4-1) czyli 5*4*rec(3)

kolejne rozwinięcia to:

5 * 4 * 3 * rec(3-1)

5 * 4 * 3 * 2 * rec(2-1) na tym etapie rec(2) zwraca 1 bo argument jest mniejszy od 1 więc ostatecznie powstaje

5 * 4 * 3 * 2 * 1

Answer 3

Czyli dobrze to rozumiem, że:
Wykonująca się rekurencja nie zwraca żadnej wartości dopóki jej praca się nie dopełni.
W tym przypadku podstawia sobie  wartości do równania jakim jest mnożenie kolejnych liczba i dopiero na sam koniec, kiedy już zwraca wartość zamiast samej siebie, wykonuje mnożenie i wyrzuca wynik.

No bo to jest dziwne, skoro mamy funkcje, które ma reutrn 1 ale mimo wszystko zwraca wynik działania no to jest ciężkie do zrozumienia.

Te drzewka, które mi pokazaliście mają sens ale zaburza go ten "return", który się tam pojawia.

Comments

Czemu "return" zaburza? Zauważ, że każde wywołanie funkcji musi zwrócić wartość poprzez return. Nawet wywołanie funkcji w funkcji :)

---

A no dlatego, że jak widzę return to wiem, że funkcja się kończy i podaje wartość, która zwraca return. Tak wiec pomyślałem od razu, że funkcja ta zwraca 1

Obejrzałem odcinek: https://www.youtube.com/watch?v=jNi_X5bvmQ0
Już jest mniej więcej jasne i wynika z niego to co myślałem, a mianowicie to, że funkcja liczy dopiero rozwiązanie jak dostanie wynik z przypadka podstawowego czyli w przypadku silni jest to 1!