funkcja rekurencyjna silnia C

Question

hej, wiem że to idiotyczne pytanie ale nie kumam jednej rzeczy

// Example program
#include <iostream>
#include <string>


long silnia(long liczba){
    if(liczba < 2) return 1;
    
    int wynik = liczba*silnia(liczba-1);
    
    return wynik;
}

int main()
{
     printf("%d", silnia(4));
}

Dlaczego to zwraca poprawny wynik? :O

Skoro na końcu i tak zwracam "1" to skąd ten wynik?
Skoro funkcja za każdym razem zwraca wynik, a nagle 1 to czy na ekran nie powinno wywalic 1 zamiast popranwego wyniku?

 

Funkcje rekurencyjne kończą swoją pracę napotykając return'a z 1 czy o co tu chodzi?

Answer 1

Na końcu zwracasz 1 dla ostatniej instancji. W rzeczywistości program tworzy "liczba" ilosci takich funkcji, a kiedy dochodzi do tej ostatniej jedynki dopiero może wszystko wymnożyć, czyli na końcu po prostu zwracasz w jednej instancji 1, a ta jedynka jest argumentem dla silnia(3-1)*1

Jest to zawiłe, dobrze jest na początku sobie na kartce to rozpisać, a potem chyba w ogóle nie korzystać z rekurencji.

Comments

no okej ale dlaczego w takim razie nie wypisuje 1 tylko poprawny wynik?
Czy return nie odpowiada za zwracanie wartości funkcji i przerwanie jej dzialania?

---

Bo 1 zwróciła funkcja silnia(2-1) i potem ona poszła do wyrażenia wynik=2* (1)<--ta jedynka jest wynikiem silnia(2-1). Następnie zwracasz "wynik"dla następnego przypisania wynik=(3-1)*2. I tak aż dojdzie do "liczba"

Answer 2

Ta linijka:

Int wynik = liczba*silnia(liczba-1);

Jest rozwijana dla 6 do:

= 6*silnia(5)*silnia(4)*silnia(3)*silnia(2)*silnia(1)

To return 1 konczy dalsze "rozwiianie" bo przestajemy wolac silnie.

Comments

no okej ale dlaczego w takim razie nie wypisuje 1 tylko poprawny wynik?
Czy return nie odpowiada za zwracanie wartości funkcji i przerwanie jej dzialania?

Answer 3

Już chyba wiem o co chodzi.

Podchodziłem do problemu ze złym rozumowaniem tego mechanizmu.
Wszystko już rozumiem, w momencie wykonywania tego kodu odpala się drugi wątek, w którym całość obliczeń jest wykonywana, następnie po zakończeniu dostaje wynik.

Comments

w momencie wykonywania tego kodu odpala się drugi wątek

To nie jest nowy wątek. To wywołanie funkcji, jak każdej innej - jedyny szczegół, że to ta sama funkcja.

Czy return nie odpowiada za zwracanie wartości funkcji i przerwanie jej dzialania?

Tak jest - zwraca z obecnie wywoływanej funkcji. Ale silnia() wywołuje samo siebie wiele razy; return wychodzi tylko z jednej "warstwy" wywołań.

Answer 4

Jest taki stary (z brodą) dowcip że rekurencję się zrozumie jak się zrozumie rekurencję. Problem w tym że śmieją się z tego dowcipu tylko Ci którzy rozumieją rekurencję ;)

A poważnie. Myślę że lepiej rekurencję wytłumaczyć na bardzo prostym przykładzie. Sam tak byłem uczony :)

Jak wiadomo "napis w stylu C", składa się z liter ASCII zakończonych kodem '\0' (czyli znakiem o wartości 0-zero). Jak więc policzyć długość napisu?

Warunek brzegowy to sytuacja gdy napis jest już pusty. Zawiera sam znak 0. Wtedy należy zwrócić wartość licznika który będzie miał wartość 0.

Jeśli jednak zawiera znak "niezerowy", należy inkrementować licznik i wywołać samego siebie ze wskazaniem na następny znak.

Bardzo szkolny przykład:

#include <iostream>
#include <cstdio>

size_t strlen_recur(const char * str, std::size_t counter)
{
    if (*str == '\0') {
        return counter;
    }
    return strlen_recur(++str, counter + 1);
}

int main()
{
    const char * msg = "Ala ma kota";
    std::cout << "Napis: |" << msg << "|, ma długość " 
        << strlen_recur(msg, 0) << " znaków.\n";
}

W linijce 8 masz wywołanie rekurencyjne. Funkcja "sama siebie woła".

Teraz jedynie aby łatwiej można wywołać funkcję i ew. nie zapomnieć o zerowaniu licznika, można dodać do niego wartość domyślną. Tu w pełnym brzmieniu:

#include <iostream>
#include <cstdio>

size_t strlen_recur(const char * str, std::size_t counter = 0)
{
    if (*str == '\0') {
        return counter;
    }
    return strlen_recur(++str, counter + 1);
}

int main()
{
    const char * msg = "Ala ma kota";
    std::cout << "Napis: |" << msg << "|, ma długość " 
        << strlen_recur(msg) << " znaków.\n";
}

Proponuję teraz przećwiczyć sam sposób programowania na następujących przykładach:

1. Przy przekazaniu do funkcji adresu tablicy i jej długości, zwrócić ilość występujących w niej liczb parzystych.
Podpowiedź: Funkcja licząca będzie miała 3 parametry. Adres pierwszego elementu (np. int *), ilość danych (np. std::size_t ilosc), ilość występujących elementów parzystych (np. std::size_t parzyste_ilosc).

2. Przy przekazaniu do funkcji adresu tablicy i jej długości, wyprowadzić na ekran:
- elementy w kolejności ich występowania
- elementy odwrotnie do kolejności ich występowania

... itd.. (mam tych ćwiczeń oczywiście więcej... )

... rzecz jasna wszystko zrób rekurencyjnie :)