Precisamente na Disciplina ” Programação Estatística” aprendemos recursão. A imagem acima dá uma demonstração visual do que é esse conceito. Então o que é recursão de fato, o que está sendo representado na imagem acima? Talvez você já tenha uma ideia, mas vamos a definição formal:
Recursão ou recursividade pode ser definida como a capacidade da função tem de invocar a si mesma para efetuar alguma atividade dentro de um programa.
Quando usamos recursão, de cara, percebemos que o algoritmo em questão possui menos linhas de código do que seu similar sem recursão. Porém na maioria das vezes a recursão acaba que necessitando de mais processamento do computador do que um algoritmo normal precisaria. Podemos perceber isso , por exemplo, pelo algoritmo que gera os termos da sequência de Fibonacci. Nesse caso para ele calcular o termo n, ele precisará calcular o termo n-1, para esse, o termo n-2 e assim sucessivamente até o terceiro termo já que os dois primeiro por definição são iguais a 1. Conclui-se que a recursão, de fato, possui uma necessidade maior de processamento . Contudo existem situações que tanto o algoritmo normal e o com recursão possuem a mesma complexidade.
Um exemplo simples de um algoritmo, para calcular fatorial, com suas versões sem recursão e com recursão.
Sem recursão:
1>fatorial=function(n){
2>if(n%%1!=0 || n<0 || is.numeric(n)) stop(“erro”)
3>aux=1
4>for (i in 1:n){
5> aux=i*aux
6>}
7>return(aux)}
Com recursão:
1> fatorialrec=function(n){
2>if(n%%1!=0 || n<0 || is.numeric(n)) stop(“erro”)
3>if(n==1 || n==0) return(1)
4>return(fatorialrec(n-1)*n)}
Repare que o algoritmo sem recursão possui 4 linhas de código, já o sem recursão possui 7. É de fundamental importância os casos bases para que a recursão tenha um fim. No caso acima, os casos bases são: quando n=1 e n=0 o algoritmo deve retornar 1, pois 0! e 1! são iguais a 1.
Em breve uma videoaula com mais exemplos de algoritmos com recursão.