Wyniki działania dwóch różnych funkcji rozwiązujących ten sam problem są takie same – niezależnie od tego, czy zastosujemy mechanizm rekurencyjnyrekurencjarekurencyjny, czy iteracyjnyiteracjaiteracyjny. Odmienny jest natomiast sposób zapisu kodów funkcji oraz sposób ich działania. Przekonamy się o tym na przykładzie dwóch funkcji obliczających wartość silni.

Silnia liczby n jest iloczynem wszystkich liczb naturalnych od 1 do n. Wyjątkiem jest silnia liczby 0, która wynosi 1.

Wzór rekurencyjny na obliczanie ma postać:

n ! = { 1 d l a n = 0 n ( n 1 ) d l a n > 0

A oto wzór iteracyjny:

n!=12(n1)n

Korzystając z przedstawionych wzorów możemy zdefiniować dwie wersje funkcji obliczające wartość silni:

  • wykorzystującą mechanizm rekurencji;

1
Problem 1
RtCXV2OWm8fBJ
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
  • działającą z użyciem metody powtórzeniowej (iteracyjnej):

1
Problem 2
RGna7qmENTJfT
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
1
Problem 3
R1Dn1kZusXou9
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Dla zainteresowanych

W najpopularniejszej implementacji języka Python – CPython istnieje ograniczenie liczby możliwych do wykonania wywołań rekurencyjnych. Standardowo wynosi ona 1000. Możemy zmienić tę wielkość, korzystając z funkcji setrecursionlimit() należącej do modułu sys. Powinniśmy jednak pamiętać, że we wszystkich systemach operacyjnych istnieją fizyczne ograniczenia liczby wykonywanych operacji rekurencyjnych. Wynikają one z ograniczeń pamięci przydzielanych dla stosu w różnych kompilatorach i systemach operacyjnych. Oto przykład wywołania zdefiniowanej wcześniej funkcji rek_silnia() zakończony wygenerowaniem informacji o błędzie (później następuje zmiana limitu operacji, dzięki czemu funkcja zwraca poprawny wynik):

Linia 1. kratka wykonanie funkcji bez modyfikacji limitu. Linia 2. rek podkreślnik silnia otwórz nawias okrągły 993 zamknij nawias okrągły. Linia 4. Traceback otwórz nawias okrągły most recent call last zamknij nawias okrągły dwukropek. Linia 5. File cudzysłów otwórz nawias ostrokątny pyshell kratka 8 zamknij nawias ostrokątny cudzysłów przecinek line 1 przecinek in otwórz nawias ostrokątny module zamknij nawias ostrokątny. Linia 6. rek podkreślnik silnia otwórz nawias okrągły 993 zamknij nawias okrągły. Linia 7. File cudzysłów prawy ukośnik home prawy ukośnik python prawy ukośnik rek podkreślnik silnia kropka py cudzysłów przecinek line 5 przecinek in rek podkreślnik silnia. Linia 8. return n asterysk rek podkreślnik silnia otwórz nawias okrągły n minus 1 zamknij nawias okrągły. Linia 9. File cudzysłów prawy ukośnik home prawy ukośnik python prawy ukośnik rek podkreślnik silnia kropka py cudzysłów przecinek line 5 przecinek in rek podkreślnik silnia. Linia 10. return n asterysk rek podkreślnik silnia otwórz nawias okrągły n minus 1 zamknij nawias okrągły. Linia 11. File cudzysłów prawy ukośnik home prawy ukośnik python prawy ukośnik rek podkreślnik silnia kropka py cudzysłów przecinek line 5 przecinek in rek podkreślnik silnia. Linia 12. return n asterysk rek podkreślnik silnia otwórz nawias okrągły n minus 1 zamknij nawias okrągły. Linia 13. otwórz nawias kwadratowy Previous line repeated 990 more times zamknij nawias kwadratowy. Linia 14. File cudzysłów prawy ukośnik home prawy ukośnik python prawy ukośnik rek podkreślnik silnia kropka py cudzysłów przecinek line 2 przecinek in rek podkreślnik silnia. Linia 15. if n znak równości znak równości 0 dwukropek. Linia 16. RecursionError dwukropek maximum recursion depth exceeded in comparison. Linia 18. kratka teraz modyfikujemy limit. Linia 19. import sys. Linia 20. sys kropka setrecursionlimit otwórz nawias okrągły 1100 zamknij nawias okrągły. Linia 22. kratka ponownie wykonujemy funkcję. Linia 23. rek podkreślnik silnia otwórz nawias okrągły 993 zamknij nawias okrągły. Linia 25. kratka poniżej wynik. Linia 26. 410945501524637078826433597064797141006536484819577429202307344030079497838274247005087601607836. Linia 27. 650665564963697963684127592946138890165908732779701508454872983992914345542447490355458933208647. Linia 28. 171580240712038800582005376840260962182977072889971970138356673577662103029842071976445133413075. Linia 29. 944647117284151303481672710106080931332441504655223218116857241186393190085490297543705734462160. Linia 30. 748782755835766437380934418437637028140704410239180178188346598121883129788129545293208160250987. Linia 31. 588230832354840264798447383302334455372205225922289829588519551200050874423384253031533323946791. Linia 32. 776128470106973898091771888812680028727162158062143157083659140463172111290950448413444387020940. Linia 33. 243360924414480595148226552287835726647180834650691700014210838542316778110623701469323794973942. Linia 34. 492199732123949282122228818880400507634753241447528166546275778700208392530138864950494550486308. Linia 35. 885863979661696812665221841119508244434729248815151592057159062666273955402389280890444814743646. Linia 36. 659885535842886348377407136102884298026308830846530934600454936219279320869678209842146386782437. Linia 37. 232727384755813682931842555093405831874684799794408576838635716609482080112442121020824934938333. Linia 38. 629999688773860810472582600262715404480706466206657868237865995373523837608155536136260281628927. Linia 39. 197793847062140475274541740332107039177259415140202560944346418336797455404270896048118868050159. Linia 40. 436811323248720612318690166813908331142070290106699564896974063112920654654471324555508271777667. Linia 41. 930185087770759272205391168999546405346958584462584790697323659166726544084799929787911022123985. Linia 42. 319723463237842726237011545199915153087453039959209939739774713076775719947944213571610636805282. Linia 43. 755600227699196089090702245209532369603848642715207488660617928451746718375444254889312909196410. Linia 44. 296843196287890692006205524613529149984544436276426794978525391813908954520448032664501112008063. Linia 45. 221253788867755804839876430804817629000657024570328106915172695060852056864737950278488399176822. Linia 46. 775509135715700067362044389000671221437534236871617447761650953462681755488835341121987619252262. Linia 47. 968992925708630296470058414710566034126214025466076094405231488903022997195871999290413450128607. Linia 48. 923003228168103817022040093428309363615188826761869136169596880151965644401628277959572249489431. Linia 49. 754183616524745428240233639875701165960087700720601943204604453781314591794442968998197434777600. Linia 50. 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000. Linia 51. 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000. Linia 52. 000000000000000000000000000000000000000000000000000.
Dla zainteresowanych

Spróbujmy określić maksymalną liczbę operacji rekurencyjnych, które można wykonać w naszym systemie operacyjnym. Oto przykładowy program sprawdzający tę wielkość:

Linia 1. kratka kod funkcji. Linia 2. kratka program domyślnie dla Python 2 dostępny w internecie. Linia 3. kratka poniżej kod przygotowany dla Python 3. Linia 5. import sys. Linia 6. import itertools. Linia 8. class RecursiveBlowup1 dwukropek. Linia 9. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 10. self kropka podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły zamknij nawias okrągły. Linia 12. def test podkreślnik init otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 13. return RecursiveBlowup1 otwórz nawias okrągły zamknij nawias okrągły. Linia 15. class RecursiveBlowup2 dwukropek. Linia 16. def podkreślnik podkreślnik repr podkreślnik podkreślnik otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 17. return repr otwórz nawias okrągły self zamknij nawias okrągły. Linia 19. def test podkreślnik repr otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 20. return repr otwórz nawias okrągły RecursiveBlowup2 otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 22. class RecursiveBlowup4 dwukropek. Linia 23. def podkreślnik podkreślnik add podkreślnik podkreślnik otwórz nawias okrągły self przecinek x zamknij nawias okrągły dwukropek. Linia 24. return x plus self. Linia 26. def test podkreślnik add otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 27. return RecursiveBlowup4 otwórz nawias okrągły zamknij nawias okrągły plus RecursiveBlowup4 otwórz nawias okrągły zamknij nawias okrągły. Linia 29. class RecursiveBlowup5 dwukropek. Linia 30. def podkreślnik podkreślnik getattr podkreślnik podkreślnik otwórz nawias okrągły self przecinek attr zamknij nawias okrągły dwukropek. Linia 31. return getattr otwórz nawias okrągły self przecinek attr zamknij nawias okrągły. Linia 33. def test podkreślnik getattr otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 34. return RecursiveBlowup5 otwórz nawias okrągły zamknij nawias okrągły kropka attr. Linia 36. class RecursiveBlowup6 dwukropek. Linia 37. def podkreślnik podkreślnik getitem podkreślnik podkreślnik otwórz nawias okrągły self przecinek item zamknij nawias okrągły dwukropek. Linia 38. return self otwórz nawias kwadratowy item minus 2 zamknij nawias kwadratowy plus self otwórz nawias kwadratowy item minus 1 zamknij nawias kwadratowy. Linia 40. def test podkreślnik getitem otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 41. return RecursiveBlowup6 otwórz nawias okrągły zamknij nawias okrągły otwórz nawias kwadratowy 5 zamknij nawias kwadratowy. Linia 43. def test podkreślnik recurse otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 44. return test podkreślnik recurse otwórz nawias okrągły zamknij nawias okrągły. Linia 46. def test podkreślnik cpickle otwórz nawias okrągły podkreślnik cache znak równości otwórz nawias klamrowy zamknij nawias klamrowy zamknij nawias okrągły dwukropek. Linia 47. try dwukropek. Linia 48. import podkreślnik pickle as cPickle. Linia 49. except ImportError dwukropek. Linia 50. print otwórz nawias okrągły cudzysłów cannot import cPickle przecinek skipped wykrzyknik cudzysłów zamknij nawias okrągły. Linia 51. return. Linia 53. l znak równości None. Linia 55. for n in itertools kropka count otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 56. try dwukropek. Linia 57. l znak równości podkreślnik cache otwórz nawias kwadratowy n zamknij nawias kwadratowy. Linia 58. continue kratka Already tried and it works przecinek let apostrof s save some time. Linia 59. except KeyError dwukropek. Linia 60. for i in range otwórz nawias okrągły 100 zamknij nawias okrągły dwukropek. Linia 61. l znak równości otwórz nawias kwadratowy l zamknij nawias kwadratowy. Linia 63. cPickle kropka dumps otwórz nawias okrągły l przecinek protocol znak równości minus 1 zamknij nawias okrągły. Linia 64. podkreślnik cache otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości l. Linia 66. def check podkreślnik limit otwórz nawias okrągły n przecinek test podkreślnik func podkreślnik name zamknij nawias okrągły dwukropek. Linia 67. sys kropka setrecursionlimit otwórz nawias okrągły n zamknij nawias okrągły. Linia 69. if test podkreślnik func podkreślnik name kropka startswith otwórz nawias okrągły cudzysłów test podkreślnik cudzysłów zamknij nawias okrągły dwukropek. Linia 70. print otwórz nawias okrągły test podkreślnik func podkreślnik name otwórz nawias kwadratowy 5 dwukropek zamknij nawias kwadratowy zamknij nawias okrągły. Linia 71. else dwukropek. Linia 72. print otwórz nawias okrągły test podkreślnik func podkreślnik name zamknij nawias okrągły. Linia 74. test podkreślnik func znak równości globals otwórz nawias okrągły zamknij nawias okrągły otwórz nawias kwadratowy test podkreślnik func podkreślnik name zamknij nawias kwadratowy. Linia 76. try dwukropek. Linia 77. test podkreślnik func otwórz nawias okrągły zamknij nawias okrągły. Linia 78. kratka AttributeError can be raised because of the way e kropka g kropka PyDict podkreślnik GetItem otwórz nawias okrągły zamknij nawias okrągły. Linia 79. kratka silences all exceptions and returns NULL przecinek which is usually interpreted. Linia 80. kratka as cudzysłów missing attribute cudzysłów kropka. Linia 81. except otwórz nawias okrągły RuntimeError przecinek AttributeError zamknij nawias okrągły dwukropek. Linia 82. pass. Linia 83. else dwukropek. Linia 84. print otwórz nawias okrągły cudzysłów Yikes wykrzyknik cudzysłów zamknij nawias okrągły. Linia 86. limit znak równości 1000. Linia 88. while 1 dwukropek. Linia 89. check podkreślnik limit otwórz nawias okrągły limit przecinek cudzysłów test podkreślnik recurse cudzysłów zamknij nawias okrągły. Linia 90. check podkreślnik limit otwórz nawias okrągły limit przecinek cudzysłów test podkreślnik add cudzysłów zamknij nawias okrągły. Linia 91. check podkreślnik limit otwórz nawias okrągły limit przecinek cudzysłów test podkreślnik repr cudzysłów zamknij nawias okrągły. Linia 92. check podkreślnik limit otwórz nawias okrągły limit przecinek cudzysłów test podkreślnik init cudzysłów zamknij nawias okrągły. Linia 93. check podkreślnik limit otwórz nawias okrągły limit przecinek cudzysłów test podkreślnik getattr cudzysłów zamknij nawias okrągły. Linia 94. check podkreślnik limit otwórz nawias okrągły limit przecinek cudzysłów test podkreślnik getitem cudzysłów zamknij nawias okrągły. Linia 95. check podkreślnik limit otwórz nawias okrągły limit przecinek cudzysłów test podkreślnik cpickle cudzysłów zamknij nawias okrągły. Linia 96. print otwórz nawias okrągły cudzysłów Limit of procent d is fine cudzysłów procent limit zamknij nawias okrągły. Linia 97. limit znak równości limit plus 100. Linia 99. kratka wynik działania dla systemu Linux 64 minus bity. Linia 100. kratka otwórz nawias kwadratowy kropka kropka kropka zamknij nawias kwadratowy. Linia 101. recurse. Linia 102. add. Linia 103. repr. Linia 104. init. Linia 105. getattr. Linia 106. getitem. Linia 107. cpickle. Linia 108. Limit of 16800 is fine. Linia 109. recurse. Linia 111. Process finished with exit code 139 otwórz nawias okrągły interrupted by signal 11 dwukropek SIGSEGV zamknij nawias okrągły.
Już wiesz

Podsumujmy najważniejsze elementy z tego e‑materiału:

  • funkcja rekurencyjna wielokrotnie wywołuje samą siebie,

  • wykonanie funkcji wywoływanej rekurencyjnie wymaga większej ilości pamięci operacyjnej,

  • w języku Python istnieje limit możliwych do wykonania operacji rekurencyjnych.

Słownik

iteracja
iteracja

wielokrotne wykonywanie tych samych czynności

rekurencja
rekurencja

sytuacja, w której funkcja wywołuje samą siebie aż do napotkania przypadku podstawowego