Introducción
Recursión
Las funciones recursivas son funciones que se llaman a sí mismas.
Una función recursiva necesita tener al menos un caso base y al menos un caso recursivo.
Un caso base devuelve un valor sin volver a llamar a la función.
Un caso recursivo vuelve a llamar a la función, modificando la entrada para que en algún momento coincida con el caso base.
Aquí tienes un ejemplo que cuenta los elementos de 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 función recursiva puede tener muchos casos base y/o muchos casos recursivos.
Por ejemplo, la sucesión de Fibonacci es una sucesión recursiva con dos casos base.
def fibonacci:
if . == 0 then
0
elif . == 1 then
1
else
(. - 1 | fibonacci) + (. - 2 | fibonacci)
end;
10 | fibonacci # => 55
Contar el número de apariciones de un valor dado x en un array tiene dos 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
En la práctica, recorrer arrays y otras estructuras de datos enumerables se hace casi siempre con funciones integradas,
como map y reduce, o usando streams como [.[] | select(...)].
Por debajo, algunas funciones integradas están implementadas con recursión.
Instrucciones
Acabas de incorporarte a un equipo que mantiene una canalización de datos basada en jq.
Durante tu primera sesión de programación en pareja, tu nuevo compañero siente curiosidad:
«¿Sabes cómo funcionan add, reverse y map por dentro? Vamos a explorarlo. Intenta implementarlos tú mismo con recursión, sin usar los filtros incorporados.»
1. Implementa una función que sume los números de un array
Vamos a reimplementar el filtro add incorporado para practicar la recursión.
El caso base es que un array vacío tiene una suma de cero.
Impleméntalo tú mismo con una función recursiva; no uses el add incorporado.
[5, 4, 6, 10] | array_add # => 25
2. Invierte un array
Vamos a reimplementar el filtro reverse incorporado.
El caso base es que un array vacío invertido es un array vacío.
Impleméntalo tú mismo con una función recursiva; no uses el reverse incorporado.
[5, 4, 6, 10] | array_reverse # => [10, 6, 4, 5]
3. Aplica map a un array
Vamos a reimplementar el filtro map incorporado.
La función toma un filtro como parámetro, ejecuta ese filtro en cada elemento del array de entrada y devuelve los resultados en un array nuevo.
El caso base es que un array vacío se transforma en un array vacío.
Impleméntalo tú mismo con una función recursiva; no uses el map incorporado.
[5, 4, 6, 10] | array_map(. + 10) # => [15, 14, 16, 20]
Ejercicio de aprendizaje
