{"id":774,"date":"2024-11-18T16:46:05","date_gmt":"2024-11-18T16:46:05","guid":{"rendered":"http:\/\/maciux.pl\/?page_id=774"},"modified":"2024-11-19T18:51:18","modified_gmt":"2024-11-19T18:51:18","slug":"rekurencja-i-iteracja","status":"publish","type":"page","link":"https:\/\/maciux.pl\/index.php\/rekurencja-i-iteracja\/","title":{"rendered":"Rekurencja i iteracja"},"content":{"rendered":"\n

Rekurencja i iteracja to dwa kluczowe podej\u015bcia w programowaniu, pozwalaj\u0105ce na rozwi\u0105zanie problem\u00f3w poprzez wykonywanie powtarzalnych dzia\u0142a\u0144.<\/p>\n\n\n\n

Na czym polega rekurencja?<\/strong><\/h4>\n\n\n\n

Rekurencja to technika programistyczna, w kt\u00f3rej funkcja wywo\u0142uje sam\u0105 siebie, a\u017c do momentu osi\u0105gni\u0119cia okre\u015blonego warunku zako\u0144czenia, zwanego warunkiem bazowym<\/strong>. Rekurencja jest szczeg\u00f3lnie przydatna w problemach, kt\u00f3re mo\u017cna podzieli\u0107 na mniejsze, podobne do siebie podproblemy (np. przeszukiwanie struktur drzewiastych, rozwi\u0105zywanie r\u00f3wna\u0144 rekurencyjnych).<\/p>\n\n\n\n

Struktura rekurencji:<\/strong><\/h5>\n\n\n\n
    \n
  1. Warunek bazowy:<\/strong> Punkt, w kt\u00f3rym rekurencja si\u0119 zatrzymuje.<\/li>\n\n\n\n
  2. Wywo\u0142anie rekurencyjne:<\/strong> Funkcja wywo\u0142uje sam\u0105 siebie z mniejszym problemem.<\/li>\n<\/ol>\n\n\n\n

    Przyk\u0142ad (obliczanie silni w j\u0119zyku programowania pythoon):<\/p>\n\n\n\n

    \"\"<\/figure>\n\n\n\n

    Na czym polega iteracja?<\/strong><\/h4>\n\n\n\n

    Iteracja to powtarzanie zestawu operacji za pomoc\u0105 p\u0119tli (np. for<\/code>, while<\/code>). Iteracje s\u0105 prostsze do zrozumienia w wielu przypadkach i bardziej wydajne, poniewa\u017c nie obci\u0105\u017caj\u0105 stosu wywo\u0142a\u0144.<\/p>\n\n\n\n

    Przyk\u0142ad (obliczanie silni w j\u0119zyku programowania pythoon):<\/p>\n\n\n\n

    \"\"<\/figure>\n\n\n\n

    Algorytm obliczania silni liczby naturalnej<\/strong><\/h3>\n\n\n\n

    Silnia liczby naturalnej nnn, oznaczana jako n!n!n!, to iloczyn wszystkich liczb naturalnych od 1 do nnn. Definicja matematyczna:<\/p>\n\n\n\n

      \n
    • 0!=10! = 10!=1<\/li>\n\n\n\n
    • n!=n\u00d7(n\u22121)!n! = n \\times (n-1)!n!=n\u00d7(n\u22121)!, dla n>0n > 0n>0.<\/li>\n<\/ul>\n\n\n\n

      Implementacja rekurencyjna:<\/strong><\/h4>\n\n\n\n
        \n
      1. Je\u015bli n=0n = 0n=0, zwr\u00f3\u0107 1 (warunek bazowy).<\/li>\n\n\n\n
      2. W przeciwnym razie zwr\u00f3\u0107 n\u00d7silnia(n\u22121)n \\times silnia(n-1)n\u00d7silnia(n\u22121).<\/li>\n<\/ol>\n\n\n\n

        Przyk\u0142ad:<\/p>\n\n\n\n

          \n
        • 5!=5\u00d74!=5\u00d74\u00d73\u00d72\u00d71=1205! = 5 \\times 4! = 5 \\times 4 \\times 3 \\times 2 \\times 1 = 1205!=5\u00d74!=5\u00d74\u00d73\u00d72\u00d71=120.<\/li>\n<\/ul>\n\n\n\n
          \n\n\n\n

          Ci\u0105g Fibonacciego<\/strong><\/h3>\n\n\n\n

          Ci\u0105g Fibonacciego to sekwencja liczb, w kt\u00f3rej ka\u017cda liczba (pocz\u0105wszy od trzeciej) jest sum\u0105 dw\u00f3ch poprzednich:<\/p>\n\n\n\n

            \n
          • F(0)=0F(0) = 0F(0)=0<\/li>\n\n\n\n
          • F(1)=1F(1) = 1F(1)=1<\/li>\n\n\n\n
          • F(n)=F(n\u22121)+F(n\u22122)F(n) = F(n-1) + F(n-2)F(n)=F(n\u22121)+F(n\u22122), dla n>1n > 1n>1.<\/li>\n<\/ul>\n\n\n\n

            Implementacja rekurencyjna:<\/h4>\n\n\n\n
            \"\"<\/figure>\n\n\n\n

            Iteracyjna wersja algorytmu:<\/h4>\n\n\n\n
            \"\"<\/figure>\n\n\n\n

            Przyk\u0142ad:<\/p>\n\n\n\n

              \n
            • Ci\u0105g Fibonacciego dla n=5n = 5n=5: 0,1,1,2,3,50, 1, 1, 2, 3, 50,1,1,2,3,5.<\/li>\n<\/ul>\n\n\n\n
              \n\n\n\n

              Algorytm Euklidesa \u2013 wyznaczanie NWD<\/strong><\/h3>\n\n\n\n

              Najwi\u0119kszy wsp\u00f3lny dzielnik (NWD) dw\u00f3ch liczb to najwi\u0119ksza liczba ca\u0142kowita, kt\u00f3ra dzieli obie liczby bez reszty.<\/p>\n\n\n\n

              Opis algorytmu:<\/strong><\/h4>\n\n\n\n

              Algorytm Euklidesa opiera si\u0119 na w\u0142asno\u015bci, \u017ce:<\/p>\n\n\n\n

                \n
              • NWD(a,b)=NWD(b,amod\u2009\u2009b)NWD(a, b) = NWD(b, a \\mod b)NWD(a,b)=NWD(b,amodb), gdzie amod\u2009\u2009ba \\mod bamodb to reszta z dzielenia aaa przez bbb.<\/li>\n\n\n\n
              • Je\u015bli b=0b = 0b=0, to NWD(a,b)=aNWD(a, b) = aNWD(a,b)=a.<\/li>\n<\/ul>\n\n\n\n

                Rekurencyjna implementacja:<\/h4>\n\n\n\n
                \"\"<\/figure>\n\n\n\n

                Iteracyjna implementacja:<\/h4>\n\n\n\n
                \"\"<\/figure>\n\n\n\n

                Przyk\u0142ad:<\/strong><\/h4>\n\n\n\n

                Znajd\u017a NWD dla a=48a = 48a=48 i b=18b = 18b=18:<\/p>\n\n\n\n

                  \n
                1. 48mod\u2009\u200918=1248 \\mod 18 = 1248mod18=12, wi\u0119c NWD(48,18)=NWD(18,12)NWD(48, 18) = NWD(18, 12)NWD(48,18)=NWD(18,12).<\/li>\n\n\n\n
                2. 18mod\u2009\u200912=618 \\mod 12 = 618mod12=6, wi\u0119c NWD(18,12)=NWD(12,6)NWD(18, 12) = NWD(12, 6)NWD(18,12)=NWD(12,6).<\/li>\n\n\n\n
                3. 12mod\u2009\u20096=012 \\mod 6 = 012mod6=0, wi\u0119c NWD(12,6)=6NWD(12, 6) = 6NWD(12,6)=6.<\/li>\n<\/ol>\n\n\n\n

                  Wynik: NWD(48,18)=6NWD(48, 18) = 6NWD(48,18)=6.<\/p>\n\n\n\n

                  \n\n\n\n

                  Podsumowanie<\/strong><\/h3>\n\n\n\n

                  Rekurencja i iteracja to dwa r\u00f3\u017cne podej\u015bcia do rozwi\u0105zywania problem\u00f3w:<\/p>\n\n\n\n

                    \n
                  • Rekurencja jest naturalna dla problem\u00f3w o strukturze hierarchicznej (np. ci\u0105g Fibonacciego, NWD).<\/li>\n\n\n\n
                  • Iteracja jest bardziej efektywna pod wzgl\u0119dem pami\u0119ci, ale mo\u017ce by\u0107 mniej intuicyjna.<\/li>\n<\/ul>\n\n\n\n

                    W algorytmach takich jak wyznaczanie NWD, zar\u00f3wno rekurencja, jak i iteracja s\u0105 r\u00f3wnie skuteczne, ale w przypadku skomplikowanych problem\u00f3w rekurencja oferuje prostszy zapis i lepsz\u0105 czytelno\u015b\u0107.<\/p>\n\n\n\n

                    <\/p>\n","protected":false},"excerpt":{"rendered":"

                    Rekurencja i iteracja to dwa kluczowe podej\u015bcia w programowaniu, pozwalaj\u0105ce na rozwi\u0105zanie problem\u00f3w poprzez wykonywanie powtarzalnych dzia\u0142a\u0144. Na czym polega rekurencja? Rekurencja to technika programistyczna, w kt\u00f3rej funkcja wywo\u0142uje sam\u0105 siebie, a\u017c do momentu osi\u0105gni\u0119cia okre\u015blonego warunku zako\u0144czenia, zwanego warunkiem bazowym. Rekurencja jest szczeg\u00f3lnie przydatna w problemach, kt\u00f3re mo\u017cna podzieli\u0107 na mniejsze, podobne do siebie … <\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-774","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/pages\/774","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/comments?post=774"}],"version-history":[{"count":4,"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/pages\/774\/revisions"}],"predecessor-version":[{"id":880,"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/pages\/774\/revisions\/880"}],"wp:attachment":[{"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/media?parent=774"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}