Recursão (ciência da computação)

Da Wikipédia, a enciclopédia livre
Ir para navegação Pular para pesquisar

Á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.

Em 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. [1] 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. [2]

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 [3]

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 ) [4] 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 . [ citação necessária ]

Funções e algoritmos recursivos

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 cálculo 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 , [ como? ] 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)".

Tipo recursivo

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 indutivamente definidos

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 ):

Um número natural é 1 ou n + 1, onde n é um número natural.

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 >  :: =  < número > 
          | ( < 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 Coinductively definidos e corecursion

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:

Um fluxo de strings é um objeto tal que:
 cabeça (s) é uma corda, e
 cauda (s) é um fluxo de cordas.

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 pode, às vezes, 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.

Anonymous recursão

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 .

Estrutural contra recursão 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 [5]

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, Advanced Functional Programming , 2002 [6]

Essa 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. 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.

Wrapper função

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 no caso base

Fatorial: comum vs. curto-circuito
Recursão ordinária Recursão de curto-circuito
int  fac1 ( int  n )  { 
   if  ( n  <=  0 ) 
      retornar  1 ; 
   caso contrário, 
      retorne  fac1 ( n -1 ) * n ; 
}
estático  int  fac2 ( int  n )  { 
   // assert (n> = 2); 
   se  ( n  ==  2 ) 
      retornar  2 ; 
   caso contrário, 
      retorne  fac2 ( n -1 ) * n ; 
} 
int  fac2wrapper ( int  n )  { 
   if  ( n  <=  1 ) 
      return  1 ; 
   senão 
      retorna  fac2 ( n ); 
}

O curto-circuito do caso base, também conhecido como recursão de comprimento de braço , consiste em verificar o caso base antesfazer 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. [7]

Busca 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 ;   // caso base 
    else  if  ( tree_node -> data  ==  i ) 
        return  true ; 
    senão 
        retornar  tree_contains ( tree_node -> left ,  i )  || 
               tree_contains ( tree_node -> direito,  i ); 
}

O algoritmo em curto-circuito pode ser implementado como:

// Função de wrapper para lidar com árvore vazia 
bool  tree_contains ( struct  node  * tree_node ,  int  i )  { 
    if  ( tree_node  ==  NULL ) 
        return  false ;   // árvore vazia 
    senão 
        return  tree_contains_do ( tree_node ,  i );   // chama a função auxiliar 
}

// Assume tree_node! = NULL 
bool  tree_contains_do ( struct  node  * tree_node ,  int  i )  { 
    if  ( tree_node -> data  ==  i ) 
        return  true ;   // encontrou 
    outro   // recurse 
        return  ( tree_node -> left   &&  tree_contains_do ( tree_node -> left ,   i ))  || 
               ( tree_node -> right  &&  tree_contains_do( tree_node -> direito ,  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 . 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 contra 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 :

função recursiva (n)
    se n == base
        retornar x base
    outro
        retornar f (n, recursivo (n-1))
função iterativa (n)
    x = x base
    para i = base + 1 para n
        x = f (i, x)
    retornar 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:

 fatorial não assinado int  ( não assinado int n ) { produto int não assinado = 1 ; // produto vazio é 1 while ( n ) { product * = n ; - n ; } devolver produto ; }   
       
    
      
    
  
   

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. [8] [9]

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 . [10] [11] No entanto, na prática, essa reescrita depende da eliminação da chamada de cauda , que não é uma característica de todos os idiomas. C , Java e Python são linguagens dominantes notáveis ​​em que todas as chamadas de função, incluindo chamadas finais, pode causar a 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.

Espaço da pilha

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. [12] 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 . [13] Alguns malwares visam especificamente a pilha de chamadas de um programa e se beneficiam da natureza inerentemente recursiva da pilha. [14] 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ção pode não impedir que o processo correspondente seja encerrado . [15]

Problemas Multiply recursiva

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 sejam usados ​​métodos recursivos e iterativos, [16] 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.

Refatoração recursão

Algoritmos recursivos podem ser substituídos por contrapartes não recursivas. [17] Um método para substituir algoritmos recursivos é simulá-los usando a memória heap no lugar da memória stack . [18] Uma alternativa é desenvolver um algoritmo de substituição inteiramente baseado em métodos não recursivos, o que pode ser desafiador. [19] Por exemplo, algoritmos recursivos para correspondência de curingas , como o algoritmo wildmat de Rich Salz , [20] já foram típicos. Algoritmos não recursivos para a mesma finalidade, como o algoritmo de correspondência de curingas de Krauss , foram desenvolvidos para evitar as desvantagens da recursão[21] e melhoraram apenas gradualmente com base em técnicas como a coleta de testes e odesempenho de perfis . [22]

Funções cauda-recursivo

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 finais como saltosem 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: Inteiros x, y tais que x> = y e y> = 0 
int  gcd ( int  x ,  int  y ) 
{ 
  if  ( y  ==  0 ) 
     return  x ; 
  caso contrário, 
     retorne  gcd ( y ,  x  %  y ); 
}
// INPUT: n é um inteiro tal que n> = 0 
int  fact ( int  n ) 
{ 
   if  ( n  ==  0 ) 
      return  1 ; 
   senão, 
      retorna  n  *  fato ( 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 recursiva

Fatorial

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

Pseudocódigo (recursivo):
o fatorial da função é: 
entrada : inteiro n tal que n > = 0
saída : [ n × ( n -1) × ( n -2) ×… × 1]
1. se n for 0, retorne 1 2. caso contrário, retorna [ n × fatorial ( n -1)]
final fatorial

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:
b 4            = 4 × b 3 
             = 4 × (3 × b 2 )
             = 4 × (3 × (2 × b 1 ))
             = 4 × (3 × (2 × (1 × b 0 )))
             = 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):
função fatorial é: 
entrada : número inteiro n tal que n > = 0
de saída : [ N x ( n -1) x ( n -2) ... x × 1]
1. criar nova variável chamada running_total com um valor de 1
2. começar ciclo 1. se n for 0, saia do loop 2. definir running_total para ( running_total × n ) 3. decrementar n 4. repetir o loop
3. retornar running_total
final fatorial

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):
função gcd é:
 entrada : inteiro x , inteiro y tal que x > 0 ey > = 0
 
1. se y for 0, retorne x 2. caso contrário, retorne [gcd ( y , (resto de x / y ))]
fim gcd

Relação de recorrência para o maior divisor comum, ondeexpressa o resto de:

E se
Calculando a relação de recorrência para x = 27 ey = 9:
mdc (27, 9) = mdc (9, 27% 9)
             = mdc (9, 0)
             = 9
Calculando a relação de recorrência para x = 111 ey = 259:
mdc (111, 259) = mdc (259, 111% 259)
                = mdc (259, 111)
                = mdc (111, 259% 111)
                = mdc (111, 37)
                = mdc (37, 111% 37)
                = mdc (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):
função gcd é: 
entrada : inteiro x , inteiro y tal que x > = y e y > = 0
1. crie uma nova variável chamada resto
2. comece o loop 1. se y for zero, saia do loop 2. definir o resto para o resto de x / y 3. defina x para y 4. definir y para o resto 5. repetir o loop
3. retornar x
terminar 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. [23] [24] Existem três pinos que podem conter pilhas de discos de diâmetros diferentes. 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):
função hanoi é: 
entrada : inteiro n , de modo que n > = 1
1. se n for 1, então retorne 1
2. retornar [2 * [ chamar hanoi (n-1)] + 1]
fim 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. [25]

Uma fórmula explícita para Torres de Hanói:
h 1 = 1 = 2 1 - 1
h 2 = 3 = 2 2 - 1
h 3 = 7 = 2 3 - 1
h 4 = 15 = 2 4 - 1
h 5 = 31 = 2 5 - 1
h 6 = 63 = 2 6 - 1
h 7 = 127 = 2 7 - 1
Em geral:
h n = 2 n - 1, para todo n> = 1

Pesquisa 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:

 / * 
  Chame binary_search com as condições iniciais adequadas.

  INPUT: 
    data é uma matriz de inteiros SORTED em ordem ASCENDING, 
    toFind é o inteiro a ser pesquisado, 
    count é o número total de elementos na matriz

  OUTPUT: 
    resultado de binary_search

* / 
 int  search ( int  * data ,  int  toFind ,  int  count ) 
 { 
    // Start = 0 (índice inicial) 
    // End = count - 1 (índice superior) 
    return  binary_search ( data ,  toFind ,  0 ,  count -1 ); 
 }

 / * 
   Algoritmo de pesquisa binária.

   INPUT: os 
        dados são um array de inteiros SORTED em ordem ASCENDING, 
        toFind é o inteiro a ser pesquisado, 
        start é o índice mínimo do array, 
        end é o índice máximo do array 
   OUTPUT: 
        posição do inteiro toFind dentro dos dados do array, 
        -1 se não encontrado 
* / 
 int  binary_search ( int  * data ,  int  toFind ,  int  start ,  int  end ) 
 { 
    // Obtenha o ponto médio. 
    int  mid  =  start  +  ( end  -  start) / 2 ;    // Divisão inteira


    if  ( start  >  end )                      // Condição de parada (caso base) 
       return  -1 ; 
    else  if  ( data [ mid ]  ==  toFind )         // Encontrado, índice de 
       retorno return  mid ; 
    else  if  ( data [ mid ]  >  toFind )          // Os dados são maiores que toFind, pesquisa metade inferior 
       retorna  binary_search ( data ,  toFind ,  start ,  mid -1 ); 
    outro                                 // Os dados são menores que toFind, a metade superior da pesquisa 
       retorna  binary_search ( data ,  toFind ,  mid + 1 ,  end ); 
 }

Estruturas de dados recursivos (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." [26]

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. [6]

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.

 nó da 
estrutura { 
  dados internos  ; // algum nó de estrutura de dados inteiros * next ; // ponteiro para outro nó de estrutura };           
      

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 )                // caso base 
    { 
       printf  ( "% d" ,  lista -> dados );   // imprime dados inteiros seguidos por um espaço 
       list_print  ( list -> next );      // chamada recursiva no próximo nó 
    } 
}

Á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).

 nó da 
estrutura { 
  dados internos  ; // algum nó de estrutura de dados inteiros * left ; // ponteiro para o nó de struct da subárvore esquerda * right ; // aponta para a subárvore direita };            
       
      

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:

// Testa se tree_node contém i; retorne 1 em caso afirmativo, 0 se não. 
int  tree_contains ( nó de estrutura  * tree_node , int i ) { if ( tree_node == NULL ) return 0 ; // caso base else if ( tree_node -> data == i ) return 1 ; senão retornar tree_contains ( tree_node -> left , i ) || tree_contains (    
       
           
        
         
    
            tree_node -> direito ,  i ); 
}

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

// Percurso na ordem: 
void  tree_print ( struct  node  * tree_node )  { 
    if  ( tree_node  ! =  NULL )  {               // caso base 
        tree_print ( tree_node -> left );       // vá para a esquerda 
        printf ( "% d" ,  tree_node -> dados );    // imprime o inteiro seguido por um espaço 
        tree_print ( tree_node -> right );      // vá para a direita 
    } 
}

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 em que os elementos de dados de cada nó estão em ordem.

Sistema de arquivos travessia

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 uma passagem de pré - encomenda de um sistema de arquivos.

import  java.io.File ;

public  class  FileSystem  {

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

	/ **
	 * Obtém as raízes do sistema de arquivos
	 * Prossegue com a travessia recursiva do sistema de arquivos
	 * /
	private  static  void  traverse ()  {
		Arquivo []  fs  =  Arquivo . listRoots ();
		para  ( int  i  =  0 ;  i  <  fs . comprimento ;  i ++ )  {
			Sistema . para fora . println ( fs [ i ] );
			if  ( fs [ i ] . isDirectory ()  &&  fs [ i ] . canRead ())  {
				rtraverse ( fs [ i ] );
			}
		}
	}

	/ **
	 * Percorre recursivamente um determinado diretório
	 *
	 * @param fd indica o ponto de partida da travessia
	 * /
	private  static  void  rtraverse ( Arquivo  fd )  {
		Arquivo []  fss  =  fd . listFiles ();

		para  ( int  i  =  0 ;  i  <  fss . comprimento ;  i ++ )  {
			Sistema . para fora . 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.

Time-eficiência dos 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 master)

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 por 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

  1. ^ Graham, Ronald; Knuth, Donald; Patashnik, Oren (1990). "1: Problemas recorrentes" . Matemática Concreta . ISBN 0-201-55802-5.
  2. ^ Epp, Susanna (1995). Discrete Mathematics with Applications (2ª ed.). p. 427 . ISBN 978-0-53494446-9.
  3. ^ Wirth, Niklaus (1976). Algoritmos + Estruturas de Dados = Programas . Prentice-Hall . p. 126 . ISBN 978-0-13022418-7.
  4. ^ "Programação Funcional | Clojure for the Brave and True" . www.braveclojure.com . Recuperado em 2020-10-21 .
  5. ^ Felleisen e outros. 2001 , art V "Generative Recursion
  6. ^ a b Felleisen, Matthias (2002). "Desenvolvendo Programas Interativos da Web" . Em Jeuring, Johan (ed.). Programação Funcional Avançada: 4ª Escola Internacional (PDF) . Springer. p. 108. ISBN  9783540448334.
  7. ^ Mongan, John; Giguère, Eric; Kindler, Noah (2013). Entrevistas de programação expostas: segredos para conseguir seu próximo trabalho (3ª ed.). Wiley . p. 115 . ISBN 978-1-118-26136-1.
  8. ^ Hetland, Magnus Lie (2010), Python Algorithms: Mastering Basic Algorithms in the Python Language , Apress, p. 79, ISBN 9781430232384.
  9. ^ Drozdek, Adam (2012), Estruturas de dados e algoritmos em C ++ (4o ed.), Cengage Learning, p. 197, ISBN 9781285415017.
  10. ^ Arrepios, Olin. "The Anatomy of a Loop - Uma história de escopo e controle" (PDF) . Instituto de Tecnologia da Geórgia . Página visitada em 03-09-2012 .
  11. ^ Lambda, o máximo. "A anatomia de um loop" . Lambda the Ultimate . Página visitada em 03-09-2012 .
  12. ^ "27.1. Sys - Parâmetros e funções específicos do sistema - Documentação do Python v2.7.3" . Docs.python.org . Página visitada em 03-09-2012 .
  13. ^ Krauss, Kirk J. (2014). "Correspondência de curingas: uma maneira empírica de domar um algoritmo" . Diário do Dr. Dobb .
  14. ^ Mueller, Oliver (2012). "Anatomia de um ataque destruidor de pilha e como o GCC o evita" . Diário do Dr. Dobb .
  15. ^ "StackOverflowException Class" . Biblioteca de classes do .NET Framework . Microsoft Developer Network . 2018.
  16. ^ "Pesquisa em profundidade (DFS): Implementação iterativa e recursiva" . Techie Delight. 2018.
  17. ^ Mitrovic, Ivan. "Substituir Recursão por Iteração" . ThoughtWorks .
  18. ^ La, Woong Gyu (2015). "Como substituir funções recursivas usando pilha e loop while para evitar o estouro de pilha" . CodeProject.
  19. ^ Moertel, Tom (2013). "Truques do comércio: Recursão para iteração, Parte 2: Eliminando a recursão com o truque do recurso secreto de viagem no tempo" .
  20. ^ Salz, Rich (1991). "wildmat.c" . GitHub .
  21. ^ Krauss, Kirk J. (2008). "Matching Wildcards: An Algorithm" . Diário do Dr. Dobb .
  22. ^ Krauss, Kirk J. (2018). "Matching Wildcards: An Improved Algorithm for Big Data" . Desenvolva para desempenho.
  23. ^ Graham, Knuth & Patashnik 1990 , §1.1: A Torre de Hanói
  24. ^ Epp 1995 , pp. 427-430: A Torre de Hanói
  25. ^ Epp 1995 , pp. 447-448: Uma fórmula explícita para a sequência da Torre de Hanói
  26. ^ Wirth 1976 , p. 127

Referências