Função recursiva C ++

Sabe -se que um processo em que uma função específica se chama direta ou indiretamente é uma recursão, e essa função respectiva é uma função recursiva. O processo de recursão lida com a iteração de vários números para a mesma função. Para encerrar a execução de um processo de recursão, precisamos ter um caso base seguido por qualquer condição. Este tutorial usa o envolvimento das funções de recursão em C ++; portanto, antes de ler isso, você deve estar familiarizado com o básico desta linguagem de programação.

Recursão é uma abordagem eficaz para dissolver os problemas, como tarefas complexas de cálculos matemáticos. Isso é feito distribuindo a tarefa em subtareadas. Este processo é feito seguindo a regra de divisão e conquista. Não é uma coisa obrigatória sempre usar um processo de recursão em seu programa para a repetição. Qualquer problema que seja resolvido por meio de recursão também pode ser resolvido por meio de iteração. Mas a função recursiva é mais eficiente na programação, pois o código é muito curto e facilmente compreensível ao executar a mesma tarefa. O processo de recursão é sempre recomendado para problemas como pesquisa e classificação, travessias de árvores, etc.

Observação: O processo de recursão deve ter uma condição de rescisão ou uma classe base. No segundo caso, isso levará a execuções infinitas como um loop de iterações.

Sintaxe da função recursiva (C ++)

A sintaxe básica da função recursiva é dada como:

Void Recurse ()
// Declarações)
recurso();

O conceito é dividir um problema em muitos problemas menores e depois adicionar todas as condições básicas que podem parar a recursão.

Condição base

Em qualquer programa recursivo, a solução de um problema maior é expressa em problemas menores.

int fac (int n)

se (n < = 1) // base case
retornar 1;
outro
'Outra declaração'

A declaração/condição de 'n < =1' is defined here, and hence the larger value can be solved by converting to a smaller one until the condition of the base case is fulfilled. If we don't use a base condition in our program, then there will be no ending point specifying the code, the infinite execution will occur. Here we will use a sample example.

Função simples

Agora considere uma amostra de uma função recursiva na qual tomamos um valor no programa principal e depois o passamos para a função. Dentro de uma função, usamos uma declaração if-else. A parte 'se' da declaração refere -se à condição base para encerrar a função ou limitar a saída. Isso será aplicado quando o valor for menor que 1.

If (val < 1)

Enquanto o recurso principal é aplicado na parte 'else' da função. Esta é a função recursiva.

# Função (val - 1)

O valor é exibido antes e depois desta declaração, portanto a saída conterá os números em descendência e em ordem crescente. A execução do código é feita através de um compilador G ++. '-o' é usado para salvar a saída de um código-fonte em um arquivo de saída.

$ G ++ -O R1 R1.c
$ ./r1

Agora, queremos ver o efeito da condição base neste programa. Veremos o valor resultante; Se removermos a instrução if-else do mesmo programa descrito acima, qual será a saída.

Você pode ver que o restante do código permanece inalterado após a remoção da declaração condicional. Depois de remover a declaração base, a saída será a imagem abaixo. Não haverá endpoint definido para esta execução. Você pode notar que a saída é um tipo infinito de um único número.

Essa mesma saída dura muitas linhas até que uma mensagem de dump do núcleo seja mostrada.

Trabalho de recursão

Suponha que um programador esteja disposto a determinar a soma dos primeiros n números, há muitas maneiras de determinar a soma, mas a mais simples é adicionar os números começando de 1 a n. Portanto, a função ficará assim:

F (n) = 1+2+3+4+5+…+n

O exemplo acima é a simples adição dos números. A segunda abordagem lida com o uso de uma função recursiva.

F (n) = 1 n = 1
F (n) = n + f (n-1) n> 1

Agora você pode apontar a diferença entre as duas abordagens. Na segunda abordagem, f () é uma dissimilaridade básica, como é chamada.

A recursão é de dois tipos. Um é uma recursão direta. O segundo é uma recursão indireta. Uma função é chamada de recursiva indireta se tiver uma função para outra função e que outra função chama a primeira função. Uma amostra para recursão direta é ilustrada como:

Int f (int n)
F (n);
// Algum código

Enquanto uma amostra para a recursão indireta é representada como:

void f (int n)
f1 ();
void f1 (int n)
f ();
retornar;

Agora elaboraremos os dois tipos de funções recursivas através de alguns exemplos básicos.

Recursão direta

Exemplo 1

Este exemplo lida com o cálculo da série Fibonacci. Novamente, o conceito é o mesmo; Uma declaração condicional é usada aqui para interromper a condição; O valor deve ser igual a zero. Caso contrário, se o valor for igual a 1 ou 2, ele retornará 1. Como esta formação de série precisa de 2 números, o número usado no programa principal deve ser maior que 2. A fórmula da declaração para o fibonacci está escrita na arte 'else' da condição. Esta é principalmente a recursão do programa.

# Função (val - 1) + função (val - 2))

Enquanto a função principal iniciará a chamada funcional, ignorando o valor. Este valor é um número até o qual a saída deve ser. A saída pode ser verificada através do terminal Linux por um compilador G ++.

Exemplo 2

Este exemplo lida com o cálculo fatorial de um número. Para este cálculo, um número deve ser maior que 1, então aqui aplicamos uma condição base; Se esta parte da instrução 'If' for cumprida, o programa será encerrado; Caso contrário, a operação matemática é aplicada ao número.

Val * Função (Val - 1)

Esta é a função de recursão, na qual a resposta da função é novamente utilizada na chamada de função.

O valor resultante é mostrado abaixo.

Recursão indireta

Aplicaremos o mesmo cálculo de fatorial indiretamente. Como descrevemos anteriormente, que na recursão indireta, as funções não o chamam, então precisamos de outra função para esse fim. Dê um exemplo que tenha duas funções. Na função A, a função de recursão é declarada da mesma maneira que no exemplo anterior, mas a chamada de função é para a segunda função, função-b. A função B contém o mesmo método de cálculo e contém a chamada recursiva para a função A.

No programa principal, uma chamada de função para a função A é feita.

Quando você vê a saída, você notará que a resposta para ambos os métodos de recursão é a mesma, mas apenas a diferença está na abordagem usada.

Conclusão

'C ++ função recursiva' tem muitas vantagens, conforme usado nos processos de busca e classificação. A condição base tem o principal papel na execução da recursão, pois limita a saída e a execução infinita. Os exemplos comumente usados ​​são explicados aqui para fornecer a compreensão do usuário da recursão.