Nas aulas anteriores aprendemos o que é uma função / procedimento recursivo e vimos como calcular o fatorial com recursão. Nesta aula criaremos uma função recursiva para calcular um termo da sequência de fibonacci.

Como calcular a sequência de fibonacci com recursão em Portugol?

Apenas para recordar, a sequência de fibonacci inicia com os termos 0 e 1. A partir do terceiro termo, cada novo termo é a soma dos dois termos anteriores.

Uma função para calcular um determinado termo da sequência de fibonacci com recursão é bem intuitivo, pois é exatamente igual a própria definição da sequência.

Pensando em nosso ponto de parada, nosso caso base, perceba que para este problema nós temos dois casos base. Se o usuário digitar 1, significa que ele deseja saber o primeiro termo da sequência, então basta retornar este termo (0). Senão, se o usuário digitar 2, significa que ele deseja saber o segundo termo da sequência, então, basta retornar este termo (1).

	funcao inteiro fibonacci(inteiro n){
		se(n == 1)
			retorne 0 // primeiro termo
		senao{
			se(n == 2)
				retorne 1 // segundo termo
			senao
				// chamada recursiva
		}
	}

Agora, o passo seguinte é fazer a soma dos dois termos anteriores quando o usuário desejar um termo a partir do terceiro. Como não sabemos os termos anteriores, precisamos então fazer aqui duas chamadas recursivas, uma para o termo n – 1 e outra para o termo n – 2.

	funcao inteiro fibonacci(inteiro n){
		se(n == 1)
			retorne 0
		senao{
			se(n == 2)
				retorne 1
			senao
				retorne fibonacci(n - 1) + fibonacci(n - 2)
		}
	}

Código em Portugol para calcular um termo da sequência de fibonacci com recursão

programa{
	/*
		Aula 113: Fibonacci com função recursiva

		Escrito por Wagner Gaspar
		Abril de 2021
	*/

	funcao inteiro fibonacci(inteiro n){
		se(n == 1)
			retorne 0
		senao{
			se(n == 2)
				retorne 1
			senao
				retorne fibonacci(n - 1) + fibonacci(n - 2)
		}
	}
	
	funcao inicio(){
		inteiro n

		escreva("Qual termo deseja descobrir? ")
		leia(n)

		escreva("O termo ", n, " é: ", fibonacci(n))
	}
}