Rekurzió ebben a kurzusban:

A(z) Rekurzió fogalomról

A rekurzív függvények olyan függvények, amelyek önmagukat hívják.

Egy 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 úgy 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 több alapesete és/vagy több rekurzív esete is lehet. Például a Fibonacci-sorozat egy 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 eset kell.

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 legtöbbször beépített függvényekkel iterálunk, például a map és a reduce segítségével, vagy folyamok használatával, mint például a [.[] | select(...)]. A háttérben néhány beépített függvény rekurzióval van megvalósítva.

Végtelen rekurzió

A rekurzív függvények helytelen megvalósítás esetén soha nem adják vissza az eredményüket. Ez azért lehet problémás, mert minden alkalommal, amikor meghívunk egy függvényt, a memóriában eltárolódik egy hivatkozás arra, hogy hova kell a virtuális gépnek visszaadnia az eredményt (a hívási vermen). Ha egy rekurzív függvény végtelenszer hívja meg önmagát, elfogyhat a memória, és a virtuális gép veremtúlcsordulási hibával összeomolhat.

A végtelen rekurzió ezen problémáját az alábbiak okozhatják:

• Elfelejtjük megvalósítani az alapesetet.
• Nem az alapesetet adjuk meg elsőként.
• A rekurzív hívás során nem megfelelően módosítjuk az argumentumot, és így soha nem érünk el az alapesetig.

Farokhívás-optimalizálás

Ahogy a Wikipédia is leírja:

A farokhívás olyan szubrutinhívás, amelyet egy eljárás utolsó műveleteként hajtunk végre. Ha a farokhívás célpontja ugyanaz a szubrutin, akkor a szubrutint farokrekurzívnak nevezzük.

Vegyük a fent megvalósított fibonacci függvényt. A rekurzív eset kétszer hívja meg önmagát. Az utolsó művelet, amelyet a függvénynek végre kell hajtania, az összeadás. Mivel az utolsó művelet nem önmagának a meghívása, ez a függvény rekurzív, de nem farokrekurzív.

Egyes nyelvek megvalósítják a farokhívás-optimalizálást, így a farokhívás újra tudja használni az aktuális veremkeretet ahelyett, hogy új keretet kellene hozzáadnia a hívási veremhez. Ez a teljesítmény szempontjából is előnyös lehet, amellett, hogy véd a rettegett veremtúlcsordulás ellen.

A jq tényleg megvalósítja a farokhívás-optimalizálást, de csak nullás aritású függvények esetében. Ennek kihasználásához definiálj egy „belső” nullás aritású függvényt, amely valamilyen állapotot kap bemenetként. A belső függvény szükség szerint módosíthatja az állapotot, és az új állapotot átadhatja a farokrekurzív hívásnak. A külső függvény létrehozza a kezdő állapotot, és átadja a belső függvénynek, hogy elkezdődjön a rekurzió.

Egy farokrekurzív fibonacci függvényt úgy valósíthatunk meg, hogy a már kiszámolt sorozatot az állapot részeként tároljuk.

def fibonacci:
  def _fib:
    # input: {limit: number, series: array}
    if (.series | length - 1) >= .limit then
      .series[.limit]                                   # base case
    else
      .series += [.series[-1] + .series[-2]] | _fib     # recursive case
    end;
  {limit: ., series: [0, 1]} | _fib;

10 | fibonacci          # => 55