Funkcja rekurencyjna - zadanie maturalne

Question

Dana jest następująca funkcja rekurencyjna:

Dane:

x — liczba całkowita,

n — dodatnia liczba całkowita.

 

funkcja F(x, n)

      jeżeli n = 1
          podaj wynik x i zakończ

       w przeciwnym razie
             jeżeli n mod 3 = 0
                  k ← F(x, n div 3)
                  podaj wynik k*k*k i zakończ

           w przeciwnym razie
                podaj wynik x*F(x, n-1) i zakończ

 

Podaj wszystkie wywołania rekurencyjne funkcji F oraz obliczany po każdym wywołaniu wynik, jeśli na początku wywołamy F(2, 10).

I teraz pytanie - jak się do tego zabrać? Skąd mam wiedzieć, że tutaj trzeba potęgować? Według tego wynik wychodzi 2*F(2,9). I co ja mam z tym dalej zrobić?

To dopiero moje pierwsze styczności z tymi funkcjami, także proszę o wyrozumiałość

Answer 1

Jeśli wiesz, że masz już 2 * F(2,9) to teraz robisz to samo z F(2,9) co zrobiłeś z F(2,10).

Czyli wywołanie pierwsze -> 2 * F(2,9)

Wywołanie drugie -> to co wyjdzie z F(2,9) (z racji że wpada n mod 3 = 0 to liczysz k i podnosisz do potęgi 3). Obliczenie k też nie będzie proste, ale metodę już znasz

.

Ogólnie rekurencja oznacza tak potocznie mówiąc ponowne odwołanie -> wykonujesz funkcję w kółko aż dojdziesz do moment, gdzie w instrukcji jest koniec.

Rekurencja, z którą się spotkałeś na pewno  to wyznaczanie NWW i NWD z matematyki - rozkład na czynniki pierwsze robisz tak długo, aż nie dojdziesz do jedynki. "Funkcja" każe Ci najpierw dzielić przez 2 potem przez 3 itd... aż wynik będzie równy 1.

W Twoim przypadku funkcja każe robić co innego, ale zasada działania jest taka sama.