Recursão em

Sobre 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 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 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 da biblioteca padrão, como map e reduce, ou usando streams como [.[] | select(...)]. Por baixo dos panos, algumas funções da biblioteca padrão são implementadas usando recursão.

Recursão infinita

As funções recursivas, se forem implementadas de forma incorreta, podem nunca retornar o resultado. Isso pode ser um problema, porque a cada chamada de função uma referência é guardada na memória, no lugar onde a VM deve retornar o resultado (na pilha de chamadas). Se uma função recursiva chamar a si mesma infinitamente, é possível ficar sem memória e fazer a VM travar com um erro de estouro de pilha.

Esse problema de recursão infinita pode ser causado por:

• Esquecer de implementar um caso base.
• Não definir o caso base como a primeira cláusula.
• Não modificar o argumento corretamente ao fazer a chamada recursiva e, assim, nunca chegar ao caso base.

Otimização de chamada de cauda

Como descrita na Wikipédia:

Uma chamada de cauda é uma chamada de sub-rotina executada como a ação final de um procedimento. Se o destino da cauda é a mesma sub-rotina, diz-se que a sub-rotina é recursiva de cauda.

Considere a implementação de fibonacci mostrada acima. O caso recursivo chama a si mesmo duas vezes. A última ação que a função precisa realizar é uma adição. Como a última ação não é uma chamada a si mesma, essa função é recursiva, mas não é recursiva de cauda.

Algumas linguagens implementam a otimização de chamada de cauda, de modo que a chamada de cauda pode reutilizar o quadro atual da pilha em vez de precisar adicionar um novo quadro à pilha de chamadas. Isso pode trazer ganhos de desempenho, além de proteger contra o temido estouro de pilha.

O jq implementa a otimização de chamada de cauda, mas apenas para funções de aridade 0. A forma de aproveitar isso é definir uma função "interna" de aridade 0 que recebe algum tipo de estado como entrada. A função interna pode modificar o estado conforme necessário e passar o novo estado para a chamada recursiva de cauda. A função externa cria o estado inicial e o passa para a função interna para iniciar a recursão.

Uma função fibonacci recursiva de cauda poderia ser implementada mantendo a série calculada até o momento como parte do estado.

def fibonacci:
  def _fib:
    # input: {limit: number, series: array}
    if (.series | length - 1) >= .limit then
      .series[.limit]                                   # base case
    else
      .series += [.series[-1] + .series[-2]] | _fib     # recursive case
    end;
  {limit: ., series: [0, 1]} | _fib;

10 | fibonacci          # => 55