Bevezetés
Farokrekurzió
Egy függvény farokrekurzív, ha az utolsó dolog, amit végrehajt, önmaga meghívása.
Valahányszor meghívunk egy függvényt, a lokális változóit és argumentumait tartalmazó veremkeret a hívási verem tetejére kerül.
Amikor egy függvény visszatér, a veremkeret lekerül a veremről.
A farokrekurzív függvények lehetővé teszik a farokhívás-optimalizálást (vagyis a farokhívás kiküszöbölését).
Ez egy olyan optimalizálás, amely lehetővé teszi, hogy a következő függvényhívás újrahasznosítsa az utolsó veremkeretet, amikor az előző függvényről biztosan tudjuk, hogy már nem lesz rá szüksége.
Ezzel enyhíthető a hívási verem túlcsordulásának veszélye, ami az a helyzet, amikor olyan sok keret van a hívási vermen, hogy már nem maradt memória egy újabb létrehozására.
Farokhívás-optimalizálás Elmben
Bizonyos feltételek mellett az Elm-fordító képes automatikusan végrehajtani a farokhívás-optimalizálást, amikor JavaScriptre fordít.
Az optimalizálás egy rekurzív függvénynél akkor történhet meg, ha egy ágban az utolsó művelet az, hogy a függvény önmagát hívja meg egy egyszerű függvényalkalmazásban.
Nézzünk meg néhány példát:
factorial : Int -> Int
factorial n =
if n <= 1 then
n
else
n * factorial (n-1)
A fenti implementáció nem farokrekurzív, mert az else ág utolsó művelete egy szorzás, n *.
factorial : Int -> Int
factorial n =
factorialHelper n n
factorialHelper : Int -> Int -> Int
factorialHelper n resultSoFar =
if n <= 1 then
resultSoFar
else
factorialHelper (n-1) (n * resultSoFar)
A fenti implementáció farokrekurzív, és optimalizálva lesz, mert az else ág utolsó művelete az, hogy a factorialHelper meghívja önmagát.
Ez egy Int -> Int típusszignatúrájú függvénynél nem lenne lehetséges, és a gyakorlatban a farokhívás-optimalizálást gyakran segédfüggvények definiálásával érik el.
Utasítások
Piper szenvedélyes pitesütő.
Senki sem tudja, hogy a neve miatt kezdett-e el pitét sütni, vagy azért változtatta meg a nevét, hogy illjen a hobbijához.
Első ránézésre ez utóbbi nem tűnik túl valószínűnek, de hát Pipert teljesen elbűvölik a piték.
Állandóan a konyhában ügyködik, finomítja a receptjeit, csiszolja a tudományát, barátai legnagyobb örömére.
És mi érdekli mostanában?
A lehető legkerekebb pitéket sütni, a matematikai tökéletességig, kedvenc száma segítségével, amit már kitaláltál: π.
Piper talált egy remek formulát, amivel iteratívan ki lehet számítani a π-t, ez a Newton/Euler-féle konvergenciatranszformáció:
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Segíts Pipernek megsütni a matematikailag tökéletes pitét a π kiszámításával.
1. Faktoriális
Először is melegítsünk be.
A faktoriális operátort általában ! jelöli, és így definiáljuk:
0! = 1
n! = 1 * 2 * 3 * ... * n
Definiáld a factorial függvényt, amely farokrekurzív módon számítja ki a faktoriálist.
factorial 4
-- 24
2. Kettős faktoriális
A kettős faktoriális operátort általában !! jelöli, és így definiáljuk:
0!! = 1
n!! = 1 * 3 * 5 * ... * n (for odd n)
n!! = 2 * 4 * 6 * ... * n (for even n)
Definiáld a doubleFactorial függvényt, amely farokrekurzív módon számítja ki a faktoriálist.
factorial 5
-- 15
factorial 6
-- 48
Definiáld a pipersPi függvényt, amely a Newton/Euler-féle konvergenciatranszformáció képletének adott számú tagjával közelíti a π-t, farokrekurzív módon.
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Számítsuk ki együtt az első tagot.
Ha a felső határ 0 (a végtelen helyett), akkor ezt kapjuk:
π / 2 ≈ Sum for k from 0 to 0 of ( k! ) / ( 2 * k + 1 )!!
π / 2 ≈ ( 0! ) / ( 2 * 0 + 1 )!!
π / 2 ≈ 0! / 0!!
π / 2 ≈ 1 / 1
π / 2 ≈ 1
π ≈ 2
Minden további tag javítja a közelítést.
pipersPi 0
-- 2.0
pipersPi 1
-- 2.6666666
Tanulófeladat
