Recursão em

Sobre Recursão

As funções recursivas são funções que se chamam a si próprias.

Uma função recursiva tem de ter pelo menos um caso base e pelo menos um caso recursivo.

Um caso base devolve um valor sem voltar a chamar a função. Um caso recursivo chama a função outra vez, modificando o valor de entrada para que este acabe por corresponder ao caso base.

Eis 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 numa 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, a iteração sobre listas e outras estruturas de dados enumeráveis faz-se quase sempre com funções incorporadas, como map e reduce, ou usando streams como [.[] | select(...)]. Internamente, algumas funções incorporadas são implementadas com recursão.

Recursão infinita

As funções recursivas, se forem implementadas incorretamente, podem nunca devolver o seu resultado. Isto pode ser problemático porque, sempre que se chama uma função, é guardada na memória uma referência ao local onde a máquina virtual deve devolver o resultado (na pilha de chamadas). Se uma função recursiva se chamar a si própria infinitamente, é possível ficar sem memória, o que faz a máquina virtual falhar com um erro de stack overflow.

Este problema de recursão infinita pode dever-se a:

• Esqueceres-te de implementar um caso base.
• Não definires o caso base como a primeira cláusula.
• Não modificares o argumento devidamente ao fazer a chamada recursiva e, por isso, nunca chegares ao caso base.

Otimização de chamadas de cauda

Como descrito na Wikipédia:

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

Repara na implementação de fibonacci apresentada acima. O caso recursivo chama-se a si próprio duas vezes. A última ação que a função tem de executar é uma soma. Como a última ação não é uma chamada a si própria, a função é recursiva, mas não é recursiva de cauda.

Algumas linguagens implementam a otimização de chamadas de cauda, de forma que a chamada de cauda pode reutilizar o frame atual da pilha em vez de ter de acrescentar um novo frame à pilha de chamadas. Isto pode trazer benefícios de desempenho, além de proteger contra o temido stack overflow.

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

Uma função fibonacci recursiva de cauda pode ser implementada mantendo a série calculada até ao 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