{"id":1578,"date":"2026-05-15T15:37:55","date_gmt":"2026-05-15T13:37:55","guid":{"rendered":"https:\/\/trzykody.pl\/?p=1578"},"modified":"2026-05-15T15:37:56","modified_gmt":"2026-05-15T13:37:56","slug":"algorytmy-rekurencyjne","status":"publish","type":"post","link":"https:\/\/trzykody.pl\/index.php\/2026\/05\/15\/algorytmy-rekurencyjne\/","title":{"rendered":"Algorytmy rekurencyjne"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Rekurencja pojawia si\u0119 bardzo wcze\u015bnie podczas nauki programowania, ale zwykle dopiero przy wi\u0119kszych problemach wida\u0107, po co naprawd\u0119 istnieje. W prostych zadaniach cz\u0119sto da si\u0119 j\u0105 zast\u0105pi\u0107 p\u0119tl\u0105, jednak przy strukturach drzewiastych, analizie graf\u00f3w, parsowaniu sk\u0142adni albo algorytmach dziel i zwyci\u0119\u017caj kod iteracyjny szybko staje si\u0119 trudny do utrzymania. W praktyce najwi\u0119kszy problem nie polega na samym zapisaniu funkcji rekurencyjnej, tylko na zrozumieniu przep\u0142ywu wywo\u0142a\u0144, pami\u0119ci stosu oraz kosztu czasowego. W\u0142a\u015bnie dlatego <a href=\"https:\/\/trzykody.pl\/index.php\/2026\/04\/17\/co-to-jest-algorytm-przyklady\/\">algorytmy<\/a> rekurencyjne s\u0105 jednocze\u015bnie bardzo eleganckie i bardzo niebezpieczne, je\u015bli programista nie kontroluje ich g\u0142\u0119boko\u015bci oraz liczby wywo\u0142a\u0144.<\/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=\"#algorytmy-rekurencyjne-i-mechanizm-dzialania-funkcji-wywolujacej-sama-siebie-krok-po-kroku\">Algorytmy rekurencyjne i mechanizm dzia\u0142ania funkcji wywo\u0142uj\u0105cej sam\u0105 siebie krok po kroku<\/a><\/li><li><a href=\"#dlaczego-algorytmy-rekurencyjne-sa-naturalne-dla-drzew-grafow-i-problemow-dzielonych-na-mniejsze-czesci\">Dlaczego algorytmy rekurencyjne s\u0105 naturalne dla drzew, graf\u00f3w i problem\u00f3w dzielonych na mniejsze cz\u0119\u015bci<\/a><\/li><li><a href=\"#zaleznosc-miedzy-zlozonoscia-czasowa-a-liczba-wywolan-funkcji-w-rekurencji\">Zale\u017cno\u015b\u0107 mi\u0119dzy z\u0142o\u017cono\u015bci\u0105 czasow\u0105 a liczb\u0105 wywo\u0142a\u0144 funkcji w rekurencji<\/a><\/li><li><a href=\"#rekurencja-ogonowa-i-wplyw-optymalizacji-stosu-na-wydajnosc-programu\">Rekurencja ogonowa i wp\u0142yw optymalizacji stosu na wydajno\u015b\u0107 programu<\/a><\/li><li><a href=\"#algorytmy-rekurencyjne-w-sortowaniu-podziale-problemu-i-przetwarzaniu-duzych-zbiorow-danych\">Algorytmy rekurencyjne w sortowaniu, podziale problemu i przetwarzaniu du\u017cych zbior\u00f3w danych<\/a><\/li><li><a href=\"#najczestsze-bledy-spotykane-podczas-implementacji-funkcji-rekurencyjnych-i-sposoby-ich-wykrywania\">Najcz\u0119stsze b\u0142\u0119dy spotykane podczas implementacji funkcji rekurencyjnych i sposoby ich wykrywania<\/a><\/li><li><a href=\"#kiedy-rekurencja-jest-lepsza-od-iteracji-a-kiedy-prowadzi-do-problemow-wydajnosciowych\">Kiedy rekurencja jest lepsza od iteracji, a kiedy prowadzi do problem\u00f3w wydajno\u015bciowych<\/a><\/li><li><a href=\"#faq\">FAQ<\/a><ol><li><a href=\"#czy-rekurencje-da-sie-zawsze-zastapic-iteracja\">Czy rekurencj\u0119 da si\u0119 zawsze zast\u0105pi\u0107 iteracj\u0105?<\/a><\/li><li><a href=\"#dlaczego-python-ma-niski-limit-rekurencji\">Dlaczego Python ma niski limit rekurencji?<\/a><\/li><li><a href=\"#czy-rekurencja-jest-wolniejsza-od-petli\">Czy rekurencja jest wolniejsza od p\u0119tli?<\/a><\/li><li><a href=\"#gdzie-rekurencja-jest-uzywana-najczesciej\">Gdzie rekurencja jest u\u017cywana najcz\u0119\u015bciej?<\/a><\/li><li><a href=\"#dlaczego-fibonacci-jest-zlym-przykladem-rekurencji\">Dlaczego Fibonacci jest z\u0142ym przyk\u0142adem rekurencji?<\/a><\/li><li><a href=\"#co-oznacza-stack-overflow\">Co oznacza stack overflow?<\/a><\/li><li><a href=\"#czy-rekurencja-ogonowa-zawsze-jest-optymalizowana\">Czy rekurencja ogonowa zawsze jest optymalizowana?<\/a><\/li><\/ol><\/li><\/ol><\/nav><\/div>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"algorytmy-rekurencyjne-i-mechanizm-dzialania-funkcji-wywolujacej-sama-siebie-krok-po-kroku\">Algorytmy rekurencyjne i mechanizm dzia\u0142ania funkcji wywo\u0142uj\u0105cej sam\u0105 siebie krok po kroku<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Rekurencja polega na tym, \u017ce funkcja wywo\u0142uje sam\u0105 siebie, ale dla prostszego przypadku ni\u017c aktualny. Program dochodzi w ten spos\u00f3b do problemu elementarnego, kt\u00f3ry mo\u017cna rozwi\u0105za\u0107 bez kolejnych wywo\u0142a\u0144. Ten najprostszy przypadek nazywa si\u0119 warunkiem stopu.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Bez warunku stopu funkcja b\u0119dzie wywo\u0142ywa\u0107 sam\u0105 siebie w niesko\u0144czono\u015b\u0107, a\u017c do przepe\u0142nienia stosu. To jeden z najcz\u0119stszych b\u0142\u0119d\u00f3w pocz\u0105tkuj\u0105cych.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Ka\u017cde wywo\u0142anie funkcji tworzy now\u0105 ramk\u0119 stosu. Ramka zawiera:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>argumenty funkcji,<\/li>\n\n\n\n<li>zmienne lokalne,<\/li>\n\n\n\n<li>adres powrotu,<\/li>\n\n\n\n<li>stan wykonania.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Je\u017celi funkcja wywo\u0142a sam\u0105 siebie 1000 razy, na stosie znajdzie si\u0119 1000 ramek. W j\u0119zykach takich jak C czy C++ bardzo g\u0142\u0119boka rekurencja mo\u017ce zako\u0144czy\u0107 program b\u0142\u0119dem segmentation fault albo stack overflow.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Przyk\u0142ad matematyczny bardzo dobrze pokazuje ide\u0119 dzia\u0142ania. Silnia liczby <code>n<\/code> definiowana jest jako:<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><semantics><mrow><mi>n<\/mi><mo stretchy=\"false\">!<\/mo><mo>=<\/mo><mi>n<\/mi><mo>\u22c5<\/mo><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo>\u2212<\/mo><mn>1<\/mn><mo stretchy=\"false\">)<\/mo><mo stretchy=\"false\">!<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">n! = n \\cdot (n-1)!<\/annotation><\/semantics><\/math><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">oraz:<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><semantics><mrow><mn>0<\/mn><mo stretchy=\"false\">!<\/mo><mo>=<\/mo><mn>1<\/mn><\/mrow><annotation encoding=\"application\/x-tex\">0! = 1<\/annotation><\/semantics><\/math><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">To naturalna definicja rekurencyjna.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Przyk\u0142ad<\/th><th>Kod<\/th><\/tr><\/thead><tbody><tr><td>C<\/td><td><code>c\\n#include &lt;stdio.h&gt;\\n\\nint silnia(int n)\\n{\\n if(n == 0)\\n return 1;\\n\\n return n * silnia(n - 1);\\n}\\n\\nint main()\\n{\\n printf(\\\"%d\\\\n\\\", silnia(5));\\n return 0;\\n}\\n<\/code><\/td><\/tr><tr><td>C++<\/td><td><code>cpp\\n#include &lt;iostream&gt;\\nusing namespace std;\\n\\nint silnia(int n)\\n{\\n if(n == 0)\\n return 1;\\n\\n return n * silnia(n - 1);\\n}\\n\\nint main()\\n{\\n cout &lt;&lt; silnia(5) &lt;&lt; endl;\\n return 0;\\n}\\n<\/code><\/td><\/tr><tr><td>Python<\/td><td><code>python\\ndef silnia(n):\\n if n == 0:\\n return 1\\n\\n return n * silnia(n - 1)\\n\\nprint(silnia(5))\\n<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Przep\u0142yw wykonania dla <code>silnia(5)<\/code> wygl\u0105da tak:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><code>silnia(5)<\/code> czeka na wynik <code>silnia(4)<\/code><\/li>\n\n\n\n<li><code>silnia(4)<\/code> czeka na wynik <code>silnia(3)<\/code><\/li>\n\n\n\n<li><code>silnia(3)<\/code> czeka na wynik <code>silnia(2)<\/code><\/li>\n\n\n\n<li><code>silnia(2)<\/code> czeka na wynik <code>silnia(1)<\/code><\/li>\n\n\n\n<li><code>silnia(1)<\/code> czeka na wynik <code>silnia(0)<\/code><\/li>\n\n\n\n<li><code>silnia(0)<\/code> zwraca <code>1<\/code><\/li>\n\n\n\n<li>nast\u0119puje rozwijanie stosu:\n<ul class=\"wp-block-list\">\n<li><code>1 * 1<\/code><\/li>\n\n\n\n<li><code>2 * 1<\/code><\/li>\n\n\n\n<li><code>3 * 2<\/code><\/li>\n\n\n\n<li><code>4 * 6<\/code><\/li>\n\n\n\n<li><code>5 * 24<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">W praktyce bardzo wa\u017cne jest rozr\u00f3\u017cnienie dw\u00f3ch etap\u00f3w:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>schodzenia w d\u00f3\u0142 rekurencji,<\/li>\n\n\n\n<li>powrotu wynik\u00f3w.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Wiele b\u0142\u0119d\u00f3w logicznych bierze si\u0119 z niezrozumienia, \u017ce kod po wywo\u0142aniu rekurencyjnym wykona si\u0119 dopiero podczas wychodzenia ze stosu.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"dlaczego-algorytmy-rekurencyjne-sa-naturalne-dla-drzew-grafow-i-problemow-dzielonych-na-mniejsze-czesci\">Dlaczego algorytmy rekurencyjne s\u0105 naturalne dla drzew, graf\u00f3w i problem\u00f3w dzielonych na mniejsze cz\u0119\u015bci<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Rekurencja najlepiej dzia\u0142a tam, gdzie struktura danych sama ma charakter rekurencyjny. Drzewo binarne jest klasycznym przyk\u0142adem.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Ka\u017cdy w\u0119ze\u0142 drzewa:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>posiada warto\u015b\u0107,<\/li>\n\n\n\n<li>posiada lewe poddrzewo,<\/li>\n\n\n\n<li>posiada prawe poddrzewo.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Ka\u017cde poddrzewo jest znowu drzewem. To idealnie pasuje do rekurencji.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Przechodzenie drzewa preorder:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>odwied\u017a korze\u0144,<\/li>\n\n\n\n<li>przejd\u017a lewe poddrzewo,<\/li>\n\n\n\n<li>przejd\u017a prawe poddrzewo.<\/li>\n<\/ol>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Przyk\u0142ad<\/th><th>Kod<\/th><\/tr><\/thead><tbody><tr><td>C<\/td><td><code>c\\n#include &lt;stdio.h&gt;\\n#include &lt;stdlib.h&gt;\\n\\nstruct Node\\n{\\n int value;\\n struct Node* left;\\n struct Node* right;\\n};\\n\\nvoid preorder(struct Node* root)\\n{\\n if(root == NULL)\\n return;\\n\\n printf(\\\"%d \\\", root-&gt;value);\\n\\n preorder(root-&gt;left);\\n preorder(root-&gt;right);\\n}\\n<\/code><\/td><\/tr><tr><td>C++<\/td><td><code>cpp\\n#include &lt;iostream&gt;\\nusing namespace std;\\n\\nstruct Node\\n{\\n int value;\\n Node* left;\\n Node* right;\\n};\\n\\nvoid preorder(Node* root)\\n{\\n if(root == nullptr)\\n return;\\n\\n cout &lt;&lt; root-&gt;value &lt;&lt; \\\" \\\";\\n\\n preorder(root-&gt;left);\\n preorder(root-&gt;right);\\n}\\n<\/code><\/td><\/tr><tr><td>Python<\/td><td><code>python\\nclass Node:\\n def __init__(self, value):\\n self.value = value\\n self.left = None\\n self.right = None\\n\\n\\ndef preorder(root):\\n if root is None:\\n return\\n\\n print(root.value)\\n\\n preorder(root.left)\\n preorder(root.right)\\n<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Przy drzewach iteracyjna wersja cz\u0119sto wymaga w\u0142asnego stosu. Rekurencja u\u017cywa stosu funkcji procesora, wi\u0119c kod pozostaje kr\u00f3tszy.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Podobnie dzia\u0142a DFS w grafach.<\/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>python\\ngraf = {\\n 1: [2, 3],\\n 2: [4],\\n 3: [],\\n 4: []\\n}\\n\\nodwiedzone = set()\\n\\n\\ndef dfs(v):\\n if v in odwiedzone:\\n return\\n\\n odwiedzone.add(v)\\n print(v)\\n\\n for sasiad in graf[v]:\\n dfs(sasiad)\\n\\n\\ndfs(1)\\n<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Tutaj bardzo \u0142atwo pope\u0142ni\u0107 b\u0142\u0105d polegaj\u0105cy na braku tablicy odwiedzonych wierzcho\u0142k\u00f3w. W grafie zawieraj\u0105cym cykl program mo\u017ce wej\u015b\u0107 w niesko\u0144czon\u0105 rekurencj\u0119.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">W praktycznych systemach takie b\u0142\u0119dy ko\u0144cz\u0105 si\u0119:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>zawieszeniem procesu,<\/li>\n\n\n\n<li>zu\u017cyciem pami\u0119ci,<\/li>\n\n\n\n<li>restartem us\u0142ugi,<\/li>\n\n\n\n<li>utrat\u0105 stabilno\u015bci aplikacji.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"zaleznosc-miedzy-zlozonoscia-czasowa-a-liczba-wywolan-funkcji-w-rekurencji\">Zale\u017cno\u015b\u0107 mi\u0119dzy z\u0142o\u017cono\u015bci\u0105 czasow\u0105 a liczb\u0105 wywo\u0142a\u0144 funkcji w rekurencji<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Najwi\u0119kszy problem wielu algorytm\u00f3w rekurencyjnych nie wynika z samej rekurencji, ale z liczby powtarzanych oblicze\u0144.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Klasyczny przyk\u0142ad to ci\u0105g Fibonacciego.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Definicja:<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><semantics><mrow><mi>F<\/mi><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><mo>=<\/mo><mi>F<\/mi><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo>\u2212<\/mo><mn>1<\/mn><mo stretchy=\"false\">)<\/mo><mo>+<\/mo><mi>F<\/mi><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo>\u2212<\/mo><mn>2<\/mn><mo stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">F(n) = F(n-1) + F(n-2)<\/annotation><\/semantics><\/math>F(n)=F(n\u22121)+F(n\u22122)<\/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>C<\/td><td><code>c\\n#include &lt;stdio.h&gt;\\n\\nint fib(int n)\\n{\\n if(n &lt;= 1)\\n return n;\\n\\n return fib(n - 1) + fib(n - 2);\\n}\\n<\/code><\/td><\/tr><tr><td>Python<\/td><td><code>python\\ndef fib(n):\\n if n &lt;= 1:\\n return n\\n\\n return fib(n - 1) + fib(n - 2)\\n<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Dla <code>fib(40)<\/code> liczba wywo\u0142a\u0144 jest ogromna.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Przybli\u017cona z\u0142o\u017cono\u015b\u0107:<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><semantics><mrow><mi>O<\/mi><mo stretchy=\"false\">(<\/mo><msup><mn>2<\/mn><mi>n<\/mi><\/msup><mo stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">O(2^n)<\/annotation><\/semantics><\/math>Pow\u00f3d:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>fib(40)<\/code> liczy <code>fib(39)<\/code> i <code>fib(38)<\/code>,<\/li>\n\n\n\n<li><code>fib(39)<\/code> ponownie liczy <code>fib(38)<\/code>,<\/li>\n\n\n\n<li>te same wyniki s\u0105 obliczane wielokrotnie.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Drzewo wywo\u0142a\u0144 ro\u015bnie wyk\u0142adniczo.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Tutaj pojawia si\u0119 memoizacja.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Memoizacja polega na zapami\u0119tywaniu wcze\u015bniej obliczonych wynik\u00f3w.<\/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>python\\ncache = {}\\n\\n\\ndef fib(n):\\n if n in cache:\\n return cache[n]\\n\\n if n &lt;= 1:\\n return n\\n\\n wynik = fib(n - 1) + fib(n - 2)\\n cache[n] = wynik\\n\\n return wynik\\n<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Po zastosowaniu memoizacji z\u0142o\u017cono\u015b\u0107 spada do:<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><semantics><mrow><mi>O<\/mi><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">O(n)<\/annotation><\/semantics><\/math>O(n)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">R\u00f3\u017cnica jest gigantyczna:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>wersja klasyczna dla du\u017cych <code>n<\/code> mo\u017ce dzia\u0142a\u0107 kilka sekund,<\/li>\n\n\n\n<li>wersja z memoizacj\u0105 wykonuje si\u0119 praktycznie natychmiast.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">W systemach produkcyjnych niew\u0142a\u015bciwa rekurencja cz\u0119sto prowadzi do:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>przeci\u0105\u017cenia CPU,<\/li>\n\n\n\n<li>lawinowego wzrostu czasu odpowiedzi,<\/li>\n\n\n\n<li>b\u0142\u0119d\u00f3w timeout,<\/li>\n\n\n\n<li>zbyt du\u017cego zu\u017cycia pami\u0119ci.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"rekurencja-ogonowa-i-wplyw-optymalizacji-stosu-na-wydajnosc-programu\">Rekurencja ogonowa i wp\u0142yw optymalizacji stosu na wydajno\u015b\u0107 programu<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Rekurencja ogonowa wyst\u0119puje wtedy, gdy ostatni\u0105 operacj\u0105 funkcji jest wywo\u0142anie samej siebie.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Przyk\u0142ad:<\/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>C<\/td><td><code>c\\n#include &lt;stdio.h&gt;\\n\\nint suma(int n, int acc)\\n{\\n if(n == 0)\\n return acc;\\n\\n return suma(n - 1, acc + n);\\n}\\n<\/code><\/td><\/tr><tr><td>Python<\/td><td><code>python\\ndef suma(n, acc):\\n if n == 0:\\n return acc\\n\\n return suma(n - 1, acc + n)\\n<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">W niekt\u00f3rych kompilatorach mo\u017cliwa jest optymalizacja tail recursion:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>zamiast tworzy\u0107 now\u0105 ramk\u0119 stosu,<\/li>\n\n\n\n<li>funkcja nadpisuje bie\u017c\u0105c\u0105.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">To redukuje zu\u017cycie pami\u0119ci.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Problem praktyczny:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Python nie implementuje optymalizacji tail recursion,<\/li>\n\n\n\n<li>C i C++ mog\u0105 j\u0105 stosowa\u0107 zale\u017cnie od kompilatora i flag optymalizacji,<\/li>\n\n\n\n<li>Java zwykle nie gwarantuje takiej optymalizacji.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Dlatego kod poprawny teoretycznie mo\u017ce nadal przepe\u0142ni\u0107 stos.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Przyk\u0142adowe limity:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Python domy\u015blnie oko\u0142o 1000 wywo\u0142a\u0144,<\/li>\n\n\n\n<li>JVM zwykle kilka tysi\u0119cy,<\/li>\n\n\n\n<li>C\/C++ zale\u017cnie od systemu i rozmiaru stosu procesu.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">W praktyce bardzo g\u0142\u0119boka rekurencja bywa zast\u0119powana:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>w\u0142asnym stosem,<\/li>\n\n\n\n<li>iteracj\u0105,<\/li>\n\n\n\n<li>BFS zamiast DFS,<\/li>\n\n\n\n<li>dynamicznym programowaniem.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"algorytmy-rekurencyjne-w-sortowaniu-podziale-problemu-i-przetwarzaniu-duzych-zbiorow-danych\">Algorytmy rekurencyjne w sortowaniu, podziale problemu i przetwarzaniu du\u017cych zbior\u00f3w danych<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Najwa\u017cniejsze praktyczne algorytmy rekurencyjne zwykle korzystaj\u0105 z techniki dziel i zwyci\u0119\u017caj.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Schemat:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>podziel problem,<\/li>\n\n\n\n<li>rozwi\u0105\u017c mniejsze podproblemy,<\/li>\n\n\n\n<li>po\u0142\u0105cz wyniki.<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Merge sort jest klasycznym przyk\u0142adem.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Z\u0142o\u017cono\u015b\u0107:<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><semantics><mrow><mi>O<\/mi><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mi>log<\/mi><mo>\u2061<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">O(n \\log n)<\/annotation><\/semantics><\/math>O(nlogn)<\/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>python\\ndef merge_sort(tab):\\n if len(tab) &lt;= 1:\\n return tab\\n\\n mid = len(tab) \/\/ 2\\n\\n lewa = merge_sort(tab[:mid])\\n prawa = merge_sort(tab[mid:])\\n\\n wynik = []\\n\\n i = 0\\n j = 0\\n\\n while i &lt; len(lewa) and j &lt; len(prawa):\\n if lewa[i] &lt; prawa[j]:\\n wynik.append(lewa[i])\\n i += 1\\n else:\\n wynik.append(prawa[j])\\n j += 1\\n\\n wynik.extend(lewa[i:])\\n wynik.extend(prawa[j:])\\n\\n return wynik\\n<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Quick sort r\u00f3wnie\u017c wykorzystuje rekurencj\u0119.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u015arednia z\u0142o\u017cono\u015b\u0107:<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><semantics><mrow><mi>O<\/mi><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mi>log<\/mi><mo>\u2061<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">O(n \\log n)<\/annotation><\/semantics><\/math>O(nlogn)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Najgorszy przypadek:<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><semantics><mrow><mi>O<\/mi><mo stretchy=\"false\">(<\/mo><msup><mi>n<\/mi><mn>2<\/mn><\/msup><mo stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">O(n^2)<\/annotation><\/semantics><\/math>O(n2)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Najwi\u0119kszy praktyczny problem quicksorta to z\u0142y wyb\u00f3r pivota.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Dla ju\u017c posortowanych danych klasyczna implementacja mo\u017ce:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>wykonywa\u0107 ogromn\u0105 liczb\u0119 por\u00f3wna\u0144,<\/li>\n\n\n\n<li>tworzy\u0107 bardzo g\u0142\u0119bok\u0105 rekurencj\u0119,<\/li>\n\n\n\n<li>powodowa\u0107 przepe\u0142nienie stosu.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Dlatego profesjonalne implementacje u\u017cywaj\u0105:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>mediany trzech element\u00f3w,<\/li>\n\n\n\n<li>introsort,<\/li>\n\n\n\n<li>hybrydowych metod sortowania.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Rekurencja wyst\u0119puje tak\u017ce w:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>parserach sk\u0142adni,<\/li>\n\n\n\n<li>kompilatorach,<\/li>\n\n\n\n<li>analizie XML,<\/li>\n\n\n\n<li>systemach plik\u00f3w,<\/li>\n\n\n\n<li>silnikach szachowych,<\/li>\n\n\n\n<li>przeszukiwaniu przestrzeni stan\u00f3w,<\/li>\n\n\n\n<li>algorytmach AI,<\/li>\n\n\n\n<li>generowaniu kombinacji i permutacji.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Przyk\u0142ad generowania permutacji:<\/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>python\\ndef permutacje(tab, poczatek=0):\\n if poczatek == len(tab):\\n print(tab)\\n return\\n\\n for i in range(poczatek, len(tab)):\\n tab[poczatek], tab[i] = tab[i], tab[poczatek]\\n\\n permutacje(tab, poczatek + 1)\\n\\n tab[poczatek], tab[i] = tab[i], tab[poczatek]\\n\\n\\npermutacje([1, 2, 3])\\n<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Tutaj liczba mo\u017cliwych wynik\u00f3w wynosi:<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><semantics><mrow><mi>n<\/mi><mo stretchy=\"false\">!<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">n!<\/annotation><\/semantics><\/math>Dla:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>3 element\u00f3w \u2192 6 permutacji,<\/li>\n\n\n\n<li>10 element\u00f3w \u2192 3 628 800,<\/li>\n\n\n\n<li>15 element\u00f3w \u2192 ponad bilion.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">To pokazuje, \u017ce nawet poprawny algorytm rekurencyjny mo\u017ce by\u0107 praktycznie niewykonalny dla wi\u0119kszych danych.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"najczestsze-bledy-spotykane-podczas-implementacji-funkcji-rekurencyjnych-i-sposoby-ich-wykrywania\">Najcz\u0119stsze b\u0142\u0119dy spotykane podczas implementacji funkcji rekurencyjnych i sposoby ich wykrywania<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Najcz\u0119stszy problem to brak poprawnego warunku stopu.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Przyk\u0142ad b\u0142\u0119dny:<\/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>python\\ndef blad(n):\\n return blad(n - 1)\\n<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Taki kod ko\u0144czy si\u0119:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>RecursionError<\/code> w Pythonie,<\/li>\n\n\n\n<li>stack overflow w C\/C++,<\/li>\n\n\n\n<li>awari\u0105 procesu.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Drugi cz\u0119sty b\u0142\u0105d:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>z\u0142y kierunek zmiany argumentu.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Je\u017celi warto\u015b\u0107 nie zbli\u017ca si\u0119 do warunku stopu, rekurencja nigdy si\u0119 nie ko\u0144czy.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Trzeci problem:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>nadmiar kopiowania danych.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Przekazywanie du\u017cych struktur przez warto\u015b\u0107 mo\u017ce dramatycznie spowolni\u0107 program.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">W C++ lepiej stosowa\u0107 referencje:<\/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>C++<\/td><td><code>cpp\\nvoid funkcja(const vector&lt;int&gt;&amp; dane)\\n{\\n}\\n<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Kolejny problem:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>mieszanie logiki zej\u015bcia i powrotu.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Wiele os\u00f3b nie rozumie, dlaczego:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>print(n)<br>rek(n - 1)<br>print(n)<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">drukuje liczby dwa razy w r\u00f3\u017cnych momentach.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">To efekt rozwijania stosu.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Praktyczna metoda debugowania:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>wypisywanie poziomu rekurencji,<\/li>\n\n\n\n<li>wizualizacja drzewa wywo\u0142a\u0144,<\/li>\n\n\n\n<li>r\u0119czne \u015bledzenie stosu,<\/li>\n\n\n\n<li>analiza liczby wywo\u0142a\u0144 funkcji.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Dobrym \u0107wiczeniem jest rozpisanie ka\u017cdej ramki funkcji na kartce. Przy bardziej z\u0142o\u017conych algorytmach cz\u0119sto oszcz\u0119dza to godziny debugowania.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"kiedy-rekurencja-jest-lepsza-od-iteracji-a-kiedy-prowadzi-do-problemow-wydajnosciowych\">Kiedy rekurencja jest lepsza od iteracji, a kiedy prowadzi do problem\u00f3w wydajno\u015bciowych<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Rekurencja daje bardzo czytelny kod dla:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>drzew,<\/li>\n\n\n\n<li>DFS,<\/li>\n\n\n\n<li>divide and conquer,<\/li>\n\n\n\n<li>backtrackingu,<\/li>\n\n\n\n<li>parser\u00f3w.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Iteracja zwykle wygrywa przy:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>prostych p\u0119tlach,<\/li>\n\n\n\n<li>du\u017cej g\u0142\u0119boko\u015bci danych,<\/li>\n\n\n\n<li>systemach embedded,<\/li>\n\n\n\n<li>krytycznej optymalizacji pami\u0119ci,<\/li>\n\n\n\n<li>zadaniach liniowych.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Por\u00f3wnanie praktyczne:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Cecha<\/th><th>Rekurencja<\/th><th>Iteracja<\/th><\/tr><\/thead><tbody><tr><td>Czytelno\u015b\u0107<\/td><td>cz\u0119sto bardzo wysoka<\/td><td>zale\u017cy od problemu<\/td><\/tr><tr><td>Zu\u017cycie pami\u0119ci<\/td><td>wi\u0119ksze<\/td><td>mniejsze<\/td><\/tr><tr><td>Ryzyko stack overflow<\/td><td>wysokie<\/td><td>niskie<\/td><\/tr><tr><td>\u0141atwo\u015b\u0107 dla drzew<\/td><td>bardzo dobra<\/td><td>\u015brednia<\/td><\/tr><tr><td>Kontrola wykonania<\/td><td>trudniejsza<\/td><td>\u0142atwiejsza<\/td><\/tr><tr><td>Wydajno\u015b\u0107<\/td><td>czasem ni\u017csza<\/td><td>zwykle stabilniejsza<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">W praktyce do\u015bwiadczeni programi\u015bci nie traktuj\u0105 rekurencji jako \u201elepszego\u201d rozwi\u0105zania. To po prostu narz\u0119dzie.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Czasami rekurencyjny DFS jest idealny i daje kod kr\u00f3tszy o po\u0142ow\u0119. Innym razem ten sam mechanizm potrafi zabi\u0107 wydajno\u015b\u0107 aplikacji przy wi\u0119kszych danych wej\u015bciowych.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Dobry programista zwykle analizuje:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>maksymaln\u0105 g\u0142\u0119boko\u015b\u0107,<\/li>\n\n\n\n<li>z\u0142o\u017cono\u015b\u0107 czasow\u0105,<\/li>\n\n\n\n<li>zu\u017cycie pami\u0119ci,<\/li>\n\n\n\n<li>mo\u017cliwo\u015b\u0107 memoizacji,<\/li>\n\n\n\n<li>ryzyko powt\u00f3rnych oblicze\u0144,<\/li>\n\n\n\n<li>rozmiar danych wej\u015bciowych.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Rekurencja jest bardzo elegancka matematycznie, ale komputer wykonuje j\u0105 fizycznie przez stos wywo\u0142a\u0144 i pami\u0119\u0107 operacyjn\u0105. To ograniczenie zawsze trzeba bra\u0107 pod uwag\u0119 podczas projektowania algorytm\u00f3w.<\/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-rekurencje-da-sie-zawsze-zastapic-iteracja\">Czy rekurencj\u0119 da si\u0119 zawsze zast\u0105pi\u0107 iteracj\u0105?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Teoretycznie tak. Ka\u017cdy algorytm rekurencyjny mo\u017cna przepisa\u0107 iteracyjnie, zwykle przy u\u017cyciu w\u0142asnego stosu. Problem polega na tym, \u017ce kod bywa wtedy du\u017co trudniejszy do utrzymania.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"dlaczego-python-ma-niski-limit-rekurencji\">Dlaczego Python ma niski limit rekurencji?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Python celowo ogranicza g\u0142\u0119boko\u015b\u0107 wywo\u0142a\u0144, aby zmniejszy\u0107 ryzyko przepe\u0142nienia stosu i zawieszania interpretera. Domy\u015blny limit wynosi zwykle oko\u0142o 1000 wywo\u0142a\u0144.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"czy-rekurencja-jest-wolniejsza-od-petli\">Czy rekurencja jest wolniejsza od p\u0119tli?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Najcz\u0119\u015bciej tak, poniewa\u017c ka\u017cde wywo\u0142anie funkcji generuje dodatkowy koszt:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>tworzenie ramki stosu,<\/li>\n\n\n\n<li>przekazywanie argument\u00f3w,<\/li>\n\n\n\n<li>powr\u00f3t z funkcji.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Przy ma\u0142ych danych r\u00f3\u017cnica mo\u017ce by\u0107 niewielka.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"gdzie-rekurencja-jest-uzywana-najczesciej\">Gdzie rekurencja jest u\u017cywana najcz\u0119\u015bciej?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Najcz\u0119\u015bciej w:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>drzewach,<\/li>\n\n\n\n<li>grafach,<\/li>\n\n\n\n<li>parserach,<\/li>\n\n\n\n<li>algorytmach dziel i zwyci\u0119\u017caj,<\/li>\n\n\n\n<li>backtrackingu,<\/li>\n\n\n\n<li>dynamicznym programowaniu,<\/li>\n\n\n\n<li>kompilatorach.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"dlaczego-fibonacci-jest-zlym-przykladem-rekurencji\">Dlaczego Fibonacci jest z\u0142ym przyk\u0142adem rekurencji?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Klasyczna implementacja wykonuje ogromn\u0105 liczb\u0119 powtarzaj\u0105cych si\u0119 oblicze\u0144. To dobry przyk\u0142ad edukacyjny, ale s\u0142abe rozwi\u0105zanie praktyczne bez memoizacji.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"co-oznacza-stack-overflow\">Co oznacza stack overflow?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">To sytuacja, w kt\u00f3rej stos wywo\u0142a\u0144 funkcji przekracza dost\u0119pny rozmiar pami\u0119ci. Najcz\u0119\u015bciej powodem jest:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>niesko\u0144czona rekurencja,<\/li>\n\n\n\n<li>bardzo g\u0142\u0119bokie wywo\u0142ania,<\/li>\n\n\n\n<li>zbyt du\u017ce zmienne lokalne.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"czy-rekurencja-ogonowa-zawsze-jest-optymalizowana\">Czy rekurencja ogonowa zawsze jest optymalizowana?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Nie. Zale\u017cy to od:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>j\u0119zyka,<\/li>\n\n\n\n<li>kompilatora,<\/li>\n\n\n\n<li>ustawie\u0144 optymalizacji,<\/li>\n\n\n\n<li>sposobu napisania funkcji.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Python nie wykonuje takiej optymalizacji.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><em>\u0179r\u00f3d\u0142o Foto: Freepik<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Rekurencja pojawia si\u0119 bardzo wcze\u015bnie podczas nauki programowania, ale zwykle dopiero przy wi\u0119kszych problemach wida\u0107, po co naprawd\u0119 istnieje. W prostych zadaniach cz\u0119sto da si\u0119 j\u0105 zast\u0105pi\u0107 p\u0119tl\u0105, jednak przy strukturach drzewiastych, analizie graf\u00f3w, parsowaniu sk\u0142adni albo algorytmach dziel i zwyci\u0119\u017caj kod iteracyjny szybko staje si\u0119 trudny do utrzymania. W praktyce najwi\u0119kszy problem nie polega na samym zapisaniu funkcji rekurencyjnej, tylko na zrozumieniu przep\u0142ywu wywo\u0142a\u0144, pami\u0119ci stosu oraz kosztu czasowego. W\u0142a\u015bnie dlatego algorytmy rekurencyjne s\u0105 jednocze\u015bnie bardzo eleganckie i bardzo niebezpieczne, je\u015bli programista nie kontroluje ich g\u0142\u0119boko\u015bci oraz liczby wywo\u0142a\u0144. Algorytmy rekurencyjne i mechanizm dzia\u0142ania funkcji wywo\u0142uj\u0105cej sam\u0105 siebie krok po kroku Rekurencja polega na tym, \u017ce funkcja wywo\u0142uje sam\u0105 siebie, ale dla prostszego przypadku ni\u017c aktualny. Program dochodzi w ten spos\u00f3b do problemu elementarnego, kt\u00f3ry mo\u017cna rozwi\u0105za\u0107 bez kolejnych wywo\u0142a\u0144. Ten najprostszy przypadek nazywa si\u0119 warunkiem stopu. Bez warunku stopu funkcja b\u0119dzie wywo\u0142ywa\u0107 sam\u0105 siebie w niesko\u0144czono\u015b\u0107, a\u017c do przepe\u0142nienia stosu. To jeden z najcz\u0119stszych b\u0142\u0119d\u00f3w pocz\u0105tkuj\u0105cych. Ka\u017cde wywo\u0142anie funkcji tworzy now\u0105 ramk\u0119 stosu. Ramka zawiera: Je\u017celi funkcja wywo\u0142a sam\u0105 siebie 1000 razy, na stosie znajdzie si\u0119 1000 ramek. W j\u0119zykach takich jak C czy C++ bardzo g\u0142\u0119boka rekurencja mo\u017ce zako\u0144czy\u0107 program b\u0142\u0119dem segmentation fault albo stack overflow. Przyk\u0142ad matematyczny bardzo dobrze pokazuje ide\u0119 dzia\u0142ania. Silnia liczby n definiowana jest jako:n!=n\u22c5(n\u22121)!n! = n \\cdot (n-1)! oraz:0!=10! = 1 To naturalna definicja rekurencyjna. Przyk\u0142ad Kod C c\\n#include &lt;stdio.h&gt;\\n\\nint silnia(int n)\\n{\\n if(n == 0)\\n return 1;\\n\\n return n * silnia(n &#8211; 1);\\n}\\n\\nint main()\\n{\\n printf(\\&#8221;%d\\\\n\\&#8221;, silnia(5));\\n return 0;\\n}\\n C++ cpp\\n#include &lt;iostream&gt;\\nusing namespace std;\\n\\nint silnia(int n)\\n{\\n if(n == 0)\\n return 1;\\n\\n return n * silnia(n &#8211; 1);\\n}\\n\\nint main()\\n{\\n cout &lt;&lt; silnia(5) &lt;&lt; endl;\\n return 0;\\n}\\n Python python\\ndef silnia(n):\\n if n == 0:\\n return 1\\n\\n return n * silnia(n &#8211; 1)\\n\\nprint(silnia(5))\\n Przep\u0142yw wykonania dla silnia(5) wygl\u0105da tak: W praktyce bardzo wa\u017cne jest rozr\u00f3\u017cnienie dw\u00f3ch etap\u00f3w: Wiele b\u0142\u0119d\u00f3w logicznych bierze si\u0119 z niezrozumienia, \u017ce kod po wywo\u0142aniu rekurencyjnym wykona si\u0119 dopiero podczas wychodzenia ze stosu. Dlaczego algorytmy rekurencyjne s\u0105 naturalne dla drzew, graf\u00f3w i problem\u00f3w dzielonych na mniejsze cz\u0119\u015bci Rekurencja najlepiej dzia\u0142a tam, gdzie struktura danych sama ma charakter rekurencyjny. Drzewo binarne jest klasycznym przyk\u0142adem. Ka\u017cdy w\u0119ze\u0142 drzewa: Ka\u017cde poddrzewo jest znowu drzewem. To idealnie pasuje do rekurencji. Przechodzenie drzewa preorder: Przyk\u0142ad Kod C c\\n#include &lt;stdio.h&gt;\\n#include &lt;stdlib.h&gt;\\n\\nstruct Node\\n{\\n int value;\\n struct Node* left;\\n struct Node* right;\\n};\\n\\nvoid preorder(struct Node* root)\\n{\\n if(root == NULL)\\n return;\\n\\n printf(\\&#8221;%d \\&#8221;, root-&gt;value);\\n\\n preorder(root-&gt;left);\\n preorder(root-&gt;right);\\n}\\n C++ cpp\\n#include &lt;iostream&gt;\\nusing namespace std;\\n\\nstruct Node\\n{\\n int value;\\n Node* left;\\n Node* right;\\n};\\n\\nvoid preorder(Node* root)\\n{\\n if(root == nullptr)\\n return;\\n\\n cout &lt;&lt; root-&gt;value &lt;&lt; \\&#8221; \\&#8221;;\\n\\n preorder(root-&gt;left);\\n preorder(root-&gt;right);\\n}\\n Python python\\nclass Node:\\n def __init__(self, value):\\n self.value = value\\n self.left = None\\n self.right = None\\n\\n\\ndef preorder(root):\\n if root is None:\\n return\\n\\n print(root.value)\\n\\n preorder(root.left)\\n preorder(root.right)\\n Przy drzewach iteracyjna wersja cz\u0119sto wymaga w\u0142asnego stosu. Rekurencja u\u017cywa stosu funkcji procesora, wi\u0119c kod pozostaje kr\u00f3tszy. Podobnie dzia\u0142a DFS w grafach. J\u0119zyk Kod Python python\\ngraf = {\\n 1: [2, 3],\\n 2: [4],\\n 3: [],\\n 4: []\\n}\\n\\nodwiedzone = set()\\n\\n\\ndef dfs(v):\\n if v in odwiedzone:\\n return\\n\\n odwiedzone.add(v)\\n print(v)\\n\\n for sasiad in graf[v]:\\n dfs(sasiad)\\n\\n\\ndfs(1)\\n Tutaj bardzo \u0142atwo pope\u0142ni\u0107 b\u0142\u0105d polegaj\u0105cy na braku tablicy odwiedzonych wierzcho\u0142k\u00f3w. W grafie zawieraj\u0105cym cykl program mo\u017ce wej\u015b\u0107 w niesko\u0144czon\u0105 rekurencj\u0119. W praktycznych systemach takie b\u0142\u0119dy ko\u0144cz\u0105 si\u0119: Zale\u017cno\u015b\u0107 mi\u0119dzy z\u0142o\u017cono\u015bci\u0105 czasow\u0105 a liczb\u0105 wywo\u0142a\u0144 funkcji w rekurencji Najwi\u0119kszy problem wielu algorytm\u00f3w rekurencyjnych nie wynika z samej rekurencji, ale z liczby powtarzanych oblicze\u0144. Klasyczny przyk\u0142ad to ci\u0105g Fibonacciego. Definicja:F(n)=F(n\u22121)+F(n\u22122)F(n) = F(n-1) + F(n-2)F(n)=F(n\u22121)+F(n\u22122) J\u0119zyk Kod C c\\n#include &lt;stdio.h&gt;\\n\\nint fib(int n)\\n{\\n if(n &lt;= 1)\\n return n;\\n\\n return fib(n &#8211; 1) + fib(n &#8211; 2);\\n}\\n Python python\\ndef fib(n):\\n if n &lt;= 1:\\n return n\\n\\n return fib(n &#8211; 1) + fib(n &#8211; 2)\\n Dla fib(40) liczba wywo\u0142a\u0144 jest ogromna. Przybli\u017cona z\u0142o\u017cono\u015b\u0107:O(2n)O(2^n)Pow\u00f3d: Drzewo wywo\u0142a\u0144 ro\u015bnie wyk\u0142adniczo. Tutaj pojawia si\u0119 memoizacja. Memoizacja polega na zapami\u0119tywaniu wcze\u015bniej obliczonych wynik\u00f3w. J\u0119zyk Kod Python python\\ncache = {}\\n\\n\\ndef fib(n):\\n if n in cache:\\n return cache[n]\\n\\n if n &lt;= 1:\\n return n\\n\\n wynik = fib(n &#8211; 1) + fib(n &#8211; 2)\\n cache[n] = wynik\\n\\n return wynik\\n Po zastosowaniu memoizacji z\u0142o\u017cono\u015b\u0107 spada do:O(n)O(n)O(n) R\u00f3\u017cnica jest gigantyczna: W systemach produkcyjnych niew\u0142a\u015bciwa rekurencja cz\u0119sto prowadzi do: Rekurencja ogonowa i wp\u0142yw optymalizacji stosu na wydajno\u015b\u0107 programu Rekurencja ogonowa wyst\u0119puje wtedy, gdy ostatni\u0105 operacj\u0105 funkcji jest wywo\u0142anie samej siebie. Przyk\u0142ad: J\u0119zyk Kod C c\\n#include &lt;stdio.h&gt;\\n\\nint suma(int n, int acc)\\n{\\n if(n == 0)\\n return acc;\\n\\n return suma(n &#8211; 1, acc + n);\\n}\\n Python python\\ndef suma(n, acc):\\n if n == 0:\\n return acc\\n\\n return suma(n &#8211; 1, acc + n)\\n W niekt\u00f3rych kompilatorach mo\u017cliwa jest optymalizacja tail recursion: To redukuje zu\u017cycie pami\u0119ci. Problem praktyczny: Dlatego kod poprawny teoretycznie mo\u017ce nadal przepe\u0142ni\u0107 stos. Przyk\u0142adowe limity: W praktyce bardzo g\u0142\u0119boka rekurencja bywa zast\u0119powana: Algorytmy rekurencyjne w sortowaniu, podziale problemu i przetwarzaniu du\u017cych zbior\u00f3w danych Najwa\u017cniejsze praktyczne algorytmy rekurencyjne zwykle korzystaj\u0105 z techniki dziel i zwyci\u0119\u017caj. Schemat: Merge sort jest klasycznym przyk\u0142adem. Z\u0142o\u017cono\u015b\u0107:O(nlog\u2061n)O(n \\log n)O(nlogn) J\u0119zyk Kod Python python\\ndef merge_sort(tab):\\n if len(tab) &lt;= 1:\\n return tab\\n\\n mid = len(tab) \/\/ 2\\n\\n lewa = merge_sort(tab[:mid])\\n prawa = merge_sort(tab[mid:])\\n\\n wynik = []\\n\\n i = 0\\n j = 0\\n\\n while i &lt; len(lewa) and j &lt; len(prawa):\\n if lewa[i] &lt; prawa[j]:\\n wynik.append(lewa[i])\\n i += 1\\n else:\\n wynik.append(prawa[j])\\n j += 1\\n\\n wynik.extend(lewa[i:])\\n wynik.extend(prawa[j:])\\n\\n return wynik\\n Quick sort r\u00f3wnie\u017c wykorzystuje rekurencj\u0119. \u015arednia z\u0142o\u017cono\u015b\u0107:O(nlog\u2061n)O(n \\log n)O(nlogn) Najgorszy przypadek:O(n2)O(n^2)O(n2) Najwi\u0119kszy praktyczny problem quicksorta to z\u0142y wyb\u00f3r pivota. Dla ju\u017c posortowanych danych klasyczna implementacja mo\u017ce: Dlatego profesjonalne implementacje u\u017cywaj\u0105: Rekurencja wyst\u0119puje tak\u017ce w: Przyk\u0142ad generowania permutacji: J\u0119zyk Kod Python python\\ndef permutacje(tab, poczatek=0):\\n if poczatek == len(tab):\\n print(tab)\\n return\\n\\n for i in range(poczatek, len(tab)):\\n tab[poczatek], tab[i] = tab[i], tab[poczatek]\\n\\n permutacje(tab, poczatek + 1)\\n\\n tab[poczatek], tab[i] = tab[i], tab[poczatek]\\n\\n\\npermutacje([1, 2, 3])\\n Tutaj liczba mo\u017cliwych wynik\u00f3w wynosi:n!n!Dla: To pokazuje, \u017ce nawet poprawny algorytm rekurencyjny mo\u017ce by\u0107 praktycznie niewykonalny dla wi\u0119kszych danych. Najcz\u0119stsze b\u0142\u0119dy spotykane podczas implementacji funkcji rekurencyjnych i sposoby ich wykrywania Najcz\u0119stszy problem to brak poprawnego warunku stopu. Przyk\u0142ad b\u0142\u0119dny: J\u0119zyk Kod Python python\\ndef blad(n):\\n return blad(n &#8211; 1)\\n Taki kod ko\u0144czy si\u0119: Drugi cz\u0119sty b\u0142\u0105d: Je\u017celi warto\u015b\u0107 nie zbli\u017ca si\u0119 do warunku stopu, rekurencja nigdy si\u0119 nie ko\u0144czy. Trzeci problem: Przekazywanie du\u017cych struktur przez warto\u015b\u0107 mo\u017ce dramatycznie spowolni\u0107 program. W C++ lepiej stosowa\u0107 referencje: J\u0119zyk Kod C++ cpp\\nvoid funkcja(const vector&lt;int&gt;&amp; dane)\\n{\\n}\\n Kolejny problem: Wiele os\u00f3b nie rozumie, dlaczego: drukuje liczby dwa razy w r\u00f3\u017cnych momentach. To efekt rozwijania stosu. Praktyczna metoda debugowania: Dobrym \u0107wiczeniem jest rozpisanie ka\u017cdej ramki funkcji na kartce. Przy bardziej z\u0142o\u017conych algorytmach cz\u0119sto oszcz\u0119dza to godziny debugowania. Kiedy rekurencja jest lepsza od iteracji, a kiedy prowadzi do problem\u00f3w wydajno\u015bciowych Rekurencja daje bardzo czytelny kod dla: Iteracja zwykle wygrywa przy: Por\u00f3wnanie praktyczne: Cecha Rekurencja Iteracja Czytelno\u015b\u0107 cz\u0119sto bardzo wysoka zale\u017cy od problemu Zu\u017cycie pami\u0119ci wi\u0119ksze mniejsze Ryzyko stack overflow wysokie niskie \u0141atwo\u015b\u0107 dla drzew bardzo dobra \u015brednia Kontrola wykonania trudniejsza \u0142atwiejsza Wydajno\u015b\u0107 czasem ni\u017csza zwykle stabilniejsza W praktyce do\u015bwiadczeni programi\u015bci nie traktuj\u0105 rekurencji jako \u201elepszego\u201d rozwi\u0105zania. To po prostu narz\u0119dzie. Czasami rekurencyjny DFS jest idealny i daje kod kr\u00f3tszy o po\u0142ow\u0119. Innym razem ten sam mechanizm potrafi zabi\u0107 wydajno\u015b\u0107 aplikacji przy wi\u0119kszych danych wej\u015bciowych. Dobry programista zwykle analizuje: Rekurencja jest bardzo elegancka matematycznie, ale komputer wykonuje j\u0105 fizycznie przez stos wywo\u0142a\u0144 i pami\u0119\u0107 operacyjn\u0105. To ograniczenie zawsze trzeba bra\u0107 pod uwag\u0119 podczas projektowania algorytm\u00f3w. FAQ Czy rekurencj\u0119 da si\u0119 zawsze zast\u0105pi\u0107 iteracj\u0105? Teoretycznie tak. Ka\u017cdy algorytm rekurencyjny mo\u017cna przepisa\u0107 iteracyjnie, zwykle przy u\u017cyciu w\u0142asnego stosu. Problem polega na tym, \u017ce kod bywa wtedy du\u017co trudniejszy do utrzymania. Dlaczego Python ma niski limit rekurencji? Python celowo ogranicza g\u0142\u0119boko\u015b\u0107 wywo\u0142a\u0144, aby zmniejszy\u0107 ryzyko przepe\u0142nienia stosu i zawieszania interpretera. Domy\u015blny limit wynosi zwykle oko\u0142o 1000 wywo\u0142a\u0144. Czy rekurencja jest wolniejsza od p\u0119tli? Najcz\u0119\u015bciej tak, poniewa\u017c ka\u017cde wywo\u0142anie funkcji generuje dodatkowy koszt: Przy ma\u0142ych danych r\u00f3\u017cnica mo\u017ce by\u0107 niewielka. Gdzie rekurencja jest u\u017cywana najcz\u0119\u015bciej? Najcz\u0119\u015bciej w: Dlaczego Fibonacci jest z\u0142ym przyk\u0142adem rekurencji? Klasyczna implementacja wykonuje ogromn\u0105 liczb\u0119 powtarzaj\u0105cych si\u0119 oblicze\u0144. To dobry przyk\u0142ad edukacyjny, ale s\u0142abe rozwi\u0105zanie praktyczne bez memoizacji. Co oznacza stack overflow? To sytuacja, w kt\u00f3rej stos wywo\u0142a\u0144 funkcji przekracza dost\u0119pny rozmiar pami\u0119ci. Najcz\u0119\u015bciej powodem jest: Czy rekurencja ogonowa zawsze jest optymalizowana? Nie. Zale\u017cy to od: Python nie wykonuje takiej optymalizacji. \u0179r\u00f3d\u0142o Foto: Freepik<\/p>\n","protected":false},"author":1,"featured_media":1579,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24,1],"tags":[],"class_list":["post-1578","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-kodowanie","category-poradnik"],"_links":{"self":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts\/1578","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=1578"}],"version-history":[{"count":1,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts\/1578\/revisions"}],"predecessor-version":[{"id":1580,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts\/1578\/revisions\/1580"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/media\/1579"}],"wp:attachment":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/media?parent=1578"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/categories?post=1578"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/tags?post=1578"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}