Introdução
Recursão
As funções recursivas são funções que se chamam a si próprias.
Uma função recursiva precisa de ter pelo menos um caso base e pelo menos um caso recursivo.
Um caso base devolve um valor sem voltar a chamar a função.
Um caso recursivo volta a chamar a função, modificando o argumento para que este acabe por corresponder ao caso base.
Eis um exemplo que conta os elementos de um array.
def count:
if length == 0 then
0 # base case
else
1 + (.[1:] | count) # recursive case
end;
([] | count), # => 0
([11, 22, 33] | count) # => 3
Uma função recursiva pode ter muitos casos base e/ou muitos casos recursivos.
Por exemplo, a sequência de Fibonacci é uma sequência recursiva com dois casos base.
def fibonacci:
if . == 0 then
0
elif . == 1 then
1
else
(. - 1 | fibonacci) + (. - 2 | fibonacci)
end;
10 | fibonacci # => 55
Contar o número de ocorrências de um determinado valor x numa lista tem dois casos recursivos.
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
Na prática, iterar sobre listas e outras estruturas de dados enumeráveis faz-se quase sempre com funções incorporadas,
como map e reduce, ou usando streams como [.[] | select(...)].
Nos bastidores, algumas funções incorporadas são implementadas com recursão.
Instruções
Acabaste de entrar numa equipa que mantém um pipeline de dados baseado em jq.
Durante a tua primeira sessão de programação em par, o teu novo colega fica curioso:
"Sabes como funcionam o add, o reverse e o map por baixo do capô? Vamos explorar. Experimenta implementá-los tu próprio com recursão, sem usar os filtros incorporados."
1. Implementa uma função que soma os números de um array
Vamos reimplementar o filtro add incorporado para praticar recursão.
O caso base é que um array vazio tem soma zero.
Implementa-o tu próprio com uma função recursiva; não uses o add incorporado.
[5, 4, 6, 10] | array_add # => 25
2. Inverte um array
Vamos reimplementar o filtro reverse incorporado.
O caso base é que um array vazio invertido é um array vazio.
Implementa-o tu próprio com uma função recursiva; não uses o reverse incorporado.
[5, 4, 6, 10] | array_reverse # => [10, 6, 4, 5]
3. Mapeia um array
Vamos reimplementar o filtro map incorporado.
A função recebe um filtro como parâmetro, executa esse filtro para cada elemento do array de entrada e devolve os resultados num novo array.
O caso base é que um array vazio dá origem a um array vazio.
Implementa-o tu próprio com uma função recursiva; não uses o map incorporado.
[5, 4, 6, 10] | array_map(. + 10) # => [15, 14, 16, 20]
Exercício de aprendizagem
