Recursão (ciência da computação) - Recursion (computer science)

Árvore criada usando a linguagem de programação Logo e dependendo muito da recursão. Cada ramo pode ser visto como uma versão menor de uma árvore.

Na ciência da computação , a recursão é um método de resolver um problema em que a solução depende de soluções para instâncias menores do mesmo problema. Esses problemas geralmente podem ser resolvidos por iteração , mas isso precisa identificar e indexar as instâncias menores no momento da programação. A recursão resolve esses problemas recursivos usando funções que chamam a si mesmas de dentro de seu próprio código. A abordagem pode ser aplicada a muitos tipos de problemas e a recursão é uma das idéias centrais da ciência da computação.

O poder da recursão evidentemente reside na possibilidade de definir um conjunto infinito de objetos por uma declaração finita. Da mesma maneira, um número infinito de cálculos pode ser descrito por um programa recursivo finito, mesmo que esse programa não contenha repetições explícitas.

-  Niklaus Wirth , Algorithms + Data Structures = Programs , 1976

A maioria das linguagens de programação de computador oferece suporte à recursão, permitindo que uma função chame a si mesma de dentro de seu próprio código. Algumas linguagens de programação funcional (por exemplo, Clojure ) não definem nenhuma construção de loop, mas contam apenas com a recursão para chamar o código repetidamente. Está provado na teoria da computabilidade que essas linguagens apenas recursivas são Turing completas ; isso significa que eles são tão poderosos (eles podem ser usados ​​para resolver os mesmos problemas) quanto as linguagens imperativas baseadas em estruturas de controle como whilee for.

Chamar repetidamente uma função de dentro dela mesma pode fazer com que a pilha de chamadas tenha um tamanho igual à soma dos tamanhos de entrada de todas as chamadas envolvidas. Conclui-se que, para problemas que podem ser resolvidos facilmente por iteração, a recursão é geralmente menos eficiente e, para problemas grandes, é fundamental usar técnicas de otimização, como a otimização de chamada de cauda .

Funções recursivas e algoritmos

Uma tática comum de programação de computador é dividir um problema em subproblemas do mesmo tipo que o original, resolver esses subproblemas e combinar os resultados. Isso geralmente é conhecido como método de dividir e conquistar ; quando combinado com uma tabela de pesquisa que armazena os resultados de subproblemas resolvidos anteriormente (para evitar resolvê-los repetidamente e incorrer em tempo de computação extra), pode ser referido como programação dinâmica ou memoização .

Caso base

Uma definição de função recursiva tem um ou mais casos base , significando entrada (s) para a qual a função produz um resultado trivialmente (sem recorrente), e um ou mais casos recursivos , significando entrada (s) para as quais o programa se repete (chama a si mesmo) . Por exemplo, a função fatorial pode ser definida recursivamente pelas equações 0! = 1 e, para todo n > 0 , n ! = n ( n - 1)! . Nenhuma das equações por si só constitui uma definição completa; o primeiro é o caso base e o segundo é o caso recursivo. Como o caso base quebra a cadeia de recursão, às vezes também é chamado de "caso final".

O trabalho dos casos recursivos pode ser visto como a quebra de entradas complexas em outras mais simples. Em uma função recursiva adequadamente projetada, com cada chamada recursiva, o problema de entrada deve ser simplificado de tal forma que, eventualmente, o caso base deve ser alcançado. (Funções que não devem terminar em circunstâncias normais - por exemplo, alguns processos do sistema e do servidor - são uma exceção a isso.) Negligenciar a escrita de um caso base ou testá-lo incorretamente pode causar um loop infinito .

Para algumas funções (como aquela que calcula a série para e = 1/0! + 1/1! + 1/2! + 1/3! + ... ), não há um caso básico óbvio implícito nos dados de entrada ; para estes, pode-se adicionar um parâmetro (como o número de termos a serem adicionados, em nosso exemplo de série) para fornecer um 'critério de parada' que estabelece o caso base. Esse exemplo é mais naturalmente tratado por correcursão , onde os termos sucessivos na saída são as somas parciais; este pode ser convertido a um recursão usando o parâmetro de indexação para dizer "calcular o n ésimo termo ( n th soma parcial)".

Tipos de dados recursivos

Muitos programas de computador devem processar ou gerar uma quantidade arbitrariamente grande de dados . A recursão é uma técnica para representar dados cujo tamanho exato é desconhecido para o programador : o programador pode especificar esses dados com uma definição autorreferencial . Existem dois tipos de definições autorreferenciais: definições indutivas e coindutivas .

Dados definidos indutivamente

Uma definição de dados recursiva definida indutivamente é aquela que especifica como construir instâncias dos dados. Por exemplo, listas vinculadas podem ser definidas indutivamente (aqui, usando a sintaxe Haskell ):

data ListOfStrings = EmptyList | Cons String ListOfStrings

O código acima especifica uma lista de strings vazia ou uma estrutura que contém uma string e uma lista de strings. A auto-referência na definição permite a construção de listas de qualquer número (finito) de strings.

Outro exemplo de definição indutiva são os números naturais (ou inteiros positivos ):

A natural number is either 1 or n+1, where n is a natural number.

De forma semelhante, as definições recursivas são freqüentemente usadas para modelar a estrutura de expressões e instruções em linguagens de programação. Os designers de linguagem freqüentemente expressam gramáticas em uma sintaxe como a forma Backus – Naur ; aqui está essa gramática, para uma linguagem simples de expressões aritméticas com multiplicação e adição:

 <expr> ::= <number>
          | (<expr> * <expr>)
          | (<expr> + <expr>)

Isso diz que uma expressão é um número, produto de duas expressões ou a soma de duas expressões. Referindo-se recursivamente a expressões na segunda e terceira linhas, a gramática permite expressões aritméticas arbitrariamente complicadas, como (5 * ((3 * 6) + 8)), com mais de um produto ou operação de soma em uma única expressão.

Dados coindutivamente definidos e correcursão

Uma definição de dados coindutivos é aquela que especifica as operações que podem ser executadas em um dado; normalmente, definições coindutivas autorreferenciais são usadas para estruturas de dados de tamanho infinito.

Uma definição coindutiva de fluxos infinitos de strings, dada informalmente, pode ser assim:

A stream of strings is an object s such that:
 head(s) is a string, and
 tail(s) is a stream of strings.

Isso é muito semelhante a uma definição indutiva de listas de strings; a diferença é que isso especifica definição como acessar o conteúdo da estrutura de dados, ou seja, através dos acessores funções heade tail-e que esses conteúdos podem ser, ao passo que especifica definição indutiva como criar a estrutura e o que pode ser criado a partir.

A correcursão está relacionada à coindução e pode ser usada para calcular instâncias particulares de (possivelmente) objetos infinitos. Como técnica de programação, ela é usada com mais frequência no contexto de linguagens de programação preguiçosas e pode ser preferível à recursão quando o tamanho ou a precisão desejados da saída de um programa são desconhecidos. Em tais casos, o programa requer uma definição para um resultado infinitamente grande (ou infinitamente preciso) e um mecanismo para obter uma porção finita desse resultado. O problema de calcular os primeiros n números primos pode ser resolvido com um programa correcursivo (por exemplo, aqui ).

Tipos de recursão

Recursão única e recursão múltipla

A recursão que contém apenas uma única auto-referência é conhecida como recursão única , enquanto a recursão que contém múltiplas referências próprias é conhecida comorecursão múltipla . Exemplos padrão de recursão única incluem travessia de lista, como em uma pesquisa linear ou computando a função fatorial, enquanto exemplos padrão de recursão múltipla incluemtravessia de árvore, como em uma pesquisa em profundidade.

A recursão única costuma ser muito mais eficiente do que a recursão múltipla e geralmente pode ser substituída por uma computação iterativa, executada em tempo linear e exigindo espaço constante. A recursão múltipla, por outro lado, pode exigir tempo e espaço exponencial e é mais fundamentalmente recursiva, não podendo ser substituída por iteração sem uma pilha explícita.

A recursão múltipla às vezes pode ser convertida em recursão única (e, se desejado, daí em iteração). Por exemplo, embora o cálculo da sequência de Fibonacci ingenuamente seja uma iteração múltipla, como cada valor requer dois valores anteriores, ele pode ser calculado por recursão única, passando dois valores sucessivos como parâmetros. Isso é mais naturalmente enquadrado como correcursão, construindo a partir dos valores iniciais, rastreando em cada etapa dois valores sucessivos - ver correcursão: exemplos . Um exemplo mais sofisticado é o uso de uma árvore binária encadeada , que permite a travessia iterativa da árvore, em vez de recursão múltipla.

Recursão indireta

A maioria dos exemplos básicos de recursão e a maioria dos exemplos apresentados aqui demonstram recursão direta , na qual uma função chama a si mesma. A recursão indireta ocorre quando uma função é chamada não por si mesma, mas por outra função que ela chamou (direta ou indiretamente). Por exemplo, se f chama f, isso é recursão direta, mas se f chama g que chama f, então isso é recursão indireta de f. Cadeias de três ou mais funções são possíveis; por exemplo, a função 1 chama a função 2, a função 2 chama a função 3 e a função 3 chama a função 1 novamente.

A recursão indireta também é chamada de recursão mútua , que é um termo mais simétrico, embora seja simplesmente uma diferença de ênfase, não uma noção diferente. Ou seja, se f chama ge então g chama f, que por sua vez chama g novamente, do ponto de vista de f sozinho, f é indiretamente recorrente, enquanto do ponto de vista de g sozinho, é indiretamente recorrente, enquanto do ponto de vista de ambos, f e g se repetem mutuamente. Da mesma forma, um conjunto de três ou mais funções que se chamam pode ser chamado de um conjunto de funções recursivas mutuamente.

Recursão anônima

A recursão geralmente é feita chamando explicitamente uma função pelo nome. No entanto, a recursão também pode ser feita por meio da chamada implícita de uma função com base no contexto atual, o que é particularmente útil para funções anônimas e é conhecido como recursão anônima .

Recursão estrutural versus generativa

Alguns autores classificam a recursão como "estrutural" ou "generativa". A distinção está relacionada a onde um procedimento recursivo obtém os dados em que trabalha e como ele processa esses dados:

[Funções que consomem dados estruturados] normalmente decompõem seus argumentos em seus componentes estruturais imediatos e, em seguida, processam esses componentes. Se um dos componentes imediatos pertencer à mesma classe de dados da entrada, a função é recursiva. Por esse motivo, nos referimos a essas funções como FUNÇÕES (ESTRUTURALMENTE) RECURSIVAS.

-  Felleisen, Findler, Flatt e Krishnaurthi, How to Design Programs , 2001

Assim, a característica definidora de uma função estruturalmente recursiva é que o argumento para cada chamada recursiva é o conteúdo de um campo da entrada original. A recursão estrutural inclui quase todas as travessias de árvore, incluindo processamento XML, criação de árvore binária e pesquisa, etc. Considerando a estrutura algébrica dos números naturais (ou seja, um número natural é zero ou o sucessor de um número natural), funções como como fatorial também pode ser considerada como recursão estrutural.

A recursão gerativa é a alternativa:

Muitos algoritmos recursivos bem conhecidos geram um dado inteiramente novo a partir dos dados fornecidos e recorrem a ele. HtDP ( How to Design Programs ) refere-se a este tipo como recursão generativa. Exemplos de recursão generativa incluem: gcd , quicksort , pesquisa binária , mergesort , método de Newton , fractais e integração adaptativa .

-  Matthias Felleisen, Programação Funcional Avançada , 2002

Esta distinção é importante para provar o término de uma função.

  • Todas as funções estruturalmente recursivas em estruturas de dados finitas ( definidas indutivamente ) podem ser facilmente mostradas para terminar, via indução estrutural : intuitivamente, cada chamada recursiva recebe um pedaço menor de dados de entrada, até que um caso base seja alcançado.
  • As funções generativamente recursivas, em contraste, não necessariamente fornecem entrada menor para suas chamadas recursivas, portanto, a prova de seu encerramento não é necessariamente tão simples, e evitar loops infinitos requer maior cuidado. Essas funções generativamente recursivas podem frequentemente ser interpretadas como funções correcursivas - cada etapa gera os novos dados, como a aproximação sucessiva no método de Newton - e encerrar essa correcursão requer que os dados eventualmente satisfaçam alguma condição, o que não é necessariamente garantido.
  • Em termos de variantes de loop , recursão estrutural é quando há uma variante de loop óbvia, ou seja, tamanho ou complexidade, que começa finita e diminui a cada passo recursivo.
  • Por outro lado, a recursão generativa ocorre quando não existe uma variante de loop óbvia e o término depende de uma função, como "erro de aproximação" que não necessariamente diminui para zero e, portanto, o término não é garantido sem análise adicional.

Problemas de implementação

Na implementação real, em vez de uma função recursiva pura (verificação única para o caso base, caso contrário, etapa recursiva), uma série de modificações podem ser feitas, para fins de clareza ou eficiência. Esses incluem:

  • Função Wrapper (no topo)
  • Curto-circuito no caso base, também conhecido como "recursão à distância do braço" (na parte inferior)
  • Algoritmo híbrido (na parte inferior) - mudar para um algoritmo diferente quando os dados forem pequenos o suficiente

Com base na elegância, as funções de invólucro são geralmente aprovadas, enquanto um curto-circuito no case básico é desaprovado, especialmente na academia. Os algoritmos híbridos são freqüentemente usados ​​para eficiência, para reduzir a sobrecarga de recursão em casos pequenos, e a recursão à distância de um braço é um caso especial disso.

Função Wrapper

Uma função de invólucro é uma função que é chamada diretamente, mas não se repete, chama uma função auxiliar separada que realmente faz a recursão.

As funções de invólucro podem ser usadas para validar parâmetros (de modo que a função recursiva pode ignorá-los), realizar a inicialização (alocar memória, inicializar variáveis), particularmente para variáveis ​​auxiliares, como "nível de recursão" ou cálculos parciais para memoização e lidar com exceções e erros . Em linguagens que suportam funções aninhadas , a função auxiliar pode ser aninhada dentro da função wrapper e usar um escopo compartilhado. Na ausência de funções aninhadas, as funções auxiliares são, em vez disso, uma função separada, se possível privada (já que não são chamadas diretamente), e as informações são compartilhadas com a função de invólucro usando passagem por referência .

Curto-circuito do case base

Fatorial: comum vs. curto-circuito
Recursão ordinária Recursão de curto-circuito
int fac1(int n) {
   if (n <= 0)
      return 1;
   else
      return fac1(n-1)*n;
}
static int fac2(int n) {
   // assert(n >= 2);
   if (n == 2)
      return 2;
   else
      return fac2(n-1)*n;
}
int fac2wrapper(int n) {
   if (n <= 1)
      return 1;
   else
      return fac2(n);
}

O curto-circuito do caso base, também conhecido como recursão arm's-length , consiste em verificar o caso base antes de fazer uma chamada recursiva - ou seja, verificar se a próxima chamada será o caso base, em vez de chamar e, em seguida, verificar o caso base . O curto-circuito é feito principalmente por razões de eficiência, para evitar a sobrecarga de uma chamada de função que retorna imediatamente. Observe que, uma vez que o caso base já foi verificado (imediatamente antes da etapa recursiva), ele não precisa ser verificado separadamente, mas é necessário usar uma função de invólucro para o caso em que a recursão geral começa com o caso base em si. Por exemplo, na função fatorial, corretamente o caso base é 0! = 1, retornando imediatamente 1 para 1! é um curto-circuito e pode falhar 0; isso pode ser atenuado por uma função de invólucro. A caixa mostra o código C para atalhos para os casos fatoriais 0 e 1.

O curto-circuito é principalmente uma preocupação quando muitos casos base são encontrados, como ponteiros nulos em uma árvore, que podem ser lineares no número de chamadas de função, portanto, economia significativa para algoritmos O ( n ) ; isso é ilustrado abaixo para uma pesquisa em profundidade. O curto-circuito em uma árvore corresponde a considerar uma folha (nó não vazio sem filhos) como o caso base, em vez de considerar um nó vazio como o caso base. Se houver apenas um único caso base, como no cálculo do fatorial, o curto-circuito fornece apenas economia de O (1) .

Conceitualmente, o curto-circuito pode ser considerado como tendo o mesmo caso base e etapa recursiva, verificando o caso base apenas antes da recursão, ou pode ser considerado como tendo um caso base diferente (uma etapa removida do caso base padrão) e um passo recursivo mais complexo, a saber "verificar válido e depois recursar", como ao considerar nós folha em vez de nós nulos como casos base em uma árvore. Como o curto-circuito tem um fluxo mais complicado, em comparação com a separação clara do caso base e da etapa recursiva na recursão padrão, ele costuma ser considerado um estilo pobre, especialmente na academia.

Pesquisa em profundidade

Um exemplo básico de curto-circuito é dado na pesquisa em profundidade (DFS) de uma árvore binária; veja a seção de árvores binárias para uma discussão recursiva padrão.

O algoritmo recursivo padrão para um DFS é:

  • caso base: se o nó atual for nulo, retorna falso
  • etapa recursiva: caso contrário, verifique o valor do nó atual, retorne verdadeiro se corresponder, caso contrário, recorra nos filhos

Em curto-circuito, é em vez disso:

  • verificar o valor do nó atual, retornar verdadeiro se corresponder,
  • caso contrário, em crianças, se não Nulo, então recurse.

Em termos das etapas padrão, isso move a verificação do caso base antes da etapa recursiva. Alternativamente, eles podem ser considerados uma forma diferente de caso base e etapa recursiva, respectivamente. Observe que isso requer uma função de invólucro para lidar com o caso quando a própria árvore está vazia (o nó raiz é Nulo).

No caso de uma árvore binária perfeita de altura h, há 2 h +1 −1 nós e 2 h +1 ponteiros nulos como filhos (2 para cada uma das 2 h folhas), portanto, o curto-circuito reduz o número de funções chamadas pela metade no pior dos casos.

Em C, o algoritmo recursivo padrão pode ser implementado como:

bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // base case
    else if (tree_node->data == i)
        return true;
    else
        return tree_contains(tree_node->left, i) ||
               tree_contains(tree_node->right, i);
}

O algoritmo em curto-circuito pode ser implementado como:

// Wrapper function to handle empty tree
bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // empty tree
    else
        return tree_contains_do(tree_node, i);  // call auxiliary function
}

// Assumes tree_node != NULL
bool tree_contains_do(struct node *tree_node, int i) {
    if (tree_node->data == i)
        return true;  // found
    else  // recurse
        return (tree_node->left  && tree_contains_do(tree_node->left,  i)) ||
               (tree_node->right && tree_contains_do(tree_node->right, i));
}

Observe o uso da avaliação de curto-circuito dos operadores booleanos && (AND), de forma que a chamada recursiva seja feita apenas se o nó for válido (não nulo). Observe que, embora o primeiro termo no AND seja um ponteiro para um nó, o segundo termo é um booleano, portanto, a expressão geral é avaliada como um booleano. Este é um idioma comum em curto-circuito recursivo. Isso é um acréscimo à avaliação de curto-circuito do booleano || (OU) operador, para verificar apenas o filho direito se o filho esquerdo falhar. Na verdade, todo o fluxo de controle dessas funções pode ser substituído por uma única expressão booleana em uma instrução de retorno, mas a legibilidade não prejudica a eficiência.

Algoritmo híbrido

Os algoritmos recursivos são freqüentemente ineficientes para pequenos dados, devido à sobrecarga de chamadas e retornos de função repetidos. Por esta razão, implementações eficientes de algoritmos recursivos geralmente começam com o algoritmo recursivo, mas então mudam para um algoritmo diferente quando a entrada se torna pequena. Um exemplo importante é a classificação por mesclagem , que geralmente é implementada pela alternância para a classificação por inserção não recursiva quando os dados são suficientemente pequenos, como na classificação por mesclagem lado a lado . Os algoritmos recursivos híbridos podem frequentemente ser mais refinados, como no Timsort , derivados de uma classificação de fusão / inserção híbrida.

Recursão versus iteração

Recursão e iteração são igualmente expressivas: a recursão pode ser substituída por iteração com uma pilha de chamadas explícita , enquanto a iteração pode ser substituída por recursão final . Qual abordagem é preferível depende do problema em consideração e da linguagem usada. Na programação imperativa , a iteração é preferida, particularmente para recursão simples, pois evita a sobrecarga de chamadas de função e gerenciamento de pilha de chamadas, mas a recursão é geralmente usada para recursão múltipla. Por outro lado, em linguagens funcionais a recursão é preferida, com a otimização da recursão da cauda levando a pouca sobrecarga. Implementar um algoritmo usando iteração pode não ser facilmente alcançável.

Compare os modelos para calcular x n definido por x n = f (n, x n-1 ) da base x :

function recursive(n)
    if n == base
        return xbase
    else
        return f(n, recursive(n-1))
function iterative(n)
    x = xbase
    for i = base+1 to n
        x = f(i, x)
    return x

Para a linguagem imperativa, o overhead é definir a função, para a linguagem funcional, o overhead é definir a variável de acumulador x.

Por exemplo, uma função fatorial pode ser implementada iterativamente em C atribuindo a uma variável de índice de loop e uma variável de acumulador, em vez de passar argumentos e retornar valores por recursão:

unsigned int factorial(unsigned int n) {
  unsigned int product = 1; // empty product is 1
  while (n) {
    product *= n;
    --n;
  }
  return product;
}

Poder expressivo

A maioria das linguagens de programação em uso hoje permite a especificação direta de funções e procedimentos recursivos. Quando tal função é chamada, o ambiente de tempo de execução do programa rastreia as várias instâncias da função (geralmente usando uma pilha de chamadas , embora outros métodos possam ser usados). Cada função recursiva pode ser transformada em uma função iterativa substituindo chamadas recursivas por construções de controle iterativas e simulando a pilha de chamadas com uma pilha explicitamente gerenciada pelo programa.

Por outro lado, todas as funções e procedimentos iterativos que podem ser avaliados por um computador (ver completude de Turing ) podem ser expressos em termos de funções recursivas; Construções de controle iterativo, como loops while e loops for, são reescritas rotineiramente de forma recursiva em linguagens funcionais . No entanto, na prática, essa reescrita depende da eliminação da chamada de cauda , o que não é uma característica de todos os idiomas. C , Java e Python são linguagens dominantes notáveis ​​nas quais todas as chamadas de função, incluindo chamadas finais , podem causar alocação de pilha que não ocorreria com o uso de construções de loop; Nessas linguagens, um programa iterativo de trabalho reescrito em forma recursiva pode estourar a pilha de chamadas , embora a eliminação de chamadas finais possa ser um recurso que não é coberto pela especificação de uma linguagem e diferentes implementações da mesma linguagem podem diferir nos recursos de eliminação de chamadas finais.

Problemas de desempenho

Em linguagens (como C e Java ) que favorecem construções de loop iterativo, geralmente há um custo significativo de tempo e espaço associado a programas recursivos, devido à sobrecarga necessária para gerenciar a pilha e a relativa lentidão das chamadas de função; em linguagens funcionais , uma chamada de função (particularmente uma chamada final ) é normalmente uma operação muito rápida e a diferença geralmente é menos perceptível.

Como um exemplo concreto, a diferença de desempenho entre as implementações recursivas e iterativas do exemplo "fatorial" acima depende muito do compilador usado. Em linguagens onde as construções de loop são preferidas, a versão iterativa pode ser várias ordens de magnitude mais rápida do que a recursiva. Em linguagens funcionais, a diferença de tempo geral das duas implementações pode ser insignificante; na verdade, o custo de multiplicar os números maiores primeiro, em vez dos números menores (o que acontece com a versão iterativa fornecida aqui) pode sobrecarregar qualquer tempo economizado pela escolha da iteração.

Empilhar espaço

Em algumas linguagens de programação, o tamanho máximo da pilha de chamadas é muito menor do que o espaço disponível no heap , e algoritmos recursivos tendem a exigir mais espaço de pilha do que algoritmos iterativos. Conseqüentemente, essas linguagens às vezes colocam um limite na profundidade da recursão para evitar estouros de pilha ; Python é uma dessas linguagens. Observe a advertência abaixo em relação ao caso especial de recursão da cauda .

Vulnerabilidade

Como os algoritmos recursivos podem estar sujeitos a estouros de pilha, eles podem ser vulneráveis ​​a entradas patológicas ou maliciosas . Alguns malwares visam especificamente a pilha de chamadas de um programa e se beneficiam da natureza recursiva inerente da pilha. Mesmo na ausência de malware, um estouro de pilha causado por recursão ilimitada pode ser fatal para o programa, e a lógica de tratamento de exceções pode não impedir que o processo correspondente seja encerrado .

Multiplicar problemas recursivos

Problemas multiplamente recursivos são inerentemente recursivos, devido ao estado anterior que eles precisam rastrear. Um exemplo é a travessia da árvore como na pesquisa em profundidade ; embora os métodos recursivo e iterativo sejam usados, eles contrastam com o percurso de lista e a pesquisa linear em uma lista, que é um método recursivo único e, portanto, naturalmente iterativo. Outros exemplos incluem algoritmos de divisão e conquista , como Quicksort , e funções, como a função de Ackermann . Todos esses algoritmos podem ser implementados iterativamente com a ajuda de uma pilha explícita , mas o esforço do programador envolvido no gerenciamento da pilha e a complexidade do programa resultante, sem dúvida, superam quaisquer vantagens da solução iterativa.

Recursão de refatoração

Algoritmos recursivos podem ser substituídos por contrapartes não recursivas. Um método para substituir algoritmos recursivos é simulá-los usando a memória heap no lugar da memória stack . Uma alternativa é desenvolver um algoritmo de substituição totalmente baseado em métodos não recursivos, o que pode ser desafiador. Por exemplo, algoritmos recursivos para wildcards correspondentes , tais como Rich Salz ' wildmat algoritmo, uma vez foram típico. Algoritmos não recursivos para a mesma finalidade, como o algoritmo de correspondência de curingas Krauss , foram desenvolvidos para evitar as desvantagens da recursão e foram aprimorados apenas gradualmente com base em técnicas como coleta de testes e desempenho de criação de perfil .

Funções recursivas de cauda

As funções recursivas finais são funções nas quais todas as chamadas recursivas são chamadas finais e, portanto, não criam nenhuma operação adiada. Por exemplo, a função gcd (mostrada novamente abaixo) é recursiva na cauda. Em contraste, a função fatorial (também abaixo) não é recursiva na cauda; como sua chamada recursiva não está na posição final, ele cria operações de multiplicação adiada que devem ser realizadas após a conclusão da chamada recursiva final. Com um compilador ou interpretador que trata as chamadas recursivas de cauda como saltos em vez de chamadas de função, uma função recursiva de cauda, ​​como gcd, será executada usando espaço constante. Portanto, o programa é essencialmente iterativo, equivalente ao uso de estruturas de controle de linguagem imperativas, como os loops "for" e "while".

Recursão da cauda : Aumentando a recursão:
//INPUT: Integers x, y such that x >= y and y >= 0
int gcd(int x, int y)
{
  if (y == 0)
     return x;
  else
     return gcd(y, x % y);
}
//INPUT: n is an Integer such that n >= 0
int fact(int n)
{
   if (n == 0)
      return 1;
   else
      return n * fact(n - 1);
}

A importância da recursão final é que, ao fazer uma chamada recursiva final (ou qualquer chamada final), a posição de retorno do chamador não precisa ser salva na pilha de chamadas ; quando a chamada recursiva retornar, ela ramificará diretamente na posição de retorno salva anteriormente. Portanto, em linguagens que reconhecem essa propriedade de chamadas finais, a recursão final economiza espaço e tempo.

Ordem de execução

Considere estas duas funções:

Função 1

void recursiveFunction(int num) {
    printf("%d\n", num);
    if (num < 4)
        recursiveFunction(num + 1);
}

Recursive1.svg

Função 2

void recursiveFunction(int num) {
    if (num < 4)
        recursiveFunction(num + 1);
    printf("%d\n", num);
}

Recursive2.svg

A função 2 é a função 1 com as linhas trocadas.

No caso de uma função que chama a si mesma apenas uma vez, as instruções colocadas antes da chamada recursiva são executadas uma vez por recursão antes de qualquer uma das instruções colocadas após a chamada recursiva. Os últimos são executados repetidamente após a recursão máxima ter sido atingida.

Observe também que a ordem das instruções de impressão é invertida, o que se deve à maneira como as funções e instruções são armazenadas na pilha de chamadas .

Procedimentos recursivos

Fatorial

Um exemplo clássico de procedimento recursivo é a função usada para calcular o fatorial de um número natural :

Pseudocódigo (recursivo):
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ]
end factorial

A função também pode ser escrita como uma relação de recorrência :

Esta avaliação da relação de recorrência demonstra o cálculo que seria realizado na avaliação do pseudocódigo acima:

Calculando a relação de recorrência para n = 4:
b4           = 4 × b3
             = 4 × (3 × b2)
             = 4 × (3 × (2 × b1))
             = 4 × (3 × (2 × (1 × b0)))
             = 4 × (3 × (2 × (1 × 1)))
             = 4 × (3 × (2 × 1))
             = 4 × (3 × 2)
             = 4 × 6
             = 24

Esta função fatorial também pode ser descrita sem o uso de recursão, fazendo uso das construções de loop típicas encontradas em linguagens de programação imperativas:

Pseudocódigo (iterativo):
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. create new variable called running_total with a value of 1
2. begin loop 1. if n is 0, exit loop 2. set running_total to (running_total × n) 3. decrement n 4. repeat loop
3. return running_total
end factorial

O código imperativo acima é equivalente a esta definição matemática usando uma variável acumuladora t :

A definição acima se traduz diretamente em linguagens de programação funcionais , como Scheme ; este é um exemplo de iteração implementada recursivamente.

Maior divisor comum

O algoritmo euclidiano , que calcula o maior divisor comum de dois inteiros, pode ser escrito recursivamente.

Definição de função :

Pseudocódigo (recursivo):
function gcd is:
input: integer x, integer y such that x > 0 and y >= 0

1. if y is 0, return x 2. otherwise, return [ gcd( y, (remainder of x/y) ) ]
end gcd

Relação de recorrência para o maior divisor comum, onde expressa o restante de :

E se
Calculando a relação de recorrência para x = 27 ey = 9:
gcd(27, 9)   = gcd(9, 27 % 9)
             = gcd(9, 0)
             = 9
Calculando a relação de recorrência para x = 111 ey = 259:
gcd(111, 259)   = gcd(259, 111 % 259)
                = gcd(259, 111)
                = gcd(111, 259 % 111)
                = gcd(111, 37)
                = gcd(37, 111 % 37)
                = gcd(37, 0)
                = 37

O programa recursivo acima é recursivo na cauda ; é equivalente a um algoritmo iterativo, e o cálculo mostrado acima mostra as etapas de avaliação que seriam realizadas por uma linguagem que elimina as chamadas finais. Abaixo está uma versão do mesmo algoritmo usando iteração explícita, adequada para uma linguagem que não elimina chamadas finais. Ao manter seu estado inteiramente nas variáveis x e y e usando uma construção de loop, o programa evita fazer chamadas recursivas e crescendo a pilha de chamadas.

Pseudocódigo (iterativo):
function gcd is:
input: integer x, integer y such that x >= y and y >= 0
1. create new variable called remainder
2. begin loop 1. if y is zero, exit loop 2. set remainder to the remainder of x/y 3. set x to y 4. set y to remainder 5. repeat loop
3. return x
end gcd

O algoritmo iterativo requer uma variável temporária, e mesmo com o conhecimento do algoritmo euclidiano é mais difícil entender o processo por simples inspeção, embora os dois algoritmos sejam muito semelhantes em seus passos.

Torres de Hanói

Torres de Hanói

The Towers of Hanoi é um quebra-cabeça matemático cuja solução ilustra a recursão. Existem três pinos que podem conter pilhas de discos de diferentes diâmetros. Um disco maior nunca pode ser empilhado sobre um menor. Começando com n discos em um pino, eles devem ser movidos para outro pino por vez. Qual é o menor número de etapas para mover a pilha?

Definição de função :

Relação de recorrência para hanoi :

Calculando a relação de recorrência para n = 4:
hanoi(4)     = 2×hanoi(3) + 1
             = 2×(2×hanoi(2) + 1) + 1
             = 2×(2×(2×hanoi(1) + 1) + 1) + 1
             = 2×(2×(2×1 + 1) + 1) + 1
             = 2×(2×(3) + 1) + 1
             = 2×(7) + 1
             = 15


Implementações de exemplo:

Pseudocódigo (recursivo):
function hanoi is:
input: integer n, such that n >= 1
1. if n is 1 then return 1
2. return [2 * [call hanoi(n-1)] + 1]
end hanoi

Embora nem todas as funções recursivas tenham uma solução explícita, a sequência da Torre de Hanoi pode ser reduzida a uma fórmula explícita.

Uma fórmula explícita para Torres de Hanói:
h1 = 1   = 21 - 1
h2 = 3   = 22 - 1
h3 = 7   = 23 - 1
h4 = 15  = 24 - 1
h5 = 31  = 25 - 1
h6 = 63  = 26 - 1
h7 = 127 = 27 - 1
In general:
hn = 2n - 1, for all n >= 1

Busca binária

O algoritmo de busca binária é um método de busca de um único elemento em uma matriz classificada , cortando a matriz pela metade com cada passagem recursiva. O truque é escolher um ponto médio próximo ao centro da matriz, comparar os dados naquele ponto com os dados que estão sendo pesquisados ​​e, em seguida, responder a uma das três condições possíveis: os dados são encontrados no ponto médio, os dados no ponto médio são maiores do que os dados que estão sendo pesquisados, ou os dados no ponto médio são menores do que os dados que estão sendo pesquisados.

A recursão é usada neste algoritmo porque a cada passagem um novo array é criado cortando o antigo pela metade. O procedimento de pesquisa binária é então chamado recursivamente, desta vez no novo (e menor) array. Normalmente, o tamanho da matriz é ajustado pela manipulação de um índice inicial e final. O algoritmo exibe uma ordem logarítmica de crescimento porque essencialmente divide o domínio do problema pela metade com cada passagem.

Exemplo de implementação de pesquisa binária em C:

 /*
  Call binary_search with proper initial conditions.

  INPUT:
    data is an array of integers SORTED in ASCENDING order,
    toFind is the integer to search for,
    count is the total number of elements in the array

  OUTPUT:
    result of binary_search

 */
 int search(int *data, int toFind, int count)
 {
    //  Start = 0 (beginning index)
    //  End = count - 1 (top index)
    return binary_search(data, toFind, 0, count-1);
 }

 /*
   Binary Search Algorithm.

   INPUT:
        data is a array of integers SORTED in ASCENDING order,
        toFind is the integer to search for,
        start is the minimum array index,
        end is the maximum array index
   OUTPUT:
        position of the integer toFind within array data,
        -1 if not found
 */
 int binary_search(int *data, int toFind, int start, int end)
 {
    //Get the midpoint.
    int mid = start + (end - start)/2;   //Integer division


    if (start > end)                     //Stop condition (base case)
       return -1;
    else if (data[mid] == toFind)        //Found, return index
       return mid;
    else if (data[mid] > toFind)         //Data is greater than toFind, search lower half
       return binary_search(data, toFind, start, mid-1);
    else                                 //Data is less than toFind, search upper half
       return binary_search(data, toFind, mid+1, end);
 }

Estruturas de dados recursivas (recursão estrutural)

Uma aplicação importante da recursão na ciência da computação é a definição de estruturas de dados dinâmicas, como listas e árvores . Estruturas de dados recursivas podem crescer dinamicamente até um tamanho teoricamente infinito em resposta aos requisitos de tempo de execução; em contraste, o tamanho de um array estático deve ser definido em tempo de compilação.

"Algoritmos recursivos são particularmente apropriados quando o problema subjacente ou os dados a serem tratados são definidos em termos recursivos."

Os exemplos nesta seção ilustram o que é conhecido como "recursão estrutural". Este termo se refere ao fato de que os procedimentos recursivos estão agindo sobre dados que são definidos recursivamente.

Enquanto um programador deriva o modelo de uma definição de dados, as funções empregam recursão estrutural. Ou seja, as recursões no corpo de uma função consomem alguma parte imediata de um determinado valor composto.

Listas vinculadas

Abaixo está uma definição C de uma estrutura de nó de lista vinculada. Observe especialmente como o nó é definido em termos de si mesmo. O "próximo" elemento do de estrutura é um ponteiro para outro nó de estrutura , criando efetivamente um tipo de lista.

struct node
{
  int data;           // some integer data
  struct node *next;  // pointer to another struct node
};

Como a estrutura de dados do nó de estrutura é definida recursivamente, os procedimentos que operam nela podem ser implementados naturalmente como procedimentos recursivos. O procedimento list_print definido abaixo percorre a lista até que ela esteja vazia (ou seja, o ponteiro da lista tem um valor NULL). Para cada nó, ele imprime o elemento de dados (um inteiro). Na implementação C, a lista permanece inalterada pelo procedimento list_print .

void list_print(struct node *list)
{
    if (list != NULL)               // base case
    {
       printf ("%d ", list->data);  // print integer data followed by a space
       list_print (list->next);     // recursive call on the next node
    }
}

Árvores binárias

Abaixo está uma definição simples para um nó de árvore binária. Como o nó para listas vinculadas, ele é definido em termos de si mesmo, recursivamente. Existem dois ponteiros autorreferenciais: esquerdo (apontando para a subárvore esquerda) e direito (apontando para a subárvore direita).

struct node
{
  int data;            // some integer data
  struct node *left;   // pointer to the left subtree
  struct node *right;  // point to the right subtree
};

As operações na árvore podem ser implementadas usando recursão. Observe que, como há dois ponteiros de autorreferência (esquerdo e direito), as operações de árvore podem exigir duas chamadas recursivas:

// Test if tree_node contains i; return 1 if so, 0 if not.
int tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return 0;  // base case
    else if (tree_node->data == i)
        return 1;
    else
        return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i);
}

No máximo duas chamadas recursivas serão feitas para qualquer chamada para tree_contains conforme definido acima.

// Inorder traversal:
void tree_print(struct node *tree_node) {
    if (tree_node != NULL) {              // base case
        tree_print(tree_node->left);      // go left
        printf("%d ", tree_node->data);   // print the integer followed by a space
        tree_print(tree_node->right);     // go right
    }
}

O exemplo acima ilustra uma travessia em ordem da árvore binária. Uma árvore de pesquisa binária é um caso especial da árvore binária onde os elementos de dados de cada nó estão em ordem.

Travessia do sistema de arquivos

Como o número de arquivos em um sistema de arquivos pode variar, a recursão é a única maneira prática de percorrer e, assim, enumerar seu conteúdo. A travessia de um sistema de arquivos é muito semelhante à travessia de árvore , portanto, os conceitos por trás da travessia de árvore são aplicáveis ​​à travessia de um sistema de arquivos. Mais especificamente, o código a seguir seria um exemplo de passagem de pré - ordem de um sistema de arquivos.

import java.io.File;

public class FileSystem {

	public static void main(String [] args) {
		traverse();
	}

	/**
	 * Obtains the filesystem roots
	 * Proceeds with the recursive filesystem traversal
	 */
	private static void traverse() {
		File[] fs = File.listRoots();
		for (int i = 0; i < fs.length; i++) {
			System.out.println(fs[i]);
			if (fs[i].isDirectory() && fs[i].canRead()) {
				rtraverse(fs[i]);
			}
		}
	}

	/**
	 * Recursively traverse a given directory
	 *
	 * @param fd indicates the starting point of traversal
	 */
	private static void rtraverse(File fd) {
		File[] fss = fd.listFiles();

		for (int i = 0; i < fss.length; i++) {
			System.out.println(fss[i]);
			if (fss[i].isDirectory() && fss[i].canRead()) {
				rtraverse(fss[i]);
			}
		}
	}

}

Este código é recursivo e iterativo - os arquivos e diretórios são iterados e cada diretório é aberto recursivamente.

O método "rtraverse" é um exemplo de recursão direta, enquanto o método "traverse" é uma função de invólucro.

O cenário do "caso básico" é que sempre haverá um número fixo de arquivos e / ou diretórios em um determinado sistema de arquivos.

Eficiência de tempo de algoritmos recursivos

A eficiência de tempo de algoritmos recursiva pode ser expresso em uma relação de recorrência de Big O notação . Eles podem (geralmente) ser simplificados em um único termo Big-O.

Regra de atalho (teorema mestre)

Se a complexidade de tempo da função está na forma

Então o Grande O da complexidade do tempo é assim:

  • Se por alguma constante , então
  • Se então
  • Se para alguma constante , e se para alguma constante c <1 e todos n suficientemente grande , então

onde a representa o número de chamadas recursivas em cada nível de recursão, b representa por qual fator menor a entrada é para o próximo nível de recursão (ou seja, o número de peças em que você divide o problema) e f  ( n ) representa o trabalho a função é independente de qualquer recursão (por exemplo, particionamento, recombinação) em cada nível de recursão.

Veja também

Notas

Referências