Compreensão moderna de recursão: definição de funcionalidade e acesso a ela de fora e desta funcionalidade. Acredita-se que a recursão nasceu pelos matemáticos: cálculo fatorial, séries infinitas, fractais, frações contínuas… No entanto, a recursão pode ser encontrada em todos os lugares. As leis naturais objetivas “consideram” a recursão como seu principal algoritmo e forma de expressão (existência) não tanto dos objetos do mundo material, mas em geral o principal algoritmo de movimento.
Pessoas de diversas especialidades em diversos campos da ciência e tecnologia utilizam o algoritmo recursivo f (x), onde "x ~/=f (x)". Uma função que chama a si mesma é uma solução forte, mas formar e entender essa solução é, na maioria dos casos, uma tarefa muito difícil.
Nos tempos antigos, a recursão era usada para aumentar o espaço do palácio. Através de um sistema de espelhos direcionados um para o outro, você pode criar efeitos espaciais tridimensionais impressionantes. Mas é tão fácil entender comoajustar esses espelhos? É ainda mais difícil determinar onde está um ponto no espaço, refletido através de vários espelhos.
Recursão, algoritmos recursivos: significado e sintaxe
O problema, que é formulado pela repetição de uma sequência de operações, pode ser resolvido recursivamente. Um algoritmo simples (computar uma equação quadrática, um script para preencher uma página web com informações, ler um arquivo, enviar uma mensagem…) não requer recursão.
Principais diferenças do algoritmo que permite uma solução recursiva:
- há um algoritmo que precisa ser executado várias vezes;
- algoritmo precisa de dados que mudam toda vez;
- o algoritmo não precisa mudar toda vez;
- há uma condição final: o algoritmo é recursivo - não infinito.
Em geral, não se pode argumentar que a execução única é uma condição necessária para a ausência de uma razão para a recursão. Você também não pode exigir uma condição final obrigatória: recursões infinitas têm seu próprio escopo.
O algoritmo é recursivo: quando uma sequência de operações é executada repetidamente, em dados que mudam a cada vez e dão um novo resultado a cada vez.
Fórmula de recursão
A compreensão matemática da recursão e seu análogo na programação são diferentes. Matemática, embora haja sinais de programação, mas programação é matemática de uma ordem muito superior.
Um algoritmo bem escrito é como um espelho do intelecto de seu autor. Em gerala fórmula de recursão na programação é "f(x)", onde "x ~/=f(x)" tem pelo menos duas interpretações. Aqui "~" é a semelhança ou ausência do resultado, e "=" é a presença do resultado da função.
Primeira opção: dinâmica de dados.
- função "f(x)" tem um algoritmo recursivo e imutável;
- "x" e o resultado "f(x)" têm novos valores a cada vez, o resultado "f(x)" é o novo parâmetro "x" desta função.
Segunda opção: dinâmica de código.
- função "f(x)" tem vários algoritmos que refinam (analisam) os dados;
- análise de dados - uma parte do código e a implementação de algoritmos recursivos que realizam a ação desejada - a segunda parte do código;
- o resultado da função "f(x)" não é.
Nenhum resultado é normal. Programação não é matemática, aqui o resultado não precisa estar explicitamente presente. Uma função recursiva pode simplesmente analisar sites e preencher o banco de dados ou instanciar objetos de acordo com a entrada recebida.
Dados e recursão
Programar algoritmos recursivos não se trata de calcular um fatorial, em que a função recebe cada vez um determinado valor que é um a mais ou a menos um - a opção de implementação depende da preferência do desenvolvedor.
Não importa como o fatorial "8!",algoritmo que segue estritamente esta fórmula.
O processamento de informações é uma "matemática" de uma ordem completamente diferente. Funções e algoritmos recursivos aqui operam em letras, palavras, frases, sentenças e parágrafos. Cada próximo nível usa o anterior.
O fluxo de dados de entrada é analisado em uma ampla gama de condições, mas o processo de análise é geralmente recursivo. Não faz sentido escrever algoritmos exclusivos para todas as variantes do fluxo de entrada. Deve haver uma funcionalidade. Aqui, algoritmos recursivos são exemplos de como formar um fluxo de saída adequado à entrada. Esta não é a saída do algoritmo recursivo, mas é a solução desejada e necessária.
Abstração, recursão e POO
Programação orientada a objetos (OOP) e recursão são entidades fundamentalmente diferentes, mas se complementam perfeitamente. Abstração não tem nada a ver com recursão, mas através das lentes da OOP ela cria a possibilidade de implementar recursão contextual.
Por exemplo, as informações estão sendo analisadas e letras, palavras, frases, sentenças e parágrafos são destacados separadamente. Obviamente, o desenvolvedor providenciará a criação de instâncias de objetos desses cinco tipos e oferecerá uma solução de algoritmos recursivos em cada nível.
Enquanto isso, se ao nível das letras “não adianta procurar sentido”, então a semântica aparece ao nível das palavras. Você pode dividir as palavras em verbos, substantivos, advérbios, preposições… Você pode ir além e definir casos.
No nível da frase, a semântica é complementada por sinais de pontuação e lógicacombinações de palavras. Ao nível das frases, encontra-se um nível semântico mais perfeito, e um parágrafo pode ser considerado como um pensamento completo.
O desenvolvimento orientado a objetos predetermina a herança de propriedades e métodos e propõe iniciar a hierarquia de objetos com a criação de um ancestral completamente abstrato. Ao mesmo tempo, sem dúvida, a análise de cada descendente será recursiva e não diferirá muito no nível técnico em muitas posições (letras, palavras, frases e sentenças). Parágrafos, como pensamentos completos, podem se destacar desta lista, mas não são a essência.
É importante que a maior parte do algoritmo possa ser formulada no nível do ancestral abstrato, refinando-o no nível de cada descendente com dados e métodos chamados do nível abstrato. Nesse contexto, a abstração abre novos horizontes para a recursão.
Recursos históricos da POO
OOP chegou ao mundo do software duas vezes, embora alguns especialistas possam destacar o surgimento da computação em nuvem e ideias modernas sobre objetos e classes como uma nova rodada no desenvolvimento de tecnologias de TI.
Os termos "objeto" e "objetivo" no contexto moderno da POO são geralmente atribuídos aos anos 50 e 60 do século passado, mas estão associados a 1965 e ao surgimento de Simula, Lisp, Algol, Smalltalk.
Naquela época, a programação não era particularmente desenvolvida e não conseguia responder adequadamente a conceitos revolucionários. A luta de ideias e estilos de programação (C/C++ e Pascal - principalmente) ainda estava longe, e os bancos de dados ainda estavam formados conceitualmente.
No final dos anos 80 e início dos anos 90, os objetos apareciam em Pascal e todos se lembravam de classes em C/C++ - isso marcou uma nova rodada de interesse em POO e foi então que ferramentas, principalmente linguagens de programação, deixaram de ser suporta apenas ideias orientadas a objetos, mas evolui de acordo.
Claro, se os algoritmos recursivos anteriores fossem apenas funções usadas no código geral do programa, agora a recursão poderia se tornar parte das propriedades de um objeto (classe), o que oferecia oportunidades interessantes no contexto de herança.
Recurso da OOP moderna
O desenvolvimento da OOP inicialmente declarou objetos (classes) como coleções de dados e propriedades (métodos). Na verdade, tratava-se de dados que têm sintaxe e significado. Mas então não foi possível apresentar a POO como uma ferramenta para gerenciar objetos reais.
OOP tornou-se uma ferramenta para gerenciar objetos de "natureza computacional". Um script, um botão, um item de menu, uma barra de menu, uma tag em uma janela do navegador é um objeto. Mas não uma máquina, um produto alimentício, uma palavra ou uma frase. Objetos reais permaneceram fora da programação orientada a objetos, e ferramentas de computador assumiram uma nova encarnação.
Devido às diferenças nas linguagens de programação populares, muitos dialetos de OOP surgiram. Em termos de semântica, são praticamente equivalentes, e seu foco na esfera instrumental, e não na aplicada, permite levar a descrição de objetos reais alémalgoritmos e garantir sua "existência" entre plataformas e linguagens.
Pilhas e mecanismos de chamada de função
Mecanismos para chamar funções (procedimentos, algoritmos) requerem passar dados (parâmetros), retornar um resultado e lembrar o endereço do operador que deve receber o controle após a conclusão da função (procedimento).
Normalmente, a pilha é usada para esse fim, embora as linguagens de programação ou o próprio desenvolvedor possam fornecer uma variedade de opções para transferência de controle. A programação moderna admite que o nome de uma função não pode ser apenas um parâmetro: ele pode ser formado durante a execução do algoritmo. Um algoritmo também pode ser criado durante a execução de outro algoritmo.
O conceito de algoritmos recursivos, quando seus nomes e corpos podem ser determinados no momento da formação da tarefa (escolhendo o algoritmo desejado), estende a recursividade não apenas para como fazer algo, mas também quem exatamente deve fazer faça isso. Escolher um algoritmo pelo nome "significativo" é promissor, mas cria dificuldades.
Recursividade em um conjunto de funções
Você não pode dizer que um algoritmo é recursivo quando ele chama a si mesmo e pronto. A programação não é um dogma, e o conceito de recursividade não é um requisito exclusivo para chamar a si mesmo a partir do corpo do seu próprio algoritmo.
Aplicativos práticos nem sempre fornecem uma solução limpa. Muitas vezes, os dados iniciais devem ser preparados e o resultado da chamada recursiva deve ser analisado no contexto de todo o problema (todo o algoritmo) emgeral.
Na verdade, não apenas antes de uma função recursiva ser chamada, mas também após ela ser concluída, outro programa pode ou deve ser chamado. Se não houver problemas especiais com a chamada: a função recursiva A() chama a função B(), que faz algo e chama A(), imediatamente há um problema com o retorno do controle. Tendo completado a chamada recursiva, a função A() deve receber o controle para chamar novamente B(), que a chamará novamente. Retornar o controle como deveria estar na pilha de volta para B() é a solução errada.
O programador não está limitado na escolha de parâmetros e pode completá-los com nomes de funções. Em outras palavras, a solução ideal é passar o nome de B() para A() e deixar o próprio A() chamar B(). Nesse caso, não haverá problemas com o retorno do controle, e a implementação do algoritmo recursivo será mais transparente.
Compreensão e nível de recursão
O problema com o desenvolvimento de algoritmos recursivos é que você precisa entender a dinâmica do processo. Ao usar a recursão em métodos de objeto, especialmente no nível de um ancestral abstrato, há um problema de entender seu próprio algoritmo no contexto de seu tempo de execução.
Atualmente, não há restrições sobre o nível de aninhamento de funções e capacidade de pilha em mecanismos de chamada, mas há um problema de compreensão: em que momento qual nível de dados ou qual lugar no algoritmo geral chamado de recursivo função e em que número de chamadas ela mesma é.
As ferramentas de depuração existentes geralmente são impotentesdiga ao programador a solução certa.
Loops e recursão
Considera-se que a execução cíclica é equivalente à recursão. De fato, em alguns casos, o algoritmo recursivo pode ser implementado na sintaxe de construções condicionais e cíclicas.
No entanto, se houver um entendimento claro de que uma função específica deve ser implementada por meio de um algoritmo recursivo, qualquer uso externo de um loop ou de instruções condicionais deve ser abandonado.
O significado aqui é que uma solução recursiva na forma de uma função usando a si mesma será um algoritmo completo e funcionalmente completo. Este algoritmo exigirá que o programador o crie com esforço, entendendo a dinâmica do algoritmo, mas será a solução final que não requer controle externo.
Qualquer combinação de operadores condicionais externos e cíclicos não nos permitirá representar o algoritmo recursivo como uma função completa.
Consenso de Recursão e OOP
Em quase todas as variantes de desenvolvimento de um algoritmo recursivo, surge um plano para desenvolver dois algoritmos. O primeiro algoritmo gera uma lista de objetos futuros (instâncias), e o segundo algoritmo é na verdade uma função recursiva.
A melhor solução seria organizar a recursão como uma única propriedade (método) que realmente contém o algoritmo recursivo e colocar todo o trabalho preparatório no construtor do objeto.
Um algoritmo recursivo só será a solução certa quando funcionarapenas por ele mesmo, sem controle e gerenciamento externo. Um algoritmo externo só pode dar um sinal para funcionar. O resultado deste trabalho deve ser a solução esperada, sem suporte externo.
Recursão deve sempre ser uma solução completa e independente.
Compreensão intuitiva e integridade funcional
Quando a programação orientada a objetos se tornou o padrão de fato, ficou óbvio que para codificar de forma eficaz, você precisa mudar seu próprio pensamento. O programador deve passar da sintaxe e semântica da linguagem para a dinâmica da semântica durante a execução do algoritmo.
Característica da recursão: pode ser aplicada a tudo:
- web scraping;
- operações de pesquisa;
- analisando informações de texto;
- leitura ou criação de documentos do MS Word;
- amostragem ou análise de tags…
Característica da POO: permite descrever um algoritmo recursivo no nível de um ancestral abstrato, mas permite que ele se refira a descendentes únicos, cada um com sua própria paleta de dados e propriedades.
Recursão é ideal porque requer a completude funcional de seu algoritmo. OOP melhora o desempenho de um algoritmo recursivo, dando-lhe acesso a todos os filhos únicos.
