{"id":1450,"date":"2026-04-21T20:29:00","date_gmt":"2026-04-21T18:29:00","guid":{"rendered":"https:\/\/trzykody.pl\/?p=1450"},"modified":"2026-04-21T20:29:02","modified_gmt":"2026-04-21T18:29:02","slug":"ciag-fibonacciego-python-w-praktyce-rekurencja-iteracja-i-analiza-zlozonosci-algorytmu","status":"publish","type":"post","link":"https:\/\/trzykody.pl\/index.php\/2026\/04\/21\/ciag-fibonacciego-python-w-praktyce-rekurencja-iteracja-i-analiza-zlozonosci-algorytmu\/","title":{"rendered":"Ci\u0105g Fibonacciego Python w praktyce &#8211; rekurencja, iteracja i analiza z\u0142o\u017cono\u015bci algorytmu"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Liczby Fibonacciego s\u0105 jednym z najcz\u0119\u015bciej u\u017cywanych przyk\u0142ad\u00f3w podczas nauki algorytmiki, poniewa\u017c na prostym schemacie pokazuj\u0105 kilka wa\u017cnych rzeczy naraz: zale\u017cno\u015b\u0107 rekurencyjn\u0105, koszt oblicze\u0144, pami\u0119\u0107 programu i r\u00f3\u017cnic\u0119 mi\u0119dzy rozwi\u0105zaniem eleganckim a rozwi\u0105zaniem praktycznym. Ten temat wraca zar\u00f3wno na studiach, jak i podczas rozm\u00f3w technicznych, bo dobrze ujawnia spos\u00f3b my\u015blenia programisty. Dobrym punktem wej\u015bcia do takich \u0107wicze\u0144 jest <strong>Ci\u0105g Fibonacciego Python<\/strong>.<\/p>\n\n\n\n<div class=\"wp-block-rank-math-toc-block\" id=\"rank-math-toc\"><h2>Spis Tre\u015bci<\/h2><nav><ol><li><a href=\"#dlaczego-ciag-fibonacciego-python-dobrze-pokazuje-roznice-miedzy-rekurencja-a-iteracja\">Dlaczego Ci\u0105g Fibonacciego Python dobrze pokazuje r\u00f3\u017cnic\u0119 mi\u0119dzy rekurencj\u0105 a iteracj\u0105<\/a><ol><li><a href=\"#wzor-matematyczny-i-podstawowe-zaleznosci\">Wz\u00f3r matematyczny i podstawowe zale\u017cno\u015bci<\/a><\/li><li><a href=\"#najprostsza-implementacja-rekurencyjna-w-python\">Najprostsza implementacja rekurencyjna w Python<\/a><\/li><li><a href=\"#wersja-iteracyjna-znacznie-blizsza-praktyce\">Wersja iteracyjna znacznie bli\u017csza praktyce<\/a><\/li><\/ol><\/li><li><a href=\"#jak-ciag-fibonacciego-python-ujawnia-koszt-czasowy-i-problem-nadmiarowych-obliczen\">Jak Ci\u0105g Fibonacciego Python ujawnia koszt czasowy i problem nadmiarowych oblicze\u0144<\/a><ol><li><a href=\"#porownanie-podejsc\">Por\u00f3wnanie podej\u015b\u0107<\/a><\/li><li><a href=\"#memoizacja-jako-rozwiazanie-posrednie\">Memoizacja jako rozwi\u0105zanie po\u015brednie<\/a><\/li><li><a href=\"#ten-sam-problem-w-c\">Ten sam problem w C<\/a><\/li><li><a href=\"#wersja-iteracyjna-w-c\">Wersja iteracyjna w C++<\/a><\/li><\/ol><\/li><li><a href=\"#zastosowania-poza-zadaniami-akademickimi-i-zaleznosc-z-programowaniem-dynamicznym\">Zastosowania poza zadaniami akademickimi i zale\u017cno\u015b\u0107 z programowaniem dynamicznym<\/a><\/li><li><a href=\"#praktyczne-zastosowania-i-testowanie-kodu-na-przykladzie-ciag-fibonacciego-python\">Praktyczne zastosowania i testowanie kodu na przyk\u0142adzie Ci\u0105g Fibonacciego Python<\/a><ol><li><a href=\"#prosty-test-kontrolny\">Prosty test kontrolny<\/a><\/li><li><a href=\"#krotki-test-w-python\">Kr\u00f3tki test w Python<\/a><\/li><\/ol><\/li><li><a href=\"#na-co-uwazac-przy-pracy-z-duzymi-wartosciami-n-i-przy-zadaniach-rekrutacyjnych\">Na co uwa\u017ca\u0107 przy pracy z du\u017cymi warto\u015bciami n i przy zadaniach rekrutacyjnych<\/a><ol><li><a href=\"#wersja-z-modulo\">Wersja z modulo<\/a><\/li><\/ol><\/li><li><a href=\"#faq\">FAQ<\/a><ol><li><a href=\"#czy-rekurencja-zawsze-jest-gorsza-od-iteracji\">Czy rekurencja zawsze jest gorsza od iteracji?<\/a><\/li><li><a href=\"#dlaczego-fib-40-dziala-tak-dlugo-w-wersji-naiwnej\">Dlaczego fib(40) dzia\u0142a tak d\u0142ugo w wersji naiwnej?<\/a><\/li><li><a href=\"#czy-memoizacja-zawsze-jest-najlepszym-wyborem\">Czy memoizacja zawsze jest najlepszym wyborem?<\/a><\/li><li><a href=\"#czy-warto-uczyc-sie-tego-przykladu-skoro-rzadko-wystepuje-w-realnym-projekcie\">Czy warto uczy\u0107 si\u0119 tego przyk\u0142adu, skoro rzadko wyst\u0119puje w realnym projekcie?<\/a><\/li><li><a href=\"#czy-python-jest-dobrym-jezykiem-do-takich-cwiczen\">Czy Python jest dobrym j\u0119zykiem do takich \u0107wicze\u0144?<\/a><\/li><\/ol><\/li><\/ol><\/nav><\/div>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"dlaczego-ciag-fibonacciego-python-dobrze-pokazuje-roznice-miedzy-rekurencja-a-iteracja\">Dlaczego Ci\u0105g Fibonacciego Python dobrze pokazuje r\u00f3\u017cnic\u0119 mi\u0119dzy rekurencj\u0105 a iteracj\u0105<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Ci\u0105g Fibonacciego definiuje si\u0119 bardzo prosto. Dwa pierwsze wyrazy to najcz\u0119\u015bciej:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>F(0) = 0<\/li>\n\n\n\n<li>F(1) = 1<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Ka\u017cdy kolejny wyraz jest sum\u0105 dw\u00f3ch poprzednich:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>F(n) = F(n &#8211; 1) + F(n &#8211; 2)<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Powstaje wi\u0119c sekwencja:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">0, 1, 1, 2, 3, 5, 8, 13, 21, 34&#8230;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">To wygl\u0105da niewinnie, ale w\u0142a\u015bnie tutaj dobrze wida\u0107 r\u00f3\u017cnic\u0119 mi\u0119dzy zapisem matematycznym a rzeczywistym wykonaniem programu. Matematycznie definicja rekurencyjna jest naturalna. Programistycznie mo\u017ce by\u0107 bardzo kosztowna.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Najcz\u0119stszy b\u0142\u0105d pocz\u0105tkuj\u0105cych polega na za\u0142o\u017ceniu, \u017ce skoro zapis rekurencyjny jest kr\u00f3tki i \u201e\u0142adny\u201d, to b\u0119dzie te\u017c najlepszy wydajno\u015bciowo. W praktyce zwykle jest odwrotnie.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"wzor-matematyczny-i-podstawowe-zaleznosci\">Wz\u00f3r matematyczny i podstawowe zale\u017cno\u015bci<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Element<\/th><th>Zapis<\/th><\/tr><\/thead><tbody><tr><td>Definicja pocz\u0105tkowa<\/td><td>F(0) = 0<\/td><\/tr><tr><td>Definicja pocz\u0105tkowa<\/td><td>F(1) = 1<\/td><\/tr><tr><td>Zale\u017cno\u015b\u0107 rekurencyjna<\/td><td>F(n) = F(n &#8211; 1) + F(n &#8211; 2)<\/td><\/tr><tr><td>Przyk\u0142ad<\/td><td>F(5) = F(4) + F(3) = 3 + 2 = 5<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"najprostsza-implementacja-rekurencyjna-w-python\">Najprostsza implementacja rekurencyjna w Python<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>J\u0119zyk<\/th><th>Kod<\/th><\/tr><\/thead><tbody><tr><td>Python<\/td><td><code>def fib(n):<\/code><br><code>if n &lt;= 1:<\/code><br><code>return n<\/code><br><code>return fib(n - 1) + fib(n - 2)<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Kod jest kr\u00f3tki i dobrze oddaje definicj\u0119 matematyczn\u0105. Problem pojawia si\u0119 przy wi\u0119kszych warto\u015bciach.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Dla <code>fib(40)<\/code> program wykonuje ogromn\u0105 liczb\u0119 powt\u00f3rzonych oblicze\u0144. <code>fib(30)<\/code> jest liczone wielokrotnie, podobnie <code>fib(29)<\/code>, <code>fib(28)<\/code> i tak dalej. Proces zaczyna przypomina\u0107 lawin\u0119.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"wersja-iteracyjna-znacznie-blizsza-praktyce\">Wersja iteracyjna znacznie bli\u017csza praktyce<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>J\u0119zyk<\/th><th>Kod<\/th><\/tr><\/thead><tbody><tr><td>Python<\/td><td><code>def fib_iter(n):<\/code><br><code>a = 0<\/code><br><code>b = 1<\/code><br><code>for i in range(n):<\/code><br><code>a, b = b, a + b<\/code><br><code>return a<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Tutaj nie ma powt\u00f3rnych oblicze\u0144. Program przechodzi po kolejnych warto\u015bciach raz i ko\u0144czy dzia\u0142anie w czasie liniowym.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">To jest wersja, kt\u00f3r\u0105 realnie stosuje si\u0119 cz\u0119\u015bciej.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"jak-ciag-fibonacciego-python-ujawnia-koszt-czasowy-i-problem-nadmiarowych-obliczen\">Jak Ci\u0105g Fibonacciego Python ujawnia koszt czasowy i problem nadmiarowych oblicze\u0144<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Analiza z\u0142o\u017cono\u015bci to moment, w kt\u00f3rym ten przyk\u0142ad przestaje by\u0107 tylko \u0107wiczeniem akademickim.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Rekurencja bez pami\u0119ci podr\u0119cznej ma z\u0142o\u017cono\u015b\u0107 wyk\u0142adnicz\u0105, w przybli\u017ceniu:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">O(2^n)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">To oznacza bardzo szybki wzrost czasu wykonania. R\u00f3\u017cnica mi\u0119dzy <code>n = 20<\/code> a <code>n = 40<\/code> nie jest \u201edwa razy wi\u0119ksza\u201d, tylko wielokrotnie wi\u0119ksza.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wersja iteracyjna dzia\u0142a w:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">O(n)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">i zu\u017cywa sta\u0142\u0105 ilo\u015b\u0107 pami\u0119ci.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">To ogromna r\u00f3\u017cnica.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"porownanie-podejsc\">Por\u00f3wnanie podej\u015b\u0107<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Metoda<\/th><th>Z\u0142o\u017cono\u015b\u0107 czasowa<\/th><th>Z\u0142o\u017cono\u015b\u0107 pami\u0119ciowa<\/th><th>Praktyczne u\u017cycie<\/th><\/tr><\/thead><tbody><tr><td>Rekurencja naiwna<\/td><td>O(2^n)<\/td><td>O(n)<\/td><td>g\u0142\u00f3wnie nauka<\/td><\/tr><tr><td>Iteracja<\/td><td>O(n)<\/td><td>O(1)<\/td><td>bardzo praktyczne<\/td><\/tr><tr><td>Rekurencja z memoizacj\u0105<\/td><td>O(n)<\/td><td>O(n)<\/td><td>dobra r\u00f3wnowaga<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"memoizacja-jako-rozwiazanie-posrednie\">Memoizacja jako rozwi\u0105zanie po\u015brednie<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Memoizacja polega na zapami\u0119tywaniu wcze\u015bniej obliczonych wynik\u00f3w. Dzi\u0119ki temu rekurencja nie liczy tych samych warto\u015bci wiele razy.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>J\u0119zyk<\/th><th>Kod<\/th><\/tr><\/thead><tbody><tr><td>Python<\/td><td><code>memo = {}<\/code><br><br><code>def fib_memo(n):<\/code><br><code>if n in memo:<\/code><br><code>return memo[n]<\/code><br><code>if n &lt;= 1:<\/code><br><code>return n<\/code><br><code>memo[n] = fib_memo(n - 1) + fib_memo(n - 2)<\/code><br><code>return memo[n]<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">To rozwi\u0105zanie jest cz\u0119sto wybierane na zaj\u0119ciach z dynamic programming, bo dobrze pokazuje ide\u0119 pami\u0119ci podr\u0119cznej.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ten-sam-problem-w-c\">Ten sam problem w C<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>J\u0119zyk<\/th><th>Kod<\/th><\/tr><\/thead><tbody><tr><td>C<\/td><td><code>#include &lt;stdio.h&gt;<\/code><br><br><code>int fib(int n)<\/code><br><code>{<\/code><br><code>if (n &lt;= 1)<\/code><br><code>return n;<\/code><br><code>return fib(n - 1) + fib(n - 2);<\/code><br><code>}<\/code><br><br><code>int main()<\/code><br><code>{<\/code><br><code>printf(\"%d\\n\", fib(10));<\/code><br><code>return 0;<\/code><br><code>}<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">W C problem wydajno\u015bci jest dok\u0142adnie taki sam. J\u0119zyk nie rozwi\u0105zuje z\u0142ej strategii algorytmicznej.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"wersja-iteracyjna-w-c\">Wersja iteracyjna w C++<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>J\u0119zyk<\/th><th>Kod<\/th><\/tr><\/thead><tbody><tr><td>C++<\/td><td><code>#include &lt;iostream&gt;<\/code><br><code>using namespace std;<\/code><br><br><code>int fib(int n)<\/code><br><code>{<\/code><br><code>int a = 0;<\/code><br><code>int b = 1;<\/code><br><code>for (int i = 0; i &lt; n; i++)<\/code><br><code>{<\/code><br><code>int temp = a;<\/code><br><code>a = b;<\/code><br><code>b = temp + b;<\/code><br><code>}<\/code><br><code>return a;<\/code><br><code>}<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Tu dobrze wida\u0107 proceduralny, przewidywalny przebieg programu bez kosztownego rozga\u0142\u0119ziania.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"zastosowania-poza-zadaniami-akademickimi-i-zaleznosc-z-programowaniem-dynamicznym\">Zastosowania poza zadaniami akademickimi i zale\u017cno\u015b\u0107 z programowaniem dynamicznym<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Sam ci\u0105g rzadko jest celem biznesowym projektu. Nie buduje si\u0119 systemu p\u0142atno\u015bci tylko po to, \u017ceby liczy\u0107 Fibonacciego. Wa\u017cne jest jednak to, czego ten przyk\u0142ad uczy.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Najwa\u017cniejsza lekcja to rozpoznawanie problem\u00f3w z nak\u0142adaj\u0105cymi si\u0119 podproblemami.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Je\u017celi algorytm wielokrotnie liczy te same fragmenty pracy, warto sprawdzi\u0107:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>czy mo\u017cna u\u017cy\u0107 memoizacji<\/li>\n\n\n\n<li>czy da si\u0119 przej\u015b\u0107 na bottom-up<\/li>\n\n\n\n<li>czy iteracja b\u0119dzie prostsza i szybsza<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">To jest dok\u0142adnie fundament programowania dynamicznego.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Podobny mechanizm pojawia si\u0119 w:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>obliczaniu najkr\u00f3tszych \u015bcie\u017cek<\/li>\n\n\n\n<li>problemie plecakowym<\/li>\n\n\n\n<li>obliczaniu odleg\u0142o\u015bci Levenshteina<\/li>\n\n\n\n<li>analizie sekwencji DNA<\/li>\n\n\n\n<li>optymalizacji koszt\u00f3w i harmonogram\u00f3w<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Student zwykle widzi tylko \u201ekolejny przyk\u0142ad z Fibonaccim\u201d, ale p\u00f3\u017aniej ten sam schemat wraca w systemach produkcyjnych.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"praktyczne-zastosowania-i-testowanie-kodu-na-przykladzie-ciag-fibonacciego-python\">Praktyczne zastosowania i testowanie kodu na przyk\u0142adzie Ci\u0105g Fibonacciego Python<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Samo napisanie funkcji to za ma\u0142o. Trzeba jeszcze sprawdzi\u0107 poprawno\u015b\u0107.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Typowe b\u0142\u0119dy:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>z\u0142e warunki pocz\u0105tkowe<\/li>\n\n\n\n<li>przesuni\u0119cie indeks\u00f3w (<code>F(1)=1<\/code> czy <code>F(1)=0<\/code>)<\/li>\n\n\n\n<li>przepe\u0142nienie typu liczbowego w C\/C++<\/li>\n\n\n\n<li>mylenie rekurencji z wydajno\u015bci\u0105<\/li>\n\n\n\n<li>brak test\u00f3w dla ma\u0142ych warto\u015bci<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">B\u0142\u0105d w definicji pocz\u0105tkowej powoduje, \u017ce ca\u0142y ci\u0105g staje si\u0119 inny, a program nadal \u201ewygl\u0105da poprawnie\u201d.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"prosty-test-kontrolny\">Prosty test kontrolny<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Wej\u015bcie<\/th><th>Oczekiwany wynik<\/th><\/tr><\/thead><tbody><tr><td>0<\/td><td>0<\/td><\/tr><tr><td>1<\/td><td>1<\/td><\/tr><tr><td>2<\/td><td>1<\/td><\/tr><tr><td>3<\/td><td>2<\/td><\/tr><tr><td>5<\/td><td>5<\/td><\/tr><tr><td>10<\/td><td>55<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"krotki-test-w-python\">Kr\u00f3tki test w Python<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>J\u0119zyk<\/th><th>Kod<\/th><\/tr><\/thead><tbody><tr><td>Python<\/td><td><code>for i in range(11):<\/code><br><code>print(i, fib_iter(i))<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Takie testy s\u0105 banalne, ale oszcz\u0119dzaj\u0105 godziny szukania b\u0142\u0119du p\u00f3\u017aniej.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">W praktyce warto te\u017c mierzy\u0107 czas wykonania. Program, kt\u00f3ry daje poprawny wynik po 40 sekundach, cz\u0119sto jest po prostu z\u0142y projektowo.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"na-co-uwazac-przy-pracy-z-duzymi-wartosciami-n-i-przy-zadaniach-rekrutacyjnych\">Na co uwa\u017ca\u0107 przy pracy z du\u017cymi warto\u015bciami n i przy zadaniach rekrutacyjnych<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Dla du\u017cych <code>n<\/code> pojawia si\u0119 kolejny problem: rozmiar liczby.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Python radzi sobie dobrze, poniewa\u017c obs\u0142uguje liczby ca\u0142kowite o arbitralnej d\u0142ugo\u015bci. W C i C++ standardowe typy maj\u0105 ograniczenia.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Przyk\u0142adowo:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>int<\/code> zwykle ko\u0144czy si\u0119 w okolicach 2 miliard\u00f3w<\/li>\n\n\n\n<li><code>long long<\/code> daje wi\u0119kszy zakres, ale nadal sko\u0144czony<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Dla wi\u0119kszych indeks\u00f3w trzeba u\u017cywa\u0107 bibliotek big integer albo liczy\u0107 modulo, je\u015bli zadanie tego wymaga.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">W zadaniach rekrutacyjnych bardzo cz\u0119sto pojawia si\u0119 wariant:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u201eOblicz n-ty wyraz modulo 1 000 000 007\u201d<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">To ju\u017c nie jest szkolny przyk\u0142ad, tylko test znajomo\u015bci ogranicze\u0144 pami\u0119ci i czasu.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"wersja-z-modulo\">Wersja z modulo<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>J\u0119zyk<\/th><th>Kod<\/th><\/tr><\/thead><tbody><tr><td>Python<\/td><td><code>def fib_mod(n):<\/code><br><code>mod = 1000000007<\/code><br><code>a = 0<\/code><br><code>b = 1<\/code><br><code>for i in range(n):<\/code><br><code>a, b = b % mod, (a + b) % mod<\/code><br><code>return a<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Takie podej\u015bcie pojawia si\u0119 bardzo cz\u0119sto w konkursach algorytmicznych.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"faq\">FAQ<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"czy-rekurencja-zawsze-jest-gorsza-od-iteracji\">Czy rekurencja zawsze jest gorsza od iteracji?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Nie. Rekurencja bywa czytelniejsza i naturalna dla problem\u00f3w drzewiastych, np. DFS czy parsowanie struktur. Problem pojawia si\u0119 wtedy, gdy powtarza te same obliczenia bez kontroli.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"dlaczego-fib-40-dziala-tak-dlugo-w-wersji-naiwnej\">Dlaczego <code>fib(40)<\/code> dzia\u0142a tak d\u0142ugo w wersji naiwnej?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Bo funkcja wielokrotnie liczy te same warto\u015bci. <code>fib(38)<\/code> i <code>fib(37)<\/code> uruchamiaj\u0105 kolejne identyczne ga\u0142\u0119zie oblicze\u0144, a ich liczba ro\u015bnie wyk\u0142adniczo.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"czy-memoizacja-zawsze-jest-najlepszym-wyborem\">Czy memoizacja zawsze jest najlepszym wyborem?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Nie zawsze. Czasem prostsza i szybsza b\u0119dzie iteracja bottom-up. Memoizacja jest \u015bwietna dydaktycznie i wygodna przy bardziej z\u0142o\u017conych zale\u017cno\u015bciach.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"czy-warto-uczyc-sie-tego-przykladu-skoro-rzadko-wystepuje-w-realnym-projekcie\">Czy warto uczy\u0107 si\u0119 tego przyk\u0142adu, skoro rzadko wyst\u0119puje w realnym projekcie?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Tak, bo nie chodzi o sam ci\u0105g, tylko o spos\u00f3b my\u015blenia algorytmicznego. Ten sam schemat wraca p\u00f3\u017aniej w du\u017co powa\u017cniejszych problemach.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"czy-python-jest-dobrym-jezykiem-do-takich-cwiczen\">Czy Python jest dobrym j\u0119zykiem do takich \u0107wicze\u0144?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Tak, szczeg\u00f3lnie na pocz\u0105tku. Kod jest kr\u00f3tki, \u0142atwo testowa\u0107 przypadki brzegowe i nie trzeba od razu walczy\u0107 z ograniczeniami typ\u00f3w liczbowych.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Ci\u0105g Fibonacciego jest prosty tylko na pierwszy rzut oka. W rzeczywisto\u015bci to bardzo dobry test rozumienia algorytm\u00f3w, z\u0142o\u017cono\u015bci i jako\u015bci decyzji programistycznych. W\u0142a\u015bnie dlatego wraca tak cz\u0119sto i w\u0142a\u015bnie dlatego warto go pisa\u0107 wi\u0119cej ni\u017c raz.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><em>\u0179r\u00f3d\u0142o Foto: Freepik<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Liczby Fibonacciego s\u0105 jednym z najcz\u0119\u015bciej u\u017cywanych przyk\u0142ad\u00f3w podczas nauki algorytmiki, poniewa\u017c na prostym schemacie pokazuj\u0105 kilka wa\u017cnych rzeczy naraz: zale\u017cno\u015b\u0107 rekurencyjn\u0105, koszt oblicze\u0144, pami\u0119\u0107 programu i r\u00f3\u017cnic\u0119 mi\u0119dzy rozwi\u0105zaniem eleganckim a rozwi\u0105zaniem praktycznym. Ten temat wraca zar\u00f3wno na studiach, jak i podczas rozm\u00f3w technicznych, bo dobrze ujawnia spos\u00f3b my\u015blenia programisty. Dobrym punktem wej\u015bcia do takich \u0107wicze\u0144 jest Ci\u0105g Fibonacciego Python. Dlaczego Ci\u0105g Fibonacciego Python dobrze pokazuje r\u00f3\u017cnic\u0119 mi\u0119dzy rekurencj\u0105 a iteracj\u0105 Ci\u0105g Fibonacciego definiuje si\u0119 bardzo prosto. Dwa pierwsze wyrazy to najcz\u0119\u015bciej: Ka\u017cdy kolejny wyraz jest sum\u0105 dw\u00f3ch poprzednich: Powstaje wi\u0119c sekwencja: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34&#8230; To wygl\u0105da niewinnie, ale w\u0142a\u015bnie tutaj dobrze wida\u0107 r\u00f3\u017cnic\u0119 mi\u0119dzy zapisem matematycznym a rzeczywistym wykonaniem programu. Matematycznie definicja rekurencyjna jest naturalna. Programistycznie mo\u017ce by\u0107 bardzo kosztowna. Najcz\u0119stszy b\u0142\u0105d pocz\u0105tkuj\u0105cych polega na za\u0142o\u017ceniu, \u017ce skoro zapis rekurencyjny jest kr\u00f3tki i \u201e\u0142adny\u201d, to b\u0119dzie te\u017c najlepszy wydajno\u015bciowo. W praktyce zwykle jest odwrotnie. Wz\u00f3r matematyczny i podstawowe zale\u017cno\u015bci Element Zapis Definicja pocz\u0105tkowa F(0) = 0 Definicja pocz\u0105tkowa F(1) = 1 Zale\u017cno\u015b\u0107 rekurencyjna F(n) = F(n &#8211; 1) + F(n &#8211; 2) Przyk\u0142ad F(5) = F(4) + F(3) = 3 + 2 = 5 Najprostsza implementacja rekurencyjna w Python J\u0119zyk Kod Python def fib(n):if n &lt;= 1:return nreturn fib(n &#8211; 1) + fib(n &#8211; 2) Kod jest kr\u00f3tki i dobrze oddaje definicj\u0119 matematyczn\u0105. Problem pojawia si\u0119 przy wi\u0119kszych warto\u015bciach. Dla fib(40) program wykonuje ogromn\u0105 liczb\u0119 powt\u00f3rzonych oblicze\u0144. fib(30) jest liczone wielokrotnie, podobnie fib(29), fib(28) i tak dalej. Proces zaczyna przypomina\u0107 lawin\u0119. Wersja iteracyjna znacznie bli\u017csza praktyce J\u0119zyk Kod Python def fib_iter(n):a = 0b = 1for i in range(n):a, b = b, a + breturn a Tutaj nie ma powt\u00f3rnych oblicze\u0144. Program przechodzi po kolejnych warto\u015bciach raz i ko\u0144czy dzia\u0142anie w czasie liniowym. To jest wersja, kt\u00f3r\u0105 realnie stosuje si\u0119 cz\u0119\u015bciej. Jak Ci\u0105g Fibonacciego Python ujawnia koszt czasowy i problem nadmiarowych oblicze\u0144 Analiza z\u0142o\u017cono\u015bci to moment, w kt\u00f3rym ten przyk\u0142ad przestaje by\u0107 tylko \u0107wiczeniem akademickim. Rekurencja bez pami\u0119ci podr\u0119cznej ma z\u0142o\u017cono\u015b\u0107 wyk\u0142adnicz\u0105, w przybli\u017ceniu: O(2^n) To oznacza bardzo szybki wzrost czasu wykonania. R\u00f3\u017cnica mi\u0119dzy n = 20 a n = 40 nie jest \u201edwa razy wi\u0119ksza\u201d, tylko wielokrotnie wi\u0119ksza. Wersja iteracyjna dzia\u0142a w: O(n) i zu\u017cywa sta\u0142\u0105 ilo\u015b\u0107 pami\u0119ci. To ogromna r\u00f3\u017cnica. Por\u00f3wnanie podej\u015b\u0107 Metoda Z\u0142o\u017cono\u015b\u0107 czasowa Z\u0142o\u017cono\u015b\u0107 pami\u0119ciowa Praktyczne u\u017cycie Rekurencja naiwna O(2^n) O(n) g\u0142\u00f3wnie nauka Iteracja O(n) O(1) bardzo praktyczne Rekurencja z memoizacj\u0105 O(n) O(n) dobra r\u00f3wnowaga Memoizacja jako rozwi\u0105zanie po\u015brednie Memoizacja polega na zapami\u0119tywaniu wcze\u015bniej obliczonych wynik\u00f3w. Dzi\u0119ki temu rekurencja nie liczy tych samych warto\u015bci wiele razy. J\u0119zyk Kod Python memo = {} def fib_memo(n):if n in memo:return memo[n]if n &lt;= 1:return nmemo[n] = fib_memo(n &#8211; 1) + fib_memo(n &#8211; 2)return memo[n] To rozwi\u0105zanie jest cz\u0119sto wybierane na zaj\u0119ciach z dynamic programming, bo dobrze pokazuje ide\u0119 pami\u0119ci podr\u0119cznej. Ten sam problem w C J\u0119zyk Kod C #include &lt;stdio.h&gt; int fib(int n){if (n &lt;= 1)return n;return fib(n &#8211; 1) + fib(n &#8211; 2);} int main(){printf(&#8222;%d\\n&#8221;, fib(10));return 0;} W C problem wydajno\u015bci jest dok\u0142adnie taki sam. J\u0119zyk nie rozwi\u0105zuje z\u0142ej strategii algorytmicznej. Wersja iteracyjna w C++ J\u0119zyk Kod C++ #include &lt;iostream&gt;using namespace std; int fib(int n){int a = 0;int b = 1;for (int i = 0; i &lt; n; i++){int temp = a;a = b;b = temp + b;}return a;} Tu dobrze wida\u0107 proceduralny, przewidywalny przebieg programu bez kosztownego rozga\u0142\u0119ziania. Zastosowania poza zadaniami akademickimi i zale\u017cno\u015b\u0107 z programowaniem dynamicznym Sam ci\u0105g rzadko jest celem biznesowym projektu. Nie buduje si\u0119 systemu p\u0142atno\u015bci tylko po to, \u017ceby liczy\u0107 Fibonacciego. Wa\u017cne jest jednak to, czego ten przyk\u0142ad uczy. Najwa\u017cniejsza lekcja to rozpoznawanie problem\u00f3w z nak\u0142adaj\u0105cymi si\u0119 podproblemami. Je\u017celi algorytm wielokrotnie liczy te same fragmenty pracy, warto sprawdzi\u0107: To jest dok\u0142adnie fundament programowania dynamicznego. Podobny mechanizm pojawia si\u0119 w: Student zwykle widzi tylko \u201ekolejny przyk\u0142ad z Fibonaccim\u201d, ale p\u00f3\u017aniej ten sam schemat wraca w systemach produkcyjnych. Praktyczne zastosowania i testowanie kodu na przyk\u0142adzie Ci\u0105g Fibonacciego Python Samo napisanie funkcji to za ma\u0142o. Trzeba jeszcze sprawdzi\u0107 poprawno\u015b\u0107. Typowe b\u0142\u0119dy: B\u0142\u0105d w definicji pocz\u0105tkowej powoduje, \u017ce ca\u0142y ci\u0105g staje si\u0119 inny, a program nadal \u201ewygl\u0105da poprawnie\u201d. Prosty test kontrolny Wej\u015bcie Oczekiwany wynik 0 0 1 1 2 1 3 2 5 5 10 55 Kr\u00f3tki test w Python J\u0119zyk Kod Python for i in range(11):print(i, fib_iter(i)) Takie testy s\u0105 banalne, ale oszcz\u0119dzaj\u0105 godziny szukania b\u0142\u0119du p\u00f3\u017aniej. W praktyce warto te\u017c mierzy\u0107 czas wykonania. Program, kt\u00f3ry daje poprawny wynik po 40 sekundach, cz\u0119sto jest po prostu z\u0142y projektowo. Na co uwa\u017ca\u0107 przy pracy z du\u017cymi warto\u015bciami n i przy zadaniach rekrutacyjnych Dla du\u017cych n pojawia si\u0119 kolejny problem: rozmiar liczby. Python radzi sobie dobrze, poniewa\u017c obs\u0142uguje liczby ca\u0142kowite o arbitralnej d\u0142ugo\u015bci. W C i C++ standardowe typy maj\u0105 ograniczenia. Przyk\u0142adowo: Dla wi\u0119kszych indeks\u00f3w trzeba u\u017cywa\u0107 bibliotek big integer albo liczy\u0107 modulo, je\u015bli zadanie tego wymaga. W zadaniach rekrutacyjnych bardzo cz\u0119sto pojawia si\u0119 wariant: \u201eOblicz n-ty wyraz modulo 1 000 000 007\u201d To ju\u017c nie jest szkolny przyk\u0142ad, tylko test znajomo\u015bci ogranicze\u0144 pami\u0119ci i czasu. Wersja z modulo J\u0119zyk Kod Python def fib_mod(n):mod = 1000000007a = 0b = 1for i in range(n):a, b = b % mod, (a + b) % modreturn a Takie podej\u015bcie pojawia si\u0119 bardzo cz\u0119sto w konkursach algorytmicznych. FAQ Czy rekurencja zawsze jest gorsza od iteracji? Nie. Rekurencja bywa czytelniejsza i naturalna dla problem\u00f3w drzewiastych, np. DFS czy parsowanie struktur. Problem pojawia si\u0119 wtedy, gdy powtarza te same obliczenia bez kontroli. Dlaczego fib(40) dzia\u0142a tak d\u0142ugo w wersji naiwnej? Bo funkcja wielokrotnie liczy te same warto\u015bci. fib(38) i fib(37) uruchamiaj\u0105 kolejne identyczne ga\u0142\u0119zie oblicze\u0144, a ich liczba ro\u015bnie wyk\u0142adniczo. Czy memoizacja zawsze jest najlepszym wyborem? Nie zawsze. Czasem prostsza i szybsza b\u0119dzie iteracja bottom-up. Memoizacja jest \u015bwietna dydaktycznie i wygodna przy bardziej z\u0142o\u017conych zale\u017cno\u015bciach. Czy warto uczy\u0107 si\u0119 tego przyk\u0142adu, skoro rzadko wyst\u0119puje w realnym projekcie? Tak, bo nie chodzi o sam ci\u0105g, tylko o spos\u00f3b my\u015blenia algorytmicznego. Ten sam schemat wraca p\u00f3\u017aniej w du\u017co powa\u017cniejszych problemach. Czy Python jest dobrym j\u0119zykiem do takich \u0107wicze\u0144? Tak, szczeg\u00f3lnie na pocz\u0105tku. Kod jest kr\u00f3tki, \u0142atwo testowa\u0107 przypadki brzegowe i nie trzeba od razu walczy\u0107 z ograniczeniami typ\u00f3w liczbowych. Ci\u0105g Fibonacciego jest prosty tylko na pierwszy rzut oka. W rzeczywisto\u015bci to bardzo dobry test rozumienia algorytm\u00f3w, z\u0142o\u017cono\u015bci i jako\u015bci decyzji programistycznych. W\u0142a\u015bnie dlatego wraca tak cz\u0119sto i w\u0142a\u015bnie dlatego warto go pisa\u0107 wi\u0119cej ni\u017c raz. \u0179r\u00f3d\u0142o Foto: Freepik<\/p>\n","protected":false},"author":1,"featured_media":1451,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[27],"tags":[],"class_list":["post-1450","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-jezyk-programowania"],"_links":{"self":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts\/1450","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/comments?post=1450"}],"version-history":[{"count":1,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts\/1450\/revisions"}],"predecessor-version":[{"id":1452,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts\/1450\/revisions\/1452"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/media\/1451"}],"wp:attachment":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/media?parent=1450"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/categories?post=1450"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/tags?post=1450"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}