Recursão mútua

Em matemática e ciência da computação, recursão mútua é uma forma de recursão em que dois objetos matemáticos ou computacionais, como funções ou tipos de dados, são definidos em termos do outro. Recursão mútua é muito comum em programação funcional e, em alguns domínios de problemas, tais como o analisador sintático descendente recursivo, onde os tipos de dados são naturalmente mutuamente recursivos, mas é incomum em outros domínios.

Exemplos

Tipos de Dados

O exemplo básico mais importante de um tipo de dados que pode ser definido por recursão mútua é uma árvore, que pode ser mutuamente definida recursivamente em termos de uma floresta (uma lista de árvores). Simbolicamente:

f: [t[1], ..., t[k]]
t: v f

Uma floresta f consiste de uma lista de árvores, enquanto uma árvore t consiste em um par de um valor v e uma floresta f (seus filhos). Esta definição é elegante e fácil de trabalhar abstratamente (tal como, quando provar teoremas sobre as propriedades de árvores), como expressa uma árvore em termos simples: uma lista de um tipo e um par de dois tipos. Além disso, ele corresponde a muitos algoritmos de árvores, que consistem em fazer uma coisa com o valor, e outra coisa com os filhos.

Esta definição mutuamente recursiva pode ser convertida para uma única definição recursiva por incluir a definição de uma floresta:

t: v [t[1], ..., t[k]]

Uma árvore t consiste em um par de um valor v e uma lista de árvores (seus filhos). Esta definição é mais compacta, mas aqui está uma um pouco mais complicado: uma árvore é composta de um par de um tipo e uma lista de outro, que exigem desentrelaçar para comprovar os resultados.

Em Standard ML, a árvore e a floresta tipos de dados podem ser mutuamente recursivamente definidos como se segue, permitindo árvores vazias:

datatype 'a tree = Empty | Node of 'a * 'a forest
and      'a forest = Nil | Cons of 'a tree * 'a forest

As funções do computador

Assim como algoritmos recursivos, tipos de dados podem, naturalmente, ser dados através de funções recursivas, algoritmos em estruturas de dados mutuamente recursivas  podem ser, naturalmente, dadas por funções mutuamente recursivas. Exemplos comuns incluem algoritmos de árvores, e analisador sintático descendente recursivo. Tal como acontece com recursão direta, otimização de chamada de cauda é necessária se a profundidade da recursão é grande ou ilimitada, como o uso de recursão mútua para multitarefa. Observe que a otimização de chamada de cauda em geral (quando a função chamada não é o mesmo que a função original, como nas chamadas de cauda recursivas) pode ser mais difícil de implementar do que o caso especial de otimização de chamada de cauda recursiva, e, portanto, a implementação eficiente de recursão mútua pode estar ausente de linguagens que apenas otimizam chamadas de cauda recursivas. Em linguagens como Pascal que requerem a declaração antes do uso, funções mutuamente recursivas requerem a declaração à frente, como uma referência à frente não pode ser evitada quando definem ela.

Tal como acontece com funções recursivas, uma função diretamente recursiva pode ser útil, com as funções mutuamente recursivas definidas como funções aninhadas dentro de seu âmbito de aplicação se esta é suportada. Isto é particularmente útil para compartilhar o estado através de um conjunto de funções sem ter que passar parâmetros entre eles.

Exemplos básicos

Um exemplo de recursividade mútua, que é reconhecidamente artificial, é determinar se um número não negativo é par ou é ímpar por ter duas funções separadas e chamando umas às outras, decrescendo a cada vez. Em C:Estas funções são baseadas na observação de que a questão 4 é par? é equivalente a 3 é ímpar?, que por sua vez é equivalente a 2 é par?, e assim por diante até a 0. Este exemplo usa uma única recursão mútua, e pode ser facilmente substituído por iteração. Neste exemplo, as chamadas mutuamente recursivas são chamadas de cauda, e otimização de chamada de cauda seria necessário para que isso execute no espaço de pilha constante; em C isso levaria O (n) espaço de pilha, a não ser que seja reescrito usando saltos em vez de chamadas.  Isto pode ser reduzido a uma única função recursiva is_even, com is_odd chamando is_even, mas is_even apenas chamando a si própria, com is_odd embutidos.

Como uma classe mais geral de exemplos, um algoritmo em uma árvore pode ser decomposto em seu comportamento em um valor e seu comportamento nos filhos, e pode ser dividido em duas funções mutuamente recursivas, uma especificando o comportamento em uma árvore, chamando a função floresta para a floresta de filhos, e uma especificando o comportamento em uma floresta, chamando a função árvore para árvore na floresta. Em Python: Neste caso, a função árvore chama a função floresta por uma única recursão, mas a função floresta chama a função árvore por recursões múltiplas.

Usando os tipo de dados Standard ML acima, o tamanho de uma árvore (número de nós) pode ser calculado através da seguinte funções mutuamente recursivas:Um exemplo mais detalhado no esquema, a contagem de folhas de uma árvore:Estes exemplos reduzem facilmente a uma única função recursiva por inclusão a função floresta na função árvore, o que é normalmente feito na prática: funções diretamente recursiva que operam em árvores sequencialmente processam o valor do nó e recursos sobre os filhos dentro de uma função, em vez de dividi-los em duas funções distintas.

Exemplos avançados

Um exemplo mais complicado é dado pelo analisador sintático descendente recursivo, que pode ser, naturalmente, implementado por ter uma função para cada regra de produção de uma gramática, que, em seguida, mutuamente recursiva; este será em geral recursão múltipla, como regras de produção geralmente combinam várias partes. Isso também pode ser feito sem recursividade mútua, por exemplo, por ainda ter funções separadas para cada regra de produção, mas tê-los chamado por um único controlador de função, ou colocando toda a gramática em uma única função.

Recursividade mútua pode também implementar um máquina de estado finito, com uma função para cada estado, e única recursão na mudança de estado; isto requer otimização de chamada de cauda se o número de alterações de estado é grande ou ilimitados. Isso pode ser usado como uma forma simples de multitarefa cooperativa. Uma abordagem semelhante para multitarefa é em vez disso usar, co-rotinas , que se chamam umas às outras, onde, em vez de a terminar chamando outra rotina, uma co-rotina cede a outra, mas não terminar, e, em seguida, retoma a execução quando é produzida de volta. Isto permite que co-rotinas individuais armazenem o estado, sem precisarem ser passados por parâmetros ou estarem armazenadas em variáveis compartilhadas.

Existem também alguns algoritmos que, naturalmente, têm duas fases, tais como minimax (min e max), e estes podem ser implementados por ter cada fase em uma função separada com recursividade mútua, embora eles também possam ser combinados em uma única função com recursão direta.

Funções matemáticas

Em matemática, a sequência Hofstadter, Masculino e Feminino, as sequências são um exemplo de um par de sequências de números inteiros definidos de forma mutuamente recursiva.

Os fractais podem ser calculadas (até uma determinada resolução) através de funções recursivas. Às vezes, isso pode ser feito de modo mais elegante através de funções mutuamente recursivas; o Sierpiński curva é um bom exemplo.

Prevalência

Recursão mútua é muito comum no estilo programação funcional, e é muitas vezes utilizada para programas escritos em LISP, Scheme, ML, e línguagens semelhantes. Em linguagens como o Prolog, recursão mútua é quase inevitável.

Alguns estilos de programação desencorajar recursividade mútua, alegando que ela pode ser confuso para distinguir as condições que irá retornar uma resposta a condições que poderiam permitir a execução de código para sempre, sem produzir uma resposta. Peter Norvig aponta para um padrão de projeto que desestimula o uso inteiramente, afirmando: Se você tem duas funções mutuamente recursivas que tanto alteram o estado de um objeto, tente mover quase toda a funcionalidade em apenas uma das funções. Caso contrário, você provavelmente vai acabar com duplicação de código.

Terminologia

Recursividade mútua é também conhecida como recursão indireta, por contraste com a recursão direta, onde uma única função chama a si mesmo diretamente. Isto é simplesmente uma diferença de ênfase, não uma noção diferente: "recursão indireta", enfatiza uma função individual, enquanto "recursão mútua", enfatiza o conjunto de funções, e não identifica uma função individual. Por exemplo, se f chama a si próprio, que é recursão direta. Mas se, ao invés disso, f chama g e g chama f, que por sua vez chama g novamente, do ponto de vista de f sozinho, f é indiretamente recursivo, enquanto do ponto de vista de g sozinho, g é indiretamente recursivo, enquanto do ponto de vista de ambos, f e g são mutuamente recursivos um sobre o outro. Da mesma forma, um conjunto de três ou mais funções que chamam uns aos outros pode ser chamado de um conjunto de funções mutuamente recursivas.

A conversão de recursão direta

Matematicamente, um conjunto de funções mutuamente são primitivas recursivas, o que pode ser comprovado pelo curso-de-valores de recursão, a construção de uma única função F que lista os valores da função recursiva individual no fim: e reescrever a recursão mútua como uma recursão primitiva.

Qualquer recursividade mútua entre os dois procedimentos podem ser convertidos para recursão direta por inclusão o código de um procedimento para o outro. Se há apenas um local onde um procedimento chama outro, isso é simples, caso contrário, isso pode envolver a duplicação de código. Em termos de pilha de chamada, dois procedimentos mutuamente recursivos produzem uma pilha ABABAB..., e por inclusão B em A produz a recursão direta (AB)(AB)(AB)...

Em alternativa, qualquer número de procedimentos podem ser mesclados em um único procedimento que recebe como argumento uma variante de registro (ou tipo de dados algébricos), que representam a seleção de um procedimento e seus argumentos; procedimento mesclados, em seguida, distribui em seu argumento para executar o código correspondente e utiliza recursão direta para chamar a si mesmo, conforme apropriado. Isto pode ser visto como uma aplicação limitada de desfuncionalização. Esta tradução pode ser útil quando qualquer um dos procedimentos mutuamente recursivas podem ser chamados por fora do código, então não há nenhum caso óbvio de inclusão de um procedimento para o outro. Esse código, em seguida, precisa ser modificado para que as chamadas de procedimento sejam realizadas através do agrupamento de argumentos para uma variante de registro como descrito; como alternativa, procedimentos diretamente recursivos podem ser utilizados para esta tarefa.

Ver também

• A recursão (ciência da computação)
• Dependência Circular

Referências

• Harper, Robert (2000), Programming in Standard ML 
• Harvey, Brian; Wright, Matthew (1999). Simply Scheme: Introducing Computer Science. [S.l.]: MIT Press. ISBN 978-0-26208281-5 
• Hutton, Graham (2007). Programming in Haskell. [S.l.]: Cambridge University Press. ISBN 978-0-52169269-4 

Ligações externas

• «Recursão mútua».  em Rosetta Código 
• "Exemplo demonstrando o bom uso de recursão mútua", "há algum exemplo de recursão mútua?", Estouro De Pilha