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 rendelkeznie kell legalább egy alapesettel és legalább egy rekurzív esettel.

Egy alapeset anélkül ad vissza egy értéket, hogy újra hívná a függvényt. Egy rekurzív eset újra hívja a függvényt, módosítva a bemenetet, hogy az valamikor illeszkedjen az alapesethez.

Nagyon gyakran minden eset a saját függvényklózban van megírva.

# base case
def count([]), do: 0

# recursive case
def count([_head | tail]), do: 1 + count(tail)

Egy rekurzív függvénynek sok alapesete és/vagy sok rekurzív esete lehet. Például a Fibonacci-sorozat egy rekurzív sorozat, amelynek két alapesete van:

def fibonacci(0), do: 0
def fibonacci(1), do: 1
def fibonacci(n), do: fibonacci(n - 1) + fibonacci(n - 2)

Egy adott x érték előfordulásainak megszámolása egy listában két rekurzív esettel rendelkezik:

def count_occurrences([], _x), do: 0
def count_occurrences([x | tail], x), do: 1 + count_occurrences(tail, x)
def count_occurrences([_ | tail], x), do: count_occurrences(tail, x)

Ciklusok rekurzióval

A változtathatatlanság miatt az Elixirben a ciklusok másképp íródnak, mint az imperatív nyelvekben. Például a ciklusok gyakran így néznek ki:

for(i = 0; i < array.size; i++) {
  # do something with array[i]
}

Egy funkcionális nyelvben az i módosítása (az i++ hívásával) nem lehetséges. Így a ciklusokat rekurzióval kell megvalósítani.

A for ciklus megfelelője az Elixirben így nézne ki:

def loop([]), do: nil

def loop([head | tail]) do
  do_something(head)
  loop(tail)
end

A gyakorlatban a listákon és más felsorolható adatszerkezeteken való iterálás leggyakrabban a Enum modullal történik. A háttérben az Enum modul függvényei rekurzióval vannak megvalósítva.

Végtelen végrehajtás

Előfordulhat, hogy a rekurzív függvények helytelen megvalósítás esetén soha nem adják vissza az eredményüket. Ez problémás lehet, mert minden függvényhíváskor egy hivatkozás tárolódik a memóriában, ahová a VM-nek vissza kell térnie az eredménnyel (a hívási veremben). Ha egy rekurzív függvény végtelenszer hívja önmagát, elfogyhat a memória, ami a VM összeomlását okozhatja (egy veremtúlcsordulási hiba). Az Erlang VM, amelyen az Elixir fut, különösen optimalizált a rekurzióra és a megbízhatóságra, így hosszú időbe telhet, mire a végtelen rekurzió hibái nyilvánvalóvá válnak vagy összeomlás történik.

A végtelen végrehajtás problémáját a következők okozhatják:

• Elfelejtjük megvalósítani az alapesetet.
• Nem az alapesetet definiáljuk első klózként.
• Nem módosítjuk megfelelően az argumentumot a rekurzív híváskor, és így soha nem érjük el az alapesetet.