Bevezetés
Rekurzió
A rekurzív függvények olyan függvények, amelyek önmagukat hívják.
A rekurzív függvénynek legalább egy alapesettel és legalább egy rekurzív esettel kell rendelkeznie.
Az alapeset úgy ad vissza egy értéket, hogy nem hívja meg újra a függvényt.
A rekurzív eset újra meghívja a függvényt, és módosítja a bemenetet, hogy az előbb-utóbb megfeleljen az alapesetnek.
Íme egy példa, amely megszámolja egy tömb elemeit.
def count:
if length == 0 then
0 # base case
else
1 + (.[1:] | count) # recursive case
end;
([] | count), # => 0
([11, 22, 33] | count) # => 3
Egy rekurzív függvénynek sok alapesete és/vagy sok rekurzív esete lehet.
Például a Fibonacci-sorozat egy olyan rekurzív sorozat, amelynek két alapesete van.
def fibonacci:
if . == 0 then
0
elif . == 1 then
1
else
(. - 1 | fibonacci) + (. - 2 | fibonacci)
end;
10 | fibonacci # => 55
Ha egy adott x érték előfordulásait számoljuk meg egy listában, ahhoz két rekurzív esetre van szükség.
def count_occurrences(x):
if length == 0 then
0
elif first == x then
1 + (.[1:] | count_occurrences(x))
else
(.[1:] | count_occurrences(x))
end;
[11, 22, 33, 22, 44] | count_occurrences(22) # => 2
A gyakorlatban a listákon és más felsorolható adatszerkezeteken való iterálás leggyakrabban beépített függvényekkel történik,
például a map és a reduce segítségével, vagy folyamok használatával, például így: [.[] | select(...)].
A színfalak mögött néhány beépített függvény rekurzióval valósul meg.
Utasítások
Nemrég csatlakoztál egy csapathoz, amely egy jq-alapú adatfeldolgozási folyamatot tart karban.
Az első páros programozási alkalmon az új kollégád kíváncsi lesz:
„Tudod, hogyan működnek a háttérben az add, a reverse és a map? Nézzük meg, és próbáld meg te magad megvalósítani azokat rekurzióval, a beépített függvények nélkül.”
1. Írj egy függvényt, amely összeadja egy tömb számait
A rekurzió gyakorlásához újra megírjuk a beépített add szűrőt.
Az alapeset az, hogy egy üres tömb összege nulla.
Írd meg magad egy rekurzív függvénnyel; ne használd a beépített add szűrőt.
[5, 4, 6, 10] | array_add # => 25
2. Fordítsd meg egy tömböt
Újra megírjuk a beépített reverse szűrőt.
Az alapeset az, hogy egy üres tömb megfordítva üres tömb.
Írd meg magad egy rekurzív függvénnyel; ne használd a beépített reverse szűrőt.
[5, 4, 6, 10] | array_reverse # => [10, 6, 4, 5]
3. Képezz le egy tömböt
Újra megírjuk a beépített map szűrőt.
A függvény paraméterként egy szűrőt kap, azt lefuttatja a bemeneti tömb minden elemére, és a kimeneteket egy új tömbben adja vissza.
Az alapeset az, hogy egy üres tömb leképezése üres tömb.
Írd meg magad egy rekurzív függvénnyel; ne használd a beépített map szűrőt.
[5, 4, 6, 10] | array_map(. + 10) # => [15, 14, 16, 20]
Tanulófeladat
