Introduzione
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 prima o poi 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 successione di Fibonacci è una successione 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 l'uso degli stream come [.[] | select(...)].
Dietro le quinte, alcune funzioni integrate sono implementate usando la ricorsione.
Istruzioni
Sei appena entrato a far parte di un team che gestisce una pipeline di dati basata su jq.
Durante la tua prima sessione di pair programming, il tuo nuovo collega si incuriosisce:
«Sai come funzionano add, reverse e map sotto il cofano? Esploriamo: prova a implementarli tu stesso usando la ricorsione, senza le funzioni integrate.»
1. Implementa una funzione per sommare i numeri in un array
Reimplementeremo il filtro integrato add per fare pratica con la ricorsione.
Il caso base è che un array vuoto ha una somma pari a zero.
Implementalo tu stesso con una funzione ricorsiva; non usare il filtro integrato add.
[5, 4, 6, 10] | array_add # => 25
2. Inverti un array
Reimplementeremo il filtro integrato reverse.
Il caso base è che un array vuoto invertito è un array vuoto.
Implementalo tu stesso con una funzione ricorsiva; non usare il filtro integrato reverse.
[5, 4, 6, 10] | array_reverse # => [10, 6, 4, 5]
3. Mappa un array
Reimplementeremo il filtro integrato map.
La funzione prende un filtro come parametro, esegue quel filtro per ogni elemento dell'array di input e restituisce gli output in un nuovo array.
Il caso base è che un array vuoto restituisce un array vuoto.
Implementalo tu stesso con una funzione ricorsiva; non usare il filtro integrato map.
[5, 4, 6, 10] | array_map(. + 10) # => [15, 14, 16, 20]
Esercizio di apprendimento
