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.

Ecco un esempio che conta gli elementi di un array.

def count:
  if length == 0 then
    0                       # base case
  else
    1 + (.[1:] | count)     # recursive case
  end;

([] | count),           # => 0
([11, 22, 33] | count)  # => 3

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

def fibonacci:
  if . == 0 then
    0
  elif . == 1 then
    1
  else
    (. - 1 | fibonacci) + (. - 2 | fibonacci)
  end;

10 | fibonacci          # => 55

Contare il numero di occorrenze di un dato valore x in un array ha due casi ricorsivi.

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

In pratica, per iterare su array e altre strutture dati enumerabili si usano più spesso funzioni integrate, come map e reduce, oppure gli stream come [.[] | select(...)]. Sotto il cofano, alcune funzioni integrate sono implementate usando la ricorsione.

Ricorsione infinita

Le funzioni ricorsive, se implementate in modo errato, potrebbero non restituire mai il loro risultato. Questo può essere problematico, perché ogni volta che viene chiamata una funzione viene memorizzato in memoria un riferimento al punto in cui la VM deve restituire il risultato (sullo stack di chiamate). Se una funzione ricorsiva chiama se stessa all'infinito, è possibile esaurire la memoria, facendo andare in crash la VM con un errore di stack overflow.

Questo problema di ricorsione infinita può essere causato da:

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

Ottimizzazione delle chiamate in coda

Come descritto su Wikipedia:

Una chiamata in coda è una chiamata a un sottoprogramma eseguita come azione finale di una procedura. Se la destinazione di una coda è lo stesso sottoprogramma, si dice che il sottoprogramma è ricorsivo in coda.

Considera l'implementazione di fibonacci mostrata sopra. Il caso ricorsivo chiama se stesso due volte. L'ultima azione che la funzione deve eseguire è un'addizione. Poiché l'ultima azione non è una chiamata a se stessa, quella funzione è ricorsiva, ma non ricorsiva in coda.

Alcuni linguaggi implementano l'ottimizzazione delle chiamate in coda, così che la chiamata in coda possa riutilizzare il frame dello stack corrente invece di dover aggiungere un nuovo frame allo stack di chiamate. Questo può portare vantaggi in termini di prestazioni, oltre a proteggere dal temuto stack overflow.

jq implementa davvero l'ottimizzazione delle chiamate in coda, ma solo per le funzioni con arietà 0. Il modo per approfittarne è definire una funzione «interna» con arietà 0 che prende in input una qualche forma di stato. La funzione interna può modificare lo stato come serve e passare il nuovo stato alla chiamata ricorsiva in coda. La funzione esterna crea lo stato iniziale e lo passa alla funzione interna per avviare la ricorsione.

Una funzione fibonacci ricorsiva in coda si potrebbe implementare mantenendo la serie calcolata finora come parte dello stato.

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