Przeczytaj

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 $n!$ ma postać:

n! = {\begin{array}{lc} 1 & d l a n = 0 \\ n \cdot (n - 1) & d l a n > 0 \end{array}

A oto wzór iteracyjny:

n! = 1 \cdot 2 \cdot \dots \cdot (n - 1) \cdot n

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

wykorzystującą mechanizm rekurencji;

Problem 1

RtCXV2OWm8fBJ

działającą z użyciem metody powtórzeniowej (iteracyjnej):

Problem 2

RGna7qmENTJfT

Problem 3

R1Dn1kZusXou9

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.

# wykonanie funkcji bez modyfikacji limitu
rek_silnia(993)

Traceback (most recent call last):
	File "<pyshell#8>", line 1, in <module>
		rek_silnia(993)
	File "/home/python/rek_silnia.py", line 5, in rek_silnia
		return n * rek_silnia(n - 1)
	File "/home/python/rek_silnia.py", line 5, in rek_silnia
		return n * rek_silnia(n - 1)
	File "/home/python/rek_silnia.py", line 5, in rek_silnia
		return n * rek_silnia(n - 1)
	[Previous line repeated 990 more times]
	File "/home/python/rek_silnia.py", line 2, in rek_silnia
		if n == 0:
RecursionError: maximum recursion depth exceeded in comparison

# teraz modyfikujemy limit
import sys
sys.setrecursionlimit(1100)

# ponownie wykonujemy funkcję
rek_silnia(993)

# poniżej wynik
410945501524637078826433597064797141006536484819577429202307344030079497838274247005087601607836
650665564963697963684127592946138890165908732779701508454872983992914345542447490355458933208647
171580240712038800582005376840260962182977072889971970138356673577662103029842071976445133413075
944647117284151303481672710106080931332441504655223218116857241186393190085490297543705734462160
748782755835766437380934418437637028140704410239180178188346598121883129788129545293208160250987
588230832354840264798447383302334455372205225922289829588519551200050874423384253031533323946791
776128470106973898091771888812680028727162158062143157083659140463172111290950448413444387020940
243360924414480595148226552287835726647180834650691700014210838542316778110623701469323794973942
492199732123949282122228818880400507634753241447528166546275778700208392530138864950494550486308
885863979661696812665221841119508244434729248815151592057159062666273955402389280890444814743646
659885535842886348377407136102884298026308830846530934600454936219279320869678209842146386782437
232727384755813682931842555093405831874684799794408576838635716609482080112442121020824934938333
629999688773860810472582600262715404480706466206657868237865995373523837608155536136260281628927
197793847062140475274541740332107039177259415140202560944346418336797455404270896048118868050159
436811323248720612318690166813908331142070290106699564896974063112920654654471324555508271777667
930185087770759272205391168999546405346958584462584790697323659166726544084799929787911022123985
319723463237842726237011545199915153087453039959209939739774713076775719947944213571610636805282
755600227699196089090702245209532369603848642715207488660617928451746718375444254889312909196410
296843196287890692006205524613529149984544436276426794978525391813908954520448032664501112008063
221253788867755804839876430804817629000657024570328106915172695060852056864737950278488399176822
775509135715700067362044389000671221437534236871617447761650953462681755488835341121987619252262
968992925708630296470058414710566034126214025466076094405231488903022997195871999290413450128607
923003228168103817022040093428309363615188826761869136169596880151965644401628277959572249489431
754183616524745428240233639875701165960087700720601943204604453781314591794442968998197434777600
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
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.

# kod funkcji
# program domyślnie dla Python 2 dostępny w internecie
# poniżej kod przygotowany dla Python 3

import sys
import itertools

class RecursiveBlowup1:
	def __init__(self):
		self.__init__()

def test_init():
	return RecursiveBlowup1()

class RecursiveBlowup2:
	def __repr__(self):
		return repr(self)

def test_repr():
	return repr(RecursiveBlowup2())

class RecursiveBlowup4:
	def __add__(self, x):
		return x + self

def test_add():
	return RecursiveBlowup4() + RecursiveBlowup4()

class RecursiveBlowup5:
	def __getattr__(self, attr):
		return getattr(self, attr)

def test_getattr():
	return RecursiveBlowup5().attr

class RecursiveBlowup6:
	def __getitem__(self, item):
		return self[item - 2] + self[item - 1]

def test_getitem():
	return RecursiveBlowup6()[5]

def test_recurse():
	return test_recurse()

def test_cpickle(_cache={}):
	try:
		import _pickle as cPickle
	except ImportError:
		print("cannot import cPickle, skipped!")
		return

	l = None

	for n in itertools.count():
		try:
			l = _cache[n]
			continue  # Already tried and it works, let's save some time
		except KeyError:
			for i in range(100):
				l = [l]

		cPickle.dumps(l, protocol=-1)
		_cache[n] = l

def check_limit(n, test_func_name):
	sys.setrecursionlimit(n)

	if test_func_name.startswith("test_"):
		print( test_func_name[5:])
	else:
		print(test_func_name)

	test_func = globals()[test_func_name]

	try:
		test_func()
	# AttributeError can be raised because of the way e.g. PyDict_GetItem()
	# silences all exceptions and returns NULL, which is usually interpreted
	# as "missing attribute".
	except (RuntimeError, AttributeError):
		pass
	else:
		print( "Yikes!")

limit = 1000

while 1:
	check_limit(limit, "test_recurse")
	check_limit(limit, "test_add")
	check_limit(limit, "test_repr")
	check_limit(limit, "test_init")
	check_limit(limit, "test_getattr")
	check_limit(limit, "test_getitem")
	check_limit(limit, "test_cpickle")
	print ("Limit of %d is fine" % limit)
	limit = limit + 100

# wynik działania dla systemu Linux 64-bity
# [...]
recurse
add
repr
init
getattr
getitem
cpickle
Limit of 16800 is fine
recurse

Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)

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

wielokrotne wykonywanie tych samych czynności

rekurencja

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

Wprowadzenie

Gra edukacyjna

Słownik