recursion c
Explore tudo sobre recursão em C ++ com exemplos clássicos.
Em nosso tutorial anterior, aprendemos mais sobre funções em C ++.
Além de usar as funções para quebrar o código em subunidades e torná-lo mais simples e legível, as funções são úteis em várias outras aplicações, incluindo resolução de problemas em tempo real, computação matemática e estatística.
o gateway padrão não está disponível no Windows 10
Conforme desenvolvemos aplicativos mais complexos em C ++, encontramos muitos requisitos, de modo que precisamos colocar vários conceitos especiais de C ++ em uso. A recursão é um desses conceitos.
=> Visite aqui para obter a lista completa de tutoriais em C ++.
Neste tutorial, aprenderemos mais sobre recursão, onde e por que ela é usada junto com alguns exemplos clássicos de C ++ que implementam recursão.
O que você aprenderá:
- O que é recursão?
- Condição de base de recursão
- Alocação de memória para a chamada recursiva
- Stack Overflow em recursão
- Recursão direta versus indireta
- Recursão com cauda e sem cauda
- Prós / contras da recursão em relação à programação iterativa
- Exemplos de recursão
- Conclusão
- Leitura recomendada
O que é recursão?
Recursão é um processo no qual uma função chama a si mesma. A função que implementa recursão ou chama a si mesma é chamada de função Recursiva. Na recursão, a função recursiva chama a si mesma indefinidamente e continua até que uma condição final seja satisfeita.
A imagem abaixo mostra como funciona a recursão:
Como vemos no diagrama acima, a função principal chama uma função, funct (). A função funct (), por sua vez, chama a si mesma dentro de sua definição. É assim que funciona a recursão. Este processo de chamada de função continuará até que forneçamos uma condição de término que fará com que ele termine.
Normalmente, fornecemos a ramificação do código ao implementar a recursão, de forma que fornecemos uma condição que irá acionar a recursão e outra para realizar a execução normal.
Condição de base de recursão
Quando a recursão é realizada, a solução para o caso base ou o caso final é fornecida e as soluções para problemas maiores são construídas com base nas soluções para problemas menores.
Vamos considerar um exemplo clássico de recursão, a notação fatorial.
Sabemos que matematicamente o fatorial de um número n é:
n! = nxn-1x… .x0!
dado que 0! = 1;
Portanto, o fatorial para n = 3 será 3! = 3 × 2!
3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6
Portanto, podemos expressar esse cálculo de maneira programática da seguinte maneira:
int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }Assim, como mostrado acima, expressamos o cálculo acima de um fatorial em uma chamada de função recursiva. Vemos que se o número n for menor ou igual a 1, retornamos 1 em vez de uma chamada recursiva. Isso é chamado de condição / caso base para o fatorial que permite interromper a recursão.
Portanto, a condição básica basicamente decide quantas vezes uma função recursiva deve chamar a si mesma. Isso significa que podemos muito bem calcular o fatorial de um número maior expressando-o em termos de números menores até que a classe base seja alcançada.
A seguir está um exemplo perfeito para calcular o fatorial de um número:
#include #include using namespace std; int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); } int main() { int num,result; cout<>num; result = factorial(num); cout< Resultado:
Insira o número cujo fatorial deve ser calculado: 10
10! = 3628800
No exemplo acima, implementamos recursão. Pegamos o número cujo fatorial deve ser encontrado na entrada padrão e o passamos para a função fatorial.
Na função fatorial, demos a condição de base como (n<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.
Alocação de memória para a chamada recursiva
Sabemos que quando uma chamada de função é feita, o estado da função de chamada é armazenado na pilha e quando uma chamada de função é concluída, esse estado é restaurado de volta para que o programa possa continuar a execução.
Quando uma chamada de função recursiva é feita, o estado ou a memória para a função chamada é alocado no topo do estado da função de chamada e uma cópia diferente das variáveis locais é feita para cada chamada de função recursiva.
Quando a condição básica é alcançada, a função retorna à função de chamada e a memória é desalocada e o processo continua.
Stack Overflow em recursão
Quando a recursão continua por um período de tempo ilimitado, pode resultar em um estouro de pilha.
Quando a recursão pode continuar assim? Uma situação é quando não especificamos a condição básica. Outra situação é quando a condição básica não é atingida durante a execução de um programa.
Por exemplo,modificamos o programa fatorial acima e mudamos sua condição de base.
int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }No código acima, mudamos a condição de base para (n == 1000). Agora, se dermos o número n = 10, podemos concluir que a condição de base nunca chegará. Dessa forma, em algum ponto, a memória na pilha se esgotará, resultando em um estouro da pilha.
Portanto, ao projetar programas recursivos, precisamos ter cuidado com a condição básica que fornecemos.
Recursão direta versus indireta
Até agora, na recursão, vimos a função chamando a si mesma. Esta é a recursão direta.
Existe outro tipo de recursão, ou seja, recursão indireta. Nesse caso, uma função chama outra função e, em seguida, essa função chama a função de chamada. Se f1 e f2 são duas funções. Então, f1 chama f2 e f2, por sua vez, chama f1. Esta é uma recursão indireta.
eu Vamos revisar nosso programa fatorial para demonstrar a recursão direta.
#include #include using namespace std; int factorial_b(int); int factorial_a(int n){ if(n <=1) return 1; else return n*factorial_b(n-1); } int factorial_b(int n){ if(n <=1) return 1; else return n*factorial_a(n-1); } int main() { int num, result; cout<>num; result = factorial_a(num); cout< Resultado:
Insira o número cujo fatorial deve ser calculado: 5
5! = 120
onde assistir anime de graça
No exemplo acima, mostramos a recursão indireta. A função principal chama factorial_a. Factorial_a chama factorial_b. Por sua vez, factorial_b chama factorial_a. Vemos que a saída do programa não é afetada.
Recursão com cauda e sem cauda
Uma função recursiva com cauda é uma função recursiva em que a última chamada é executada na função.
Por exemplo, considere a seguinte função.
void display(int n){ if(n<=1) return; cout<<” ”<No exemplo acima, a exibição é uma função recursiva com cauda, de modo que é a última chamada de função.
As funções tailed são consideradas melhores do que as funções recursivas não tailed, pois podem ser otimizadas pelo compilador. O motivo é que, como a chamada recursiva com cauda é a última instrução da função, não há código a ser executado após essa chamada.
Como resultado, não é necessário salvar o quadro de pilha atual para a função.
Prós / contras da recursão em relação à programação iterativa
Os programas recursivos fornecem código compacto e limpo. Um programa recursivo é uma maneira simples de escrever programas. Existem alguns problemas inerentes como fatorial, sequência de Fibonacci, torres de Hanoi, travessias de árvores, etc. que requerem recursão para serem resolvidos.
Em outras palavras, eles são resolvidos de forma eficiente com recursão. Eles também podem ser resolvidos com a programação iterativa usando pilhas ou outras estruturas de dados, mas há chances de se tornarem mais complexos para implementar.
Os poderes de resolução de problemas de programação recursiva e iterativa são os mesmos. No entanto, os programas recursivos ocupam mais espaço de memória, pois todas as chamadas de função precisam ser armazenadas na pilha até que o caso base seja correspondido.
As funções recursivas também têm uma sobrecarga de tempo por causa de muitas chamadas de função e valores de retorno.
Exemplos de recursão
A seguir, implementaremos alguns dos exemplos de programação recursiva.
Série Fibonacci
A série de Fibonacci é a sequência que é dada como
0 1 1 2 3 5 8 13 ……
Conforme mostrado acima, os primeiros dois números da série de Fibonacci são 0 e 1. O próximo número na sequência é a soma dos dois números anteriores.
Vamos implementar esta série usando recursão.
#include using namespace std; void fibSeries(int n){ static int n1=0, n2=1, n3; if(n>0){ n3 = n1 + n2; n1 = n2; n2 = n3; cout<num; cout<<'Fibonacci Series for '< Resultado:
Insira o número de elementos para a série Fibonacci: 10
Série Fibonacci para 10 números: 0 1 1 2 3 5 8 13 21 34
Neste exemplo, usamos uma chamada recursiva para gerar a sequência de Fibonacci. Vemos que os primeiros dois números constantes são impressos diretamente e para os próximos números na sequência usamos uma função recursiva.
Palíndromo
Um número de palíndromo é um número que, quando lido na direção reversa, é o mesmo que lido da esquerda para a direita.
Por exemplo, o número 121 ao ler da esquerda para a direita e da direita para a esquerda é igual, ou seja, 121. Portanto, 121 é um palíndromo.
O número 291, ao ler da direita para a esquerda, ou seja, em ordem reversa, é lido como 192. Portanto, 291 não é um palíndromo.
#include using namespace std; int reverse_digits(int n, int temp) { if (n == 0) return temp; temp = (temp * 10) + (n % 10); return reverse_digits(n / 10, temp); } int main() { int num; cout<>num; int result = reverse_digits(num, 0); if (result == num) cout << 'Number '< Resultado:
Digite o número para verificar o palíndromo: 6556
Número 6556 é um palíndromo
A captura de tela para o mesmo é fornecida abaixo.
No programa acima, lemos o número de entrada da entrada padrão. Em seguida, passamos esse número para uma função recursiva para reverter os dígitos de um número. Se os dígitos invertidos e o número de entrada forem iguais, o número é um palíndromo.
Conclusão
Com isso, terminamos com a recursão. Neste tutorial, estudamos programação recursiva, função recursiva, suas vantagens / desvantagens, juntamente com vários exemplos em detalhes.
Além desses exemplos, a recursão também é usada na resolução de alguns problemas padrão, como travessias (pedido / pré-pedido / pós-pedido), torres de Hanói, travessia BFS, etc.
=> Visite aqui para aprender C ++ do zero.
Leitura recomendada
- Funções de amigo em C ++
- Polimorfismo em C ++
- Uma visão geral completa do C ++
- Tutorial da função principal do Python com exemplos práticos
- Tutorial de Pipes Unix: Pipes em Programação Unix
- Funções de biblioteca em C ++
- Mais de 70 MELHORES tutoriais em C ++ para aprender programação C ++ GRATUITAMENTE
- QTP Tutorial # 21 - Como tornar os testes QTP modulares e reutilizáveis usando bibliotecas de ações e funções
