DC-UFRPE/Bacharelado em Ciência da Computação/Projeto e Análise de Algoritmos/Recursão
Recursividade
editarEm ciência da computação, a recursividade é a definição de uma sub-rotina (função ou método) que pode invocar a si mesma. A grande vantagem da recursão está na possibilidade de usar um programa de computador finito para definir, analisar ou produzir um estoque potencialmente infinito de sentenças, designs ou outros dados.
Em todas as funções recursivas existe:
- Um caso base (um ou mais) cujo resultado é imediatamente conhecido.
- Um passo recursivo em que se tenta resolver um sub-problema do problema inicial.
A recursão está profundamente entranhada na Teoria da computação, uma vez que a equivalência teórica entre as funções recursivas e as máquinas de Turing está na base das idéias sobre a universalidade do computador moderno.
Exemplo
editarAqui temos um exemplo de um código simples em C, sendo executado iterativamente:
#include <stdio.h>
int iterativa(int i){
for(i; i < 5; i++){
printf("%d", i);
{
}
int main(){
iterativa(0);
return 0;
}
O código de saída será:
0
1
2
3
4
5
Agora vamos fazer seu equivalente recursivo:
#include <stdio.h>
int recursiva(int i){
if(i < 5){
printf("%d", i);
recursiva(i + 1);
{
}
int main(){
recursiva(0);
return 0;
}
O código de saída será:
0
1
2
3
4
5
Note que os códigos de saída são iguais, mas a versão recursiva permite que a função se quebre em várias subfunções, exibindo com maior clareza o processo.