Recursão
Um procedimento ou função pode conter uma chamada para outro procedimento dentro dele. Inclusive, a sub-rotina pode chamar a si mesma. Nesse caso, o computador não se importa. Ele também, como sempre, executa consistentemente os comandos que conhece de cima para baixo.
Se você se lembra da matemática, pode encontrar o princípio da indução matemática. É o seguinte:
alguma afirmação é verdadeira para todo natural n se
1. é válido para n = 1 e
2. da validade da afirmação para qualquer n = k natural arbitrário, segue-se que ela é verdadeira para n = k + 1.
Na programação, essa técnica é chamada de recursão.
Recursão é uma forma de definir um conjunto de objetos em termos do próprio conjunto, com base em dados casos base simples.
Recursivo é um procedimento (função) que chama a si mesmo diretamente ou por meio de outros procedimentos e funções.
Exemplo
def Rec(a):
se (a>0): Rec(a-1)
imprimir(a)
Esquematicamente, o trabalho de recursão pode ser representado por um fluxograma
O procedimento Rec() é executado com o parâmetro 3. Em seguida, dentro do procedimento com o parâmetro 3, é chamado o procedimento com o parâmetro 2, e assim sucessivamente, até que seja chamado o procedimento com o parâmetro 0. Quando o procedimento com o parâmetro 0 é chamado, a chamada recursiva não ocorrerá mais e o procedimento com parâmetro 0 imprimirá o número 0 e sairá. Em seguida, o controle é transferido de volta para o procedimento com o parâmetro 1, ele também termina seu trabalho imprimindo o número 1 e assim por diante. antes do procedimento com o parâmetro 3.
Todos os procedimentos chamados são armazenados na memória até que concluam seu trabalho. O número de procedimentos simultâneos é chamado de profundidade de recursão.
|
Recursão como substituição de loop
Vimos que a recursão é a execução repetida de instruções contidas em uma sub-rotina. E isso, por sua vez, é semelhante ao trabalho do ciclo. Existem linguagens de programação nas quais a construção do loop está totalmente ausente. Por exemplo, Prolog.
Vamos tentar simular o funcionamento do loop for.
O loop for contém uma variável de contador de passos. Em uma sub-rotina recursiva, tal variável pode ser passada como um parâmetro.
# Procedimento LoopImitation() com dois parâmetros
# Primeiro parâmetro – contador de passos, segundo parâmetro – número total de passos
def LoopImitation(i, n):
print("Hello N", i) # Instrução a ser repetida para qualquer valor de i
se eu < n: # Até que o contador de loop seja igual ao valor n,
LoopImitation(i + 1, n) # chama uma nova instância do procedimento,
# com o parâmetro i+1 (vá para o próximo valor i)
|
Recursão e iteração
Para entender a recursão, você precisa entender a recursão...
Iteração na programação - uma etapade um processo cíclico de processamento de dados.
Freqüentemente, algoritmos iterativos na etapa atual (iteração) usam o resultado da mesma operação ou ação calculada nas etapas anteriores. Um exemplo desses cálculos é o cálculo das relações de recorrência.
Um exemplo simples de valor recursivo é o fatorial: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
O cálculo do valor em cada etapa (iteração) é \(N=N \cdot i\) . Ao calcular o valor de \(N\), tomamos o valor já armazenado \(N\).< br />
O fatorial de um número também pode ser descrito usando a fórmula recorrente:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{casos} \end{equação*}\)
Você pode perceber que esta descrição nada mais é do que uma função recursiva.
Aqui, a primeira linha ( \(n <= 1\)) é o caso base (condição de término da recursão) e a segunda linha é a transição para a próxima etapa.
| Função fatorial recursiva |
Algoritmo iterativo |
|
def Fatorial(n):
se n > 1:
return n * fatorial(n - 1)
outro:
retornar 1
|
x=1
para i no intervalo (1, n + 1):
x = x * i;
|
Deve ser entendido que as chamadas de função envolvem alguma sobrecarga adicional, portanto, um cálculo fatorial não recursivo será um pouco mais rápido.
Conclusão: onde você pode escrever um programa com um algoritmo iterativo simples, sem recursão, então você precisa escrever sem recursão. Ainda assim, existe uma grande classe de problemas onde o processo computacional é implementado apenas por recursão.
Por outro lado, algoritmos recursivos costumam ser mais compreensíveis.
|
Tarefa
No alfabeto da língua da tribo «Tumba-Yumba» quatro letras: "K", "L", "M" e "N". É necessário exibir na tela todas as palavras compostas por n letras que podem ser construídas a partir das letras deste alfabeto
O problema é um problema normal de força bruta que pode ser reduzido a um problema menor.
Substituiremos sequencialmente as letras da palavra.
A primeira posição de uma palavra pode ser uma das 4 letras do alfabeto ( K, L, M, N).
Primeiro, coloque a letra ' K' primeiro. Então, para obter todas as variantes com a primeira letra ' K', você precisa enumerar todas as combinações possíveis de letras no n-1 posições e .etc. (Ver foto)
Assim, chegamos a uma solução recursiva: em um loop, percorra todas as primeiras letras possíveis (colocando cada letra do alfabeto na primeira posição) e para cada caso construa todas as "caudas" possíveis; comprimento n-1.
Interação recursiva de caracteres
Você precisa parar a recursão e produzir a palavra finalizada quando a parte restante estiver vazia (n = 0), ou seja, todas as letras já estão selecionadas.
O procedimento recursivo ficaria assim:
def TumbaWords(palavra, alfabeto, n):
se n < 1:
imprimir(palavra)
retornar
para c no alfabeto:
TumbaWords(palavra+c, alfabeto, n - 1)
|