Descrição indutiva: Fibonacci implementado em Java

Em 1202 Leonardo Pisano criou uma série de números conhecida como sequência de Fibonacci. Cada elemento na sequência é a soma dos dois elementos imediatamente anteriores:

                                              0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Formalmente, os elementos da sequência são definidos como:

• F(0) = 0; 
• F(1) = 1; 
• Fn = F(n-1) + F(n-2);

Descrição indutiva:

• Caso Base: Por definição, F(0) = 0 e F(1) = 1.
• Hipótese de Indução: Vamos assumir que já conhecemos os valores de F(n-2) e F(n-1).
• Caso Geral: Basta combinar os valores encontrados por hipótese de indução e somá-los para obter o resultado final fazendo F(n) = F(n-1) + F(n-2).

O algoritmo decorre imediatamente da descrição indutiva apresentada acima.

• Implementação em Java

public class Fibonacci {

 public static int fibRec(int n) {
  if (n <= 1)
   return n;
  else
   return fibRec(n - 1) + fibRec(n - 2);
 }
 // test
 public static void main(String[] args) {
  System.out.println(fibRec(11));

 }
}

Complexidade

Apesar de termos um algoritmo de fácil implementação e enxuto, a versão recursiva para os números de Fibonacci apresentada acima é extremamente ineficiente, sua complexidade é exponencial. Em uma outra postagem traremos uma implementação iterativa e mais eficiente.

@inductioncode