Rekurze (angl. recursion) je programátorská technika, kdy funkce volá sebe sama.
Taková rekurze skončí nekonečným voláním. Když zadáš tento program:
def rekurzivni_funkce():
vysledek = ...
rekurzivni_funkce()
return vysledek
rekurzivni_funkce()
Jak to funguje?
rekurzivni_funkcerekurzivni_funkce:rekurzivni_funkce:rekurzivni_funkce:rekurzivni_funkce:rekurzivni_funkce:Tomu odpovídá chybová hláška:
Traceback (most recent call last):
File "/tmp/ukazka.py", line 4, in <module>
rekurzivni_funkce()
File "/tmp/ukazka.py", line 2, in rekurzivni_funkce
return rekurzivni_funkce()
File "/tmp/ukazka.py", line 2, in rekurzivni_funkce
return rekurzivni_funkce()
File "/tmp/ukazka.py", line 2, in rekurzivni_funkce
return rekurzivni_funkce()
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceededHláška je zkrácená – dva řádky by se správně měly opakovat 999×, ale novější verze Pythonu je vypíšou jen třikrát.
Jak rekurzi využít v praxi? Jeden způsob je si počítat, kolikrát se ještě „zanořit“.
Představ si potapěče, který prozkoumává mořské hlubiny následujícím způsobem:
Neboli v Pythonu:
def pruzkum(hloubka):
print(f'Zkoumám v hloubce {hloubka} m')
if hloubka >= 30:
print('Už toho bylo dost!')
else:
print(f'Zanořuju se (z {hloubka} m)')
pruzkum(hloubka + 10)
print(f'Vynořuju se (na {hloubka} m)')
pruzkum(0)
pruzkumpruzkum s hloubkou 0:Rozhlížím se v hloubce 0 m0 ≥ 30 (což neplatí)Zanořuju se (z 0 m)pruzkum s hloubkou 10 m:Rozhlížím se v hloubce 10 m10 ≥ 30 (což neplatí)Zanořuju se (na 10 m)pruzkum s hloubkou 20 m:20 ≥ 30 (což neplatí)Zanořuju se (na 20 m)pruzkum s hloubkou 30 m:30 ≥ 30 (což platí! konečně!)Už toho bylo dost! a skončíVynořuju se (na 20 m)Vynořuju se (na 10 m)Vynořuju se (na 0 m)Na předchozím příkladu je vidět zajímavé chování lokálních proměnných. Když je potapěč „na dně“, jakou hodnotu má proměnná hloubka?
Tahle otázka je chyták. Která proměnná hloubka?
Když je program „na dně“, existují čtyři různé lokální proměnné hloubka:
každé zanoření, každé zavolání funkce pruzkum, má vlastní proměnnou.
Podobně jako když máš globální a lokální proměnnou stejného jména, každá funkce „vidí“ jen tu svoji proměnnou. Ale když se potapěč vynoří a volání funkce se ukončí, tato proměnná přestane existovat. A „volající“ funkce vidí svoji proměnnou, ve které je stále původní hodnota.
Nemáš-li ráda matematiku, tuhle sekci přeskoč!
Rekurzivní algoritmy mají původ v matematice. Faktoriál x, neboli součin všech čísel od 1 do x, zapsaný jako x!, matematici definují takto:
Neboli v Pythonu:
def factorial(x):
if x == 0:
return 1
elif x > 0:
return x * factorial(x - 1)
print(factorial(5))
print(1 * 2 * 3 * 4 * 5)
{
"data": {
"sessionMaterial": {
"id": "session-material:2019/brno-podzim-pondeli:file:4",
"title": "Rekurze (bonus)",
"html": "\n \n \n\n <h1>Rekurze</h1>\n<p><em>Rekurze</em> (angl. <em>recursion</em>) je programátorská technika,\nkdy funkce volá sebe sama.</p>\n<p>Taková rekurze skončí nekonečným voláním.\nKdyž zadáš tento program:</p>\n<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">rekurzivni_funkce</span><span class=\"p\">():</span>\n <span class=\"n\">vysledek</span> <span class=\"o\">=</span> <span class=\"o\">...</span>\n <span class=\"n\">rekurzivni_funkce</span><span class=\"p\">()</span>\n <span class=\"k\">return</span> <span class=\"n\">vysledek</span>\n\n<span class=\"n\">rekurzivni_funkce</span><span class=\"p\">()</span>\n</pre></div><p>Jak to funguje?</p>\n<ul>\n<li>Python si nadefinuje funkci <code>rekurzivni_funkce</code></li>\n<li>Zavolá funkci <code>rekurzivni_funkce</code>:<ul>\n<li>Vypočítá výsledek</li>\n<li>Zavolá funkci <code>rekurzivni_funkce</code>:<ul>\n<li>Vypočítá výsledek</li>\n<li>Zavolá funkci <code>rekurzivni_funkce</code>:<ul>\n<li>Vypočítá výsledek</li>\n<li>Zavolá funkci <code>rekurzivni_funkce</code>:<ul>\n<li>Vypočítá výsledek</li>\n<li>Zavolá funkci <code>rekurzivni_funkce</code>:<ul>\n<li>...<ul>\n<li><em> ...\n </em> po stovkách opakování si Python všimne, že tohle asi\n nikam nevede, a skončí s chybou.</li>\n</ul>\n</li>\n</ul>\n</li>\n</ul>\n</li>\n</ul>\n</li>\n</ul>\n</li>\n</ul>\n</li>\n</ul>\n<p>Tomu odpovídá chybová hláška:</p>\n<div class=\"highlight\"><pre><code>Traceback (most recent call last):\n File "/tmp/ukazka.py", line 4, in <module>\n rekurzivni_funkce()\n File "/tmp/ukazka.py", line 2, in rekurzivni_funkce\n return rekurzivni_funkce()\n File "/tmp/ukazka.py", line 2, in rekurzivni_funkce\n return rekurzivni_funkce()\n File "/tmp/ukazka.py", line 2, in rekurzivni_funkce\n return rekurzivni_funkce()\n [Previous line repeated 996 more times]\nRecursionError: maximum recursion depth exceeded</code></pre></div><p>Hláška je zkrácená – dva řádky by se správně měly opakovat 999×, ale novější\nverze Pythonu je vypíšou jen třikrát.</p>\n<h1>Kontrolované zanoření</h1>\n<p>Jak rekurzi využít v praxi?\nJeden způsob je si počítat, kolikrát se ještě „zanořit“.</p>\n<p>Představ si potapěče, který prozkoumává mořské hlubiny následujícím způsobem:</p>\n<ul>\n<li>Jak <em>„prozkoumat moře“</em> v určité hloubce:<ul>\n<li>Porozhlédnu se kolem</li>\n<li>Jsem-li už teď moc hluboko, kašlu na to; nebudu prozkoumávat dál.</li>\n<li>Jinak:<ul>\n<li>Zanořím se o 10 m níž</li>\n<li><em>Prozkoumám moře</em> v nové hloubce</li>\n<li>Zase se o 10 m vynořím</li>\n</ul>\n</li>\n</ul>\n</li>\n</ul>\n<p>Neboli v Pythonu:</p>\n<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">pruzkum</span><span class=\"p\">(</span><span class=\"n\">hloubka</span><span class=\"p\">):</span>\n <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"n\">f</span><span class=\"s1\">'Zkoumám v hloubce {hloubka} m'</span><span class=\"p\">)</span>\n\n <span class=\"k\">if</span> <span class=\"n\">hloubka</span> <span class=\"o\">>=</span> <span class=\"mi\">30</span><span class=\"p\">:</span>\n <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">'Už toho bylo dost!'</span><span class=\"p\">)</span>\n <span class=\"k\">else</span><span class=\"p\">:</span>\n <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"n\">f</span><span class=\"s1\">'Zanořuju se (z {hloubka} m)'</span><span class=\"p\">)</span>\n\n <span class=\"n\">pruzkum</span><span class=\"p\">(</span><span class=\"n\">hloubka</span> <span class=\"o\">+</span> <span class=\"mi\">10</span><span class=\"p\">)</span>\n\n <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"n\">f</span><span class=\"s1\">'Vynořuju se (na {hloubka} m)'</span><span class=\"p\">)</span>\n\n<span class=\"n\">pruzkum</span><span class=\"p\">(</span><span class=\"mi\">0</span><span class=\"p\">)</span>\n</pre></div><ul>\n<li>Python si nadefinuje funkci <code>pruzkum</code></li>\n<li>Zavolá funkci <code>pruzkum</code> s hloubkou 0:<ul>\n<li>Vypíše <code>Rozhlížím se v hloubce 0 m</code></li>\n<li>Zkontroluje, že <code>0 ≥ 30</code> (což neplatí)</li>\n<li>Vypíše <code>Zanořuju se (z 0 m)</code></li>\n<li>Zavolá funkci <code>pruzkum</code> s hloubkou 10 m:<ul>\n<li>Vypíše <code>Rozhlížím se v hloubce 10 m</code></li>\n<li>Zkontroluje, že <code>10 ≥ 30</code> (což neplatí)</li>\n<li>Vypíše <code>Zanořuju se (na 10 m)</code></li>\n<li>Zavolá funkci <code>pruzkum</code> s hloubkou 20 m:<ul>\n<li>Zkontroluje, že <code>20 ≥ 30</code> (což neplatí)</li>\n<li>Vypíše <code>Zanořuju se (na 20 m)</code><ul>\n<li>Zavolá funkci <code>pruzkum</code> s hloubkou 30 m:<ul>\n<li>Zkontroluje, že <code>30 ≥ 30</code> (což platí! konečně!)<ul>\n<li><em> Vypíše <code>Už toho bylo dost!</code></em> a skončí</li>\n</ul>\n</li>\n</ul>\n</li>\n</ul>\n</li>\n<li>Vypíše <code>Vynořuju se (na 20 m)</code></li>\n</ul>\n</li>\n<li>Vypíše <code>Vynořuju se (na 10 m)</code></li>\n</ul>\n</li>\n<li>Vypíše <code>Vynořuju se (na 0 m)</code></li>\n</ul>\n</li>\n</ul>\n<h1>Lokální proměnné</h1>\n<p>Na předchozím příkladu je vidět zajímavé chování lokálních proměnných.\nKdyž je potapěč „na dně“, jakou hodnotu má proměnná <em>hloubka</em>?</p>\n<p>Tahle otázka je chyták. <em>Která</em> proměnná <code>hloubka</code>?\nKdyž je program „na dně“, existují čtyři <em>různé</em> lokální proměnné <code>hloubka</code>:\nkaždé zanoření, každé zavolání funkce <code>pruzkum</code>, má vlastní proměnnou.</p>\n<p>Podobně jako když máš globální a lokální proměnnou stejného jména,\nkaždá funkce „vidí“ jen tu svoji proměnnou.\nAle když se potapěč vynoří a volání funkce se ukončí, tato proměnná\npřestane existovat.\nA „volající“ funkce vidí svoji proměnnou, ve které je stále původní hodnota.</p>\n<h1>Pro matematiky</h1>\n<div class=\"admonition note\"><p>Nemáš-li ráda matematiku, tuhle sekci přeskoč!</p>\n</div><p>Rekurzivní algoritmy mají původ v matematice. Faktoriál <var>x</var>, neboli\nsoučin všech čísel od 1 do <var>x</var>, zapsaný jako <var>x</var>!,\nmatematici definují takto:</p>\n<ul>\n<li>0! = 1</li>\n<li>Pro kladná <var>x</var> je <var>x</var>! = <var>x</var> · (<var>x</var> - 1)!</li>\n</ul>\n<p>Neboli v Pythonu:</p>\n<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">factorial</span><span class=\"p\">(</span><span class=\"n\">x</span><span class=\"p\">):</span>\n <span class=\"k\">if</span> <span class=\"n\">x</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n <span class=\"k\">return</span> <span class=\"mi\">1</span>\n <span class=\"k\">elif</span> <span class=\"n\">x</span> <span class=\"o\">></span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n <span class=\"k\">return</span> <span class=\"n\">x</span> <span class=\"o\">*</span> <span class=\"n\">factorial</span><span class=\"p\">(</span><span class=\"n\">x</span> <span class=\"o\">-</span> <span class=\"mi\">1</span><span class=\"p\">)</span>\n\n<span class=\"k\">print</span><span class=\"p\">(</span><span class=\"n\">factorial</span><span class=\"p\">(</span><span class=\"mi\">5</span><span class=\"p\">))</span>\n<span class=\"k\">print</span><span class=\"p\">(</span><span class=\"mi\">1</span> <span class=\"o\">*</span> <span class=\"mi\">2</span> <span class=\"o\">*</span> <span class=\"mi\">3</span> <span class=\"o\">*</span> <span class=\"mi\">4</span> <span class=\"o\">*</span> <span class=\"mi\">5</span><span class=\"p\">)</span>\n</pre></div>\n\n\n "
}
}
}