Differences

This shows you the differences between two versions of the page.

--- dydaktyka:cprog:2015:recursion [2015/11/26 12:13]
pkleczek [Rekurencja]
+++ — (current)
@@ Line 1: / Line 1: @@
-====== Rekurencja ======
-Rekurencja, zwana także rekursją (//recursion//) oznacza odwoływanie się funkcji (bądź definicji) do samej siebie.
-Oto przykład prostego programu, który wykorzystuje rekurencję.
-<code c>
-#include <stdio.h>
-#include <stdlib.h>
-void gora_i_dol(int n)
-{
-    printf("Poziom %d\n", n);
-    if (n < 3) {
-        gora_i_dol(n + 1);
-    }
-    printf("POZIOM %d\n", n);
-}
-int main()
-{
-    gora_i_dol(1);
-    return 0;
-}
-</code>
-Efekt działania powyższego programu (zwróć uwagę na kolejność komunikatów):
-<code>
-Poziom 1
-Poziom 2
-Poziom 3
-POZIOM 3
-POZIOM 2
-POZIOM 1
-</code>
-Zasady rekurencji:
-  * Każdy poziom rekurencji posiada swoje własne (niezależne od innych poziomów) zmienne -- bo wywoływana jest nowa funkcja.
-  * Każdemu wywołaniu funkcji odpowiada jeden powrót. Po wykonaniu instrukcji ''return'' na końcu ostatniego (najgłębszego) poziomu rekurencji, program przechodzi do poprzedniego poziomu rekurencji (w miejsce tuż po wywołaniu funkcji) -- a nie do funkcji ''main()''.
-  * Po powrocie do miejsca wywołania funkcji wykonywane są dalsze instrukcje znajdujące się w funkcji.
-  * Chociaż każdy poziom rekurencji posiada swój własny zestaw zmiennych, kod funkcji nie jest zwielokrotniany. Po prostu podczas kolejnego wywołania tej samej funkcji program ponownie przechodzi na jej początek, tyle że z nowym zestawem zmiennych.
-:!: Jeśli do wyboru mamy napisać pętlę bądź użyć rekurencji, to ze względów wydajności lepiej użyć pętli. Rekurencja wymaga o wiele więcej pamięci na dodatkowe zestawy zmiennych! Natomiast w niektórych przypadkach użycie rekurencji jest dużo prostsze i bardziej intuicyjne...
-----
-**Przykład -- obliczanie potęgi liczby**
-Znanym z matematyki przykładem definicji rekurencyjnej jest definicja potęgi liczby naturalnej o wykładniku naturalnym:
-$$
-  a^n :=
-  \begin{cases}
-             & \mbox{dla } n = 0; \\
-    a \cdot a^{n-1} & \mbox{dla } n > 0. \\
-   \end{cases}
-   \qquad
-   a, n \in \mathbb{N}
-$$
-W poniższym programie umieszczono dodatkowe "diagnostyczne" fragmenty kodu umożliwiające śledzenie zmian wartości zmiennych. \\
-Zmienna ''poziom'' oznacza poziom rekurencji, czyli który raz z kolei funkcja wywołała samą siebie. \\
-(W dalszej części laboratorium znajduje się wersja pozbawiona tych fragmentów.)
-<code c>
-#include <stdio.h>
-#include <stdlib.h>
-int potega(int a, int n, int poziom);
-int main ()
-{
-    int a = 3;
-    int n = 2;
-    printf("\n\n %d^%d = %d\n", a, n, potega(a, n, 1));
-    return 0;
-}
-int potega(int a, int n, int poziom)
-{
-    int p;
-    printf("%*c poziom %d: n = %d\n", poziom + 1, ' ', poziom, n);
-    if (n == 0) {
-        p = 1;
-    } else {
-        p = a * potega(a, n - 1, poziom + 1);
-    }
-    printf("%*c poziom %d: p = %d\n", poziom + 1, ' ', poziom, p);
-    return p;
-}
-</code>
-Schemat ilustrujący zmianę zmiennych podczas wykonania powyższego programu (szare ramki oznaczają zmienne z wyższego poziomu //przesłonięte// przez zmienne z niższego poziomu wywołań funkcji):
-{{:dydaktyka:cprog:2015:recursion_stack.png|}}
-Używając notacji matematycznej rekurencyjne obliczanie potęgi można rozpisać następująco (cyfry rzymskie oznaczają poziom rekurencji):
-$$\text{potega($a = 3$, $n = 2$)} \colon \quad 3^2 \; \overset{I}{=} \; 3 \cdot a^1 \; \overset{II}{=} \; 3 \cdot (3 \cdot a^0) \; \overset{III/II}{=} \; 3 \cdot (3 \cdot \underbrace{1}_{a^0}) \; \overset{I}{=} \; 3 \cdot \underbrace{3}_{a^1} \; \overset{I}{=} \; 9 \; \rightarrow \text{main()}$$
-Poniżej kod programu realizującego to samo zadanie, tyle że pozbawionego części "diagnostycznej":
-<code c>
-#include <stdio.h>
-#include <stdlib.h>
-int potega(int a, int n)
-{
-    if (n == 0) {
-        return 1;
-    } else {
-        return a * potega(a, n - 1);
-    }
-}
-int main ()
-{
-    int a = 3;
-    int n = 4;
-    printf("%d^%d = %d\n", a, n, potega(a, n));
-    return 0;
-}
-</code>
-To przykład //rekurencji końcowej//, kiedy to wywołanie rekurencyjne znajduje się na końcu funkcji, tuż przed instrukcją ''return''.
-===== Jak projektować funkcję rekurencyjną? =====
-Rekurencja oznacza po prostu to, że funkcja wywołuje samą siebie. Musi jednak przypadek, w którym funkcja ta __nie__ wywoła samej siebie -- w przeciwnym razie program wpadnie w nieskończony cykl wywołań, wyczerpie dostępny limit pamięci na wywołania funkcji i... zostanie "ubity" przez system operacyjny. Przypadek, w którym funkcja nie wywołuje samej siebie, nazywamy **przypadkiem podstawowym** (w przykładzie z potęgowaniem był to przypadek dla $n = 0$). Projektowanie funkcji rekurencyjnej sprowadza się więc do wyboru rozsądnego przypadku podstawowego, a następnie upewnieniu się, że każdy ciąg wywołań funkcji w końcu osiągnie ten przypadek.
-===== Inne przykłady rekurencji... =====
-Ciekawymi przykładami definicji rekurencyjnych są [[https://pl.wikipedia.org/wiki/Fraktal|fraktale]], czyli figury samopodobne. \\
-Przykład fraktala -- zbiór Mandelbrota:\\
-{{https://upload.wikimedia.org/wikipedia/commons/2/21/Mandel_zoom_00_mandelbrot_set.jpg?400}}
-Być może podobne, nieco prostsze wzory wygenerujesz już wkrótce samodzielne, w ramach naszych zajęć! :-D
-----
-Rekurencję można wykorzystać do znajdowania [[https://pl.wikipedia.org/wiki/Najwi%C4%99kszy_wsp%C3%B3lny_dzielnik#Za_pomoc.C4.85_algorytmu_Euklidesa|największego wspólnego dzielnika]] dwóch liczb całkowitych.
-Rekurencja stanowi serce klasy algorytmów [[https://pl.wikipedia.org/wiki/Dziel_i_zwyci%C4%99%C5%BCaj|Dziel i zwyciężaj]], których idea opiera się na rekurencyjnym podziale (trudnego) problemu na (łatwe do rozwiązania) podproblemy i odpowiedniego "scalania" ich rozwiązań w celu uzyskania rozwiązania początkowego problemu.
-====== Zadania podsumowujące ======
-//Wskazówka ogólna: Czy ktoś Ci powiedział "ta funkcja ma przyjmować dokładnie jeden parametr"? //
-===== Zadanie FACT =====
-([size=10]poziom trudności:[/size] {{stars>1/4}})
-Napisz program, który obliczy silnię zadanej liczby naturalnej $n$ metodą rekurencyjną.
-Rekurencyjna definicja silni:
-$$
-  n!=\begin{cases}
-& \mbox{ dla }n=0 \\
-    n\cdot(n-1)! & \mbox{ dla }n\geqslant1
-   \end{cases}
-$$
-===== Zadanie PRI =====
-([size=10]poziom trudności:[/size] {{stars>2/4}})
-Napisz program sprawdzający, czy zadana liczba naturalna jest liczbą pierwszą -- oczywiście metodą rekurencyjną, bez użycia jakichkolwiek pętli. \\
-Przyjmij, że ani $0$ ani $1$ __nie są__ liczbami pierwszymi.
-Dla przypomnienia -- [[dydaktyka:cprog:2015:conditionals-solutions#zadanie_3|rozwiązanie tego samego problemu z użyciem pętli "for"]].
-===== Zadanie SUM =====
-([size=10]poziom trudności:[/size] {{stars>2/4}})
-Napisz funkcję, która w rekurencyjny sposób obliczy sumę cyfr liczby naturalnej przekazanej jako argument.
-//Wskazówka: Zadanie to można rozwiązać stosując podobne podejście i podobne operacje arytmetyczne, co w [[dydaktyka:cprog:2015:loops-solutions#zadanie_21|zadaniu na sumowanie cyfr]]. // \\
-===== Zadanie BIN =====
-([size=10]poziom trudności:[/size] {{stars>3/4}})
-Napisz program, który wypisze na ekranie reprezentację binarną zadanej liczby całkowitej dodatniej. Zadanie zrealizuj z użyciem rekurencji.\\
-Przykład: dla liczby ''15'' program powinien wypisać ''1111''.
-//Wskazówka 1: Wypisuj kolejne pozycje liczby binarnej -- znak po znaku (nie próbuj wypisać wszystkiego od razu). // \\
-//Wskazówka 2: Od której strony da się zacząć wypisywanie? Zastanów się, w jakiej kolejności zrealizować operacje: (1) wyświetlanie cyfry dwójkowej na ekranie i (2) ponowne wywołanie funkcji.// \\
-//Wskazówka 3: Zadanie to można rozwiązać stosując podobne podejście i podobne operacje arytmetyczne, co w [[dydaktyka:cprog:2015:loops-solutions#zadanie_21|zadaniu na sumowanie cyfr]]. // \\
-//Wskazówka 4: Do weryfikacji poprawności otrzymanych wyników możesz skorzystać z windowsowego kalkulatora w widoku programisty.//

Joanna Jaworek-Korjakowska

User Tools

Site Tools

Differences

Page Tools