Ricorsione in

Informazioni su Ricorsione

Le funzioni ricorsive sono funzioni che chiamano se stesse.

Una funzione ricorsiva deve avere almeno un caso base e almeno un caso ricorsivo.

Un caso base restituisce un valore senza chiamare di nuovo la funzione. Un caso ricorsivo chiama di nuovo la funzione, modificando l'input in modo che a un certo punto corrisponda al caso base.

Molto spesso, ogni caso è scritto in una propria clausola di funzione.

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

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

Una funzione ricorsiva può avere molti casi base e/o molti casi ricorsivi. Per esempio la successione di Fibonacci è una successione ricorsiva con due casi base:

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

Contare il numero di occorrenze di un certo valore x in un array ha due casi ricorsivi:

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)

Cicli tramite ricorsione

A causa dell'immutabilità, i cicli in Elixir si scrivono diversamente rispetto ai linguaggi imperativi. Per esempio, i cicli hanno spesso un aspetto simile a questo:

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

In un linguaggio funzionale, non è possibile modificare i (chiamando i++). Quindi i cicli vanno implementati con la ricorsione.

L'equivalente di un ciclo for in Elixir sarebbe questo:

def loop([]), do: nil

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

In pratica, per iterare sugli array e su altre strutture dati enumerabili si usa molto spesso il modulo Enum. Dietro le quinte, le funzioni del modulo Enum sono implementate usando la ricorsione.

Esecuzione infinita

Le funzioni ricorsive, se implementate in modo scorretto, potrebbero non restituire mai il loro risultato. Questo può essere problematico perché ogni volta che una funzione viene chiamata, viene memorizzato in memoria un riferimento al punto in cui la VM dovrebbe restituire il risultato (sul call stack). Se una funzione ricorsiva chiama se stessa all'infinito, si può esaurire la memoria e la VM può andare in crash (un errore di stack overflow). La VM di Erlang, su cui gira Elixir, è ottimizzata appositamente per la ricorsione e l'affidabilità, quindi può passare molto tempo prima che gli errori di ricorsione infinita diventino evidenti o che si verifichino crash.

Questo problema di esecuzione infinita può essere causato da:

• Dimenticare di implementare un caso base.
• Non definire il caso base come prima clausola.
• Non modificare correttamente l'argomento quando si fa la chiamata ricorsiva, e quindi non raggiungere mai il caso base.