Introdução
Recursão
Funções recursivas são funções que chamam a si mesmas.
Uma função recursiva precisa ter pelo menos um caso base e pelo menos um caso recursivo.
Um caso base retorna um valor sem chamar a função de novo.
Um caso recursivo chama a função de novo, modificando a entrada para que em algum momento ela corresponda ao caso base.
Veja 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 vários casos base e/ou vários 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 em uma 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 costuma ser feito com funções nativas, como map e reduce, ou usando streams como [.[] | select(...)].
Por baixo dos panos, algumas funções nativas são implementadas com recursão.
Instruções
Você acabou de entrar em um time que mantém um pipeline de dados baseado em jq.
Durante sua primeira sessão de programação em par, seu novo colega fica curioso:
"Você sabe como add, reverse e map funcionam por baixo dos panos? Vamos explorar: tente implementá-los você mesmo usando recursão, sem os embutidos."
1. Implemente uma função para somar os números de um array
Vamos reimplementar o filtro add embutido para praticar recursão.
O caso base é que um array vazio tem soma zero.
Implemente você mesmo com uma função recursiva; não use o add embutido.
[5, 4, 6, 10] | array_add # => 25
2. Inverta um array
Vamos reimplementar o filtro reverse embutido.
O caso base é que um array vazio invertido é um array vazio.
Implemente você mesmo com uma função recursiva; não use o reverse embutido.
[5, 4, 6, 10] | array_reverse # => [10, 6, 4, 5]
3. Mapeie um array
Vamos reimplementar o filtro map embutido.
A função recebe um filtro como parâmetro, roda esse filtro para cada elemento do array de entrada e retorna as saídas em um novo array.
O caso base é que um array vazio mapeia para um array vazio.
Implemente você mesmo com uma função recursiva; não use o map embutido.
[5, 4, 6, 10] | array_map(. + 10) # => [15, 14, 16, 20]
Exercício de aprendizagem
