IB111 Úvod do programovaní
skrze python
9.
š Š
Vnitro
Rekurzia
“Aby ste pochopili rekurziu,
musíte pochopiť rekurziu.”
Zdroj: http://www.slavorum.org/matryoshka-russian-nesting-dolls/
Rekurzia
★ š
ž
★ ž
○
○ č
Faktorial
def it_fact(n):
fact = 1
while n > 1:
fact *= n
n -= 1
return fact
def rec_fact(n):
if (n < 1):
return 1
else:
return n * rec_fact(n - 1)
Nevýhoda?
Rekurzia
def count_down(n):
if n < 1:
print("End!")
else:
print(n)
count_down(n - 1)
count_down(5)
5
4
3
2
1
End!
Rekurzia
# i = item, l = list
def all_(i, l):
if len(l) > 0:
return i == l[0] and all_(i, l[1:])
else:
return True
print(all_(3, [3,3,3]))
Nepriama rekurzia
★ š
def even(n):
print("even", n)
odd(n - 1)
def odd(n):
print("odd", n)
if n > 1:
even(n - 1)
?Pair programming?
Úloha 1
★ ž
č n č
★ sum_of_numbers_recursive(100) => 5050
Úloha 2
● ž
True,False ľ č
● contains(3,[1,2]) => False
● contains(3,[1,3,5]) => True
● contains(3,[]) => False
Úloha 3
● ž
ť ť
ť
● zip_strings("abc", "xyz") => 'axbycz'
● zip_strings("abc", "x") => 'axbc'
● zip_strings("a", "xyz") => 'axyz'
Úloha 4
●
š
how_many š ť ľ
ť
nested_squares(how_many=5,length=200)
Úloha 5
● ž
ń
● ž
sierpinski(how_many=3,length=100)
Úloha 6
●
● š č š
● n š
ľ
● č
čš ž ľ
● ť ž ľ
Úloha 6
ž ť
ž ť ž ť
ť
Ž ť ž š
Zdroj: https://en.wikipedia.org/wiki/File:Tower_of_Hanoi.jpeg
Úloha 6
ň n−1 A B
n A
ň 1 čš A C
ň n−1 B C čš
Zdroj: http://www.fi.muni.cz/~xpelanek/IB111/slidy/rekurze.pdf
č A B C
n A C
Úloha 6
Zdroj: http://mathforum.org/dr.math/faq/faq.tower.hanoi.html
š hanoi(n,from_pole,to_pole,helper)
š n from_pole(A)
to_pole(C) helper(B).
>>>hanoi (2,"A","C","B")
A -> B
A -> C
B -> C
Úloha 1*
● ž
š
● list.insert(0,i) ž
● smaller_than(3,[1,2]) = [1,2]
● smaller_than(6,[1,5,3]) = [1,5,3]
● smaller_than(100,[]) = []
Quick sort**
● ž č
def qsort(S):
if len(S) <= 1:
return S
randomly pick pivot x from S
L = {y in S | y < x}
R = {y in S | y > x}
return qsort(L) + {x} + qsort(R)
Quick sort**
Zdroj: https://devtalk.nvidia.com/default/topic/496167/need-help-understanding-this-function-__device_
Credits
Special thanks to all the people who made and released
these awesome resources for free:
Presentation template by SlidesCarnival
Photographs by Unsplash