Introducción
Recursión
Las funciones recursivas son funciones que se llaman a sí mismas.
Una función recursiva debe 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 el argumento 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 secuencia 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, iterar sobre arrays y otras estructuras de datos enumerables se hace casi siempre con funciones integradas,
como map y reduce, o usando streams como [.[] | select(...)].
Internamente, algunas funciones integradas están implementadas con recursión.
Instrucciones
Acabas de unirte a un equipo que mantiene un pipeline de datos basado en jq.
Durante tu primera sesión de programación en pareja, la curiosidad se apodera de tu colega:
«¿Sabes cómo funcionan add, reverse y map internamente? Exploremos. Intenta implementarlos por tu cuenta usando recursión, sin las funciones incorporadas.»
1. Implementar una función para sumar los números de un array
Vamos a reimplementar el filtro incorporado add para practicar recursión.
El caso base es que un array vacío tiene una suma de cero.
Impleméntalo por tu cuenta con una función recursiva; no uses el add incorporado.
[5, 4, 6, 10] | array_add # => 25
2. Invertir un array
Vamos a reimplementar el filtro incorporado reverse.
El caso base es que un array vacío invertido es un array vacío.
Impleméntalo por tu cuenta con una función recursiva; no uses el reverse incorporado.
[5, 4, 6, 10] | array_reverse # => [10, 6, 4, 5]
3. Mapear un array
Vamos a reimplementar el filtro incorporado map.
La función recibe un filtro como parámetro, ejecuta ese filtro para cada elemento del array de entrada y devuelve los resultados en un nuevo array.
El caso base es que un array vacío se mapea a un array vacío.
Impleméntalo por tu cuenta con una función recursiva; no uses el map incorporado.
[5, 4, 6, 10] | array_map(. + 10) # => [15, 14, 16, 20]
Ejercicio de aprendizaje
