Diferença entre recursão e iteração
Share
Diferença chave - recursão vs Iteração
Recursão e iteração podem ser usadas para resolver problemas de programação. A abordagem para resolver o problema usando recursão ou iteração depende da maneira de resolver o problema. o diferença chave entre recursão e iteração é que recursão é um mecanismo para chamar uma função dentro da mesma função enquanto a iteração é executar um conjunto de instruções repetidamente até que a condição especificada seja verdadeira. Recursão e iteração são as principais técnicas para desenvolver algoritmos e criar aplicativos de software.
CONTEÚDO
1. Visão geral e principais diferenças
2. O que é recursão
3. O que é iteração
4. Semelhanças entre recursão e iteração
5. Comparação Lado a Lado - Recursão vs Iteração em Forma Tabular
6. Resumo
O que é recursão?
Quando uma função se chama dentro da função, ela é conhecida como Recursão. Existem dois tipos de recursão. Eles são recursão finita e recursão infinita. Recursão finita tem uma condição final. Recursão infinita não tem uma condição final.
A recursão pode ser explicada usando o programa para calcular fatoriais.
n! = n * (n-1) !, se n> 0
n! = 1, se n = 0;
Consulte o código abaixo para calcular o fatorial de 3 (3! = 3 * 2 * 1).
intmain ()
valor int = fatorial (3);
printf (“fatorial é% d \ n”, valor);
retornar 0;
intfatorial (intn)
if (n == 0)
retornar 1;
outro
retorno n * fatorial (n-1);
Ao chamar fatorial (3), essa função chamará fatorial (2). Ao chamar fatorial (2), essa função chamará fatorial (1). Então fatorial (1) chamará fatorial (0). o fatorial (0) retornará 1. No programa acima, n == 0 condição no "se bloco" é a condição base. De acordo com o mesmo, a função fatorial é chamada repetidamente.
Funções recursivas estão relacionadas à pilha. Em C, o programa principal pode ter muitas funções. Portanto, main () é a função de chamada e a função chamada pelo programa principal é a função chamada. Quando a função é chamada, o controle é dado à função chamada. Depois que a execução da função é concluída, o controle é retornado para main. Então o programa principal continua. Portanto, ele cria um registro de ativação ou um quadro de pilha para continuar a execução.
Figura 01: Recursão
No programa acima, ao chamar o fatorial (3) de main, ele cria um registro de ativação na pilha de chamadas. Em seguida, o quadro da pilha fatorial (2) é criado no topo da pilha e assim por diante. O registro de ativação mantém informações sobre variáveis locais, etc. Cada vez que a função é chamada, um novo conjunto de variáveis locais é criado na parte superior da pilha. Esses quadros de pilha podem diminuir a velocidade. Da mesma forma na recursão, uma função se chama. A complexidade do tempo para uma função recursiva é encontrada pelo número de vezes que a função é chamada. A complexidade do tempo para uma chamada de função é O (1). Para n número de chamadas recursivas, a complexidade do tempo é O (n).
O que é iteração?
A iteração é um bloco de instruções que se repete várias vezes até que a condição fornecida seja verdadeira. A iteração pode ser obtida usando “for loop”, “do-while loop” ou “while loop”. A sintaxe “para loop” é a seguinte.
for (inicialização; condição; modificar)
// afirmações;
Figura 02: “para diagrama de fluxo de loop”
A etapa de inicialização é executada primeiro. Esta etapa é declarar e inicializar variáveis de controle de loop. Se a condição for verdadeira, as instruções dentro das chaves serão executadas. Essas instruções são executadas até que a condição seja verdadeira. Se a condição for falsa, o controle passará para a próxima instrução após o "for loop". Depois de executar as instruções dentro do loop, o controle vai para a seção de modificação. É para atualizar a variável de controle do loop. Em seguida, a condição é verificada novamente. Se a condição for verdadeira, as instruções dentro dos chavetas serão executadas. Dessa forma, o “for loop” itera.
No "while loop", as instruções dentro do loop são executadas até que a condição seja verdadeira.
while (condição)
//afirmações
No loop "fazer enquanto", a condição é verificada no final do loop. Portanto, o loop executa pelo menos uma vez.
Faz
//afirmações
while (condição)
O programa para encontrar o fatorial de 3 (3!) Usando a iteração (“for loop”) é o seguinte.
int main ()
intn = 3, fatorial = 1;
inti;
para (i = 1; i<=n ; i++)
fatorial = fatorial * i;
printf (“fatorial é% d \ n”, fatorial);
retornar 0;
Quais são as semelhanças entre recursão e iteração?
- Ambas são técnicas para resolver um problema.
- A tarefa pode ser resolvida em recursão ou iteração.
Qual é a diferença entre recursão e iteração?
Recursão vs Iteração | |
| Recursão é um método de chamar uma função dentro da mesma função. | A iteração é um bloco de instruções que se repete até que a condição fornecida seja verdadeira. |
| Complexidade do espaço | |
| A complexidade espacial dos programas recursivos é maior que as iterações. | A complexidade do espaço é menor nas iterações. |
| Rapidez | |
| A execução da recursão é lenta. | Normalmente, a iteração é mais rápida que a recursão. |
| Condição | |
| Se não houver condição de terminação, pode haver uma recursão infinita. | Se a condição nunca se tornar falsa, será uma iteração infinita. |
| Pilha | |
| Na recursão, a pilha é usada para armazenar variáveis locais quando a função é chamada. | Em uma iteração, a pilha não é usada. |
| Legibilidade do código | |
| Um programa recursivo é mais legível. | O programa iterativo é mais difícil de ler do que um programa recursivo. |
Resumo - Recursão vs Iteração
Este artigo discutiu a diferença entre recursão e iteração. Ambos podem ser usados para resolver problemas de programação. A diferença entre recursão e iteração é que a recursão é um mecanismo para chamar uma função dentro da mesma função e iterá-lo para executar um conjunto de instruções repetidamente até que a condição fornecida seja verdadeira. Se um problema puder ser resolvido de forma recursiva, ele também poderá ser resolvido usando iterações.
Faça o download da versão em PDF do Recursion vs Iteration
Você pode fazer o download da versão em PDF deste artigo e usá-la para fins offline, conforme nota de citação. Faça o download da versão em PDF aqui Diferença entre recursão e iteração
Referência:
1.Point, Tutoriais. “Noções básicas sobre recursão em estruturas de dados e algoritmos.”, Tutorials Point, 15 de agosto de 2017. Disponível aqui
2.nareshtechnologies. “Recursão em funções C | Tutorial do idioma C ”YouTube, YouTube, 12 de setembro de 2016. Disponível aqui
3.yusuf shakeel. “Algoritmo de recursão | Fatorial - guia passo a passo ”YouTube, YouTube, 14 de outubro de 2013. Disponível aqui
Cortesia da imagem:
1.'CPT-Recursion-Factorial-Code'Por Pluke - Obra própria, (Domínio Público) via Commons Wikimedia
2.'For-loop-diagram'By Nenhum autor legível por máquina fornecido - Trabalho próprio assumido. (CC BY-SA 2.5) via Commons Wikimedia
