Bom, o código para calcular uma Sequência de Fibonnaci via recursão é amplamente conhecido, então não vejo necessidade de postá-lo aqui. Você pode pesquisá-lo na internet, se é isso que deseja.
Se o que deseja é entender recursão, note que o conceito é um método/função/procedimento que chama ela mesma.
Escrevendo de novo: uma função/método recursivo é um método que executa a si mesmo.
Escrevendo de novo: uma função/método recursivo é um método que executa a si mesmo.
Escrevendo de novo: uma função/método recursivo é um método que executa a si mesmo.
O link da Wikipedia é um pouco mais matemático que o necessário. Este outro link também, mas possui alguns exemplos de aplicação em programação.
Mas vamos lá.
Por uma função/método que chama a si mesmo, entenda um código assim:
public tipo fazAlgumaCoisa(tipo valorQualquer){
fazAlgumaCoisa(valorQualquer);
}
Note que a função fazAlgumaCoisa() chama a si própria.
Obviamente, a chamada a função fazAlgumaCoisa() deve ser interrompida em algum momento, senão nunca obteremos o resultado da execução da função fazAlgumaCoisa(), além de obter algum erro. O erro depende da linguagem e das operações realizadas pela função. Pode falta de memória (OutOfMemoryError), estouro de pilha (StackOverFlow), etc.
Então precisamos criar uma condição de parada para a chamada a função fazAlgumaCoisa(). Se essa condição for atingida, ao invés de chamar a função fazAlgumaCoisa(), nós retornamos algum valor (ou mesmo não fazemos nada, dependendo do caso). Nossa função fica:
public tipo fazAlgumaCoisa(tipo valorQualquer){
if (atingiu_a_condicao_de_parada){
return valorQualquer;
} else{
return fazAlgumaCoisa(valorQualquer);
}
}
E é isso. Essa é a estrutura comum de uma função recursiva. Vamos a um exemplo para fixar a ideia. Ao invés de fibonnaci, vamos somar alguns números inteiros (outro exemplo clássico). Somaremos os números de 0 até X. Então:
- a função recebe um parâmetro X (100, por exemplo), que é o número até o qual nós desejamos somar;
- somaremos todos os números de 1 até X, então nosso critério de parada pode ser quando o número a ser somado já é X ou é 1. Optaremos pelo 1;
- para não somarmos novamente o mesmo número (e ficarmos presos e uma repetição infinita), devemos alterar o número antes de chamar novamente a função recursiva. Podemos incrementar ou decrementar o número. Como vamos de X até um, vamos decrementar o número até que ele seja um, o que ativa nossa condição de parada.
public int somaNumeros(int numero){
if (numero == 1){
return numero;
}else{
return numero + somaNumeros(numero-1);
}
}
Veja que na linha:
return numero + somaNumeros(numero-1);
a adição só é executada quando a função somaNumeros(numero-1) retorna, então a função fica aguardando nesse ponto até que essa função retorne.
Abraço.
