Recursive Functions

Recursion

Recursive functions are functions that call themselves.

A recursive function needs to have at least one base case and at least one recursive case.

A base case returns a value without calling the function again. A recursive case calls the function again, modifying the input so that it will at some point match the base case.

Here is an example that counts the elements of an array.

def count:
  if length == 0 then
    0                       # base case
  else
    1 + (.[1:] | count)     # recursive case
  end;

([] | count),           # => 0
([11, 22, 33] | count)  # => 3

A recursive function can have many base cases and/or many recursive cases. For example the Fibonacci sequence is a recursive sequence with two base cases.

def fibonacci:
  if . == 0 then
    0
  elif . == 1 then
    1
  else
    (. - 1 | fibonacci) + (. - 2 | fibonacci)
  end;

10 | fibonacci          # => 55

Counting the number of occurrences of some given value x in a list has two recursive cases.

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 practice, iterating over lists and other enumerable data structures is most often done using builtin functions, such as map and reduce, or by using streams like [.[] | select(...)]. Under the hood, some builtins are implemented using recursion.