Sequência de Fibonacci recursiva em Java

156

Por favor, explique este código simples:

public int fibonacci(int n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
      return 1;
   else
      return fibonacci(n - 1) + fibonacci(n - 2);
}

Estou confuso com a última linha, especialmente porque se n = 5, por exemplo, então fibonacci (4) + fibonacci (3) seriam chamados e assim por diante, mas eu não entendo como esse algoritmo calcula o valor no índice 5 por este método. Por favor, explique com muitos detalhes!

Index Hacker
fonte
8
Observe que isso é recursivo e é executado em tempo exponencial. É ineficiente para grandes valores de N. Usando uma abordagem iterativa, consegui calcular os primeiros 10.000 números na sequência. Eles podem ser encontrados aqui - goo.gl/hnbF5
Adam
@ AdamFisher: Você pode compartilhar o código usado para calcular 10.000 números em sequência? Na verdade, estou curioso para saber disso.
Shumail
4
@AdamFisher O link que você referiu está morto.
IRuth
2
Este vídeo vai explicar para entender a função recursiva em 10 minuts youtube.com/watch?v=t4MSwiqfLaY
Chathura Palihakkara
2
Há também uma abordagem iterativa que pode ser menos difícil para você. Grande artigo sobre recursiva e iterativa com código aqui - codeflex.co/java-get-fibonacci-number-by-index
user5495300

Respostas:

165

Na sequência de fibonacci, cada item é a soma dos dois anteriores. Então, você escreveu um algoritmo recursivo.

Assim,

fibonacci(5) = fibonacci(4) + fibonacci(3)

fibonacci(3) = fibonacci(2) + fibonacci(1)

fibonacci(4) = fibonacci(3) + fibonacci(2)

fibonacci(2) = fibonacci(1) + fibonacci(0)

Agora você já sabe fibonacci(1)==1 and fibonacci(0) == 0 . Portanto, você pode calcular posteriormente os outros valores.

Agora,

fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5

E a partir da sequência de fibonacci 0,1,1,2,3,5,8,13,21...., podemos ver que, para 5th elementa sequência de fibonacci, retorna 5.

Veja aqui o Tutorial de Recursão .

RanRag
fonte
funcionará, mas não será otimizado até e a menos que seja otimizado. Por favor, dê uma olhada na minha resposta. Deixe-me saber em caso de sugestões / comentários
M Sach
52

Existem 2 problemas com o seu código:

  1. O resultado é armazenado em int, que pode lidar apenas com os primeiros 48 números de fibonacci; depois disso, o número inteiro preenche menos o bit e o resultado está errado.
  2. Mas você nunca pode executar fibonacci (50).
    O código
    fibonacci(n - 1) + fibonacci(n - 2)
    está muito errado.
    O problema é que ele chama de fibonacci não 50 vezes, mas muito mais.
    Inicialmente, chama fibonacci (49) + fibonacci (48),
    próximo fibonacci (48) + fibonacci (47) e fibonacci (47) + fibonacci (46)
    Cada vez que se torna pior, a complexidade é exponencial. insira a descrição da imagem aqui

A abordagem do código não recursivo:

 double fibbonaci(int n){
    double prev=0d, next=1d, result=0d;
    for (int i = 0; i < n; i++) {
        result=prev+next;
        prev=next;
        next=result;
    }
    return result;
}
chro
fonte
4
Embora algumas das outras respostas expliquem mais claramente a recursão, essa é provavelmente a resposta mais relevante em um nível mais profundo.
precisa saber é o seguinte
1
O que significa "número inteiro preenchido menos bit"?
Richard
1
@richard, trata-se de como o número inteiro é armazenado. Depois que int atingiu 2 ^ 31-1, o próximo bit é sobre sign, então o número se torna negativo.
cro
Muito mais rápido que recursivo. A única reserva é que não funcionará para n = 1. Condição adicional é necessária
v0rin
1
"Cada vez que se tornou 2 ^ n pior", na verdade, o número total de chamadas de função é 2*fibonacci(n+1)-1, portanto, ele cresce com a mesma complexidade dos números de fibonacci, que é 1.618 ^ n em vez de 2 ^ n
Aemyl
37

No pseudo-código, onde n = 5, ocorre o seguinte:

fibonacci (4) + fibonnacci (3)

Isso se divide em:

(fibonacci (3) + fibonnacci (2)) + (fibonacci (2) + fibonnacci (1))

Isso se divide em:

(((fibonacci (2) + fibonnacci (1)) + ((fibonacci (1) + fibonnacci (0))) + (((fibonacci (1) + fibonnacci (0)) + 1))

Isso se divide em:

((((fibonacci (1) + fibonnacci (0)) + 1) + ((1 + 0)) + ((1 + 0) + 1))

Isso se divide em:

((((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1))

Isto resulta em: 5

Dada a sequência de fibonnacci é 1 1 2 3 5 8 ... , o quinto elemento é 5. Você pode usar a mesma metodologia para descobrir as outras iterações.

Dan Hardiker
fonte
Eu acho que essa resposta explica as perguntas da melhor maneira. Realmente simples
Amit
Isso é legal. Explica o valor no enésimo termo e as séries a seguir.
Ponto
12

A recursão pode ser difícil de entender algumas vezes. Apenas avalie-o em um pedaço de papel para um número pequeno:

fib(4)
-> fib(3) + fib(2)
-> fib(2) + fib(1) + fib(1) + fib(0)
-> fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
-> 1 + 0 + 1 + 1 + 0
-> 3

Não tenho certeza de como o Java realmente avalia isso, mas o resultado será o mesmo.

tim
fonte
na segunda linha, de onde vêm os 1 e 0 no final?
Pocockn 27/05
1
@pocockn fib (2) = fib (1) + fib (0)
tim
Então você tem fib (4), então n-1 e n-2 seria fib (3) + fib (2), então você faz o n-1 e n-2 novamente e obtém -> fib (2) + fib (1 ), de onde você tirou o + fib (1) + fib (0)? Adicionado no final
pocockn 27/05
@pocockn fib (2) + fib (1) é de fib (3), fib (1) + fib (0) é de fib (2)
tim
12

Você também pode simplificar sua função, da seguinte maneira:

public int fibonacci(int n)  {
    if (n < 2) return n;

    return fibonacci(n - 1) + fibonacci(n - 2);
}
Otavio Ferreira
fonte
Como isso é diferente do que isto ou isto ou esta resposta?
Tunaki
6
É apenas mais curto e mais fácil de ler, que algoritmos deve ser sempre =)
Otavio Ferreira
@OtavioFerreira a única resposta que conseguiu resolver o meu problema, bom trabalho
KKKKK
8
                                F(n)
                                /    \
                            F(n-1)   F(n-2)
                            /   \     /      \
                        F(n-2) F(n-3) F(n-3)  F(n-4)
                       /    \
                     F(n-3) F(n-4)

Um ponto importante a ser observado é que esse algoritmo é exponencial porque não armazena o resultado de números calculados anteriores. por exemplo, F (n-3) é chamado 3 vezes.

Para mais detalhes, consulte o algoritmo do capítulo 0.2 dasgupta

Amandeep Kamboj
fonte
Existe uma metodologia de programação pela qual podemos evitar o cálculo de F (n) para o mesmo n repetidamente, usando a Programação dinâmica
Amit_Hora
8

A maioria das respostas é boa e explica como funciona a recursão em fibonacci.

Aqui está uma análise sobre as três técnicas que também incluem recursão:

  1. For Loop
  2. Recursão
  3. Memoização

Aqui está o meu código para testar todos os três:

public class Fibonnaci {
    // Output = 0 1 1 2 3 5 8 13

    static int fibMemo[];

    public static void main(String args[]) {
        int num = 20;

        System.out.println("By For Loop");
        Long startTimeForLoop = System.nanoTime();
        // returns the fib series
        int fibSeries[] = fib(num);
        for (int i = 0; i < fibSeries.length; i++) {
            System.out.print(" " + fibSeries[i] + " ");
        }
        Long stopTimeForLoop = System.nanoTime();
        System.out.println("");
        System.out.println("For Loop Time:" + (stopTimeForLoop - startTimeForLoop));


        System.out.println("By Using Recursion");
        Long startTimeRecursion = System.nanoTime();
        // uses recursion
        int fibSeriesRec[] = fibByRec(num);

        for (int i = 0; i < fibSeriesRec.length; i++) {
            System.out.print(" " + fibSeriesRec[i] + " ");
        }
        Long stopTimeRecursion = System.nanoTime();
        System.out.println("");
        System.out.println("Recursion Time:" + (stopTimeRecursion -startTimeRecursion));



        System.out.println("By Using Memoization Technique");
        Long startTimeMemo = System.nanoTime();
        // uses memoization
        fibMemo = new int[num];
        fibByRecMemo(num-1);
        for (int i = 0; i < fibMemo.length; i++) {
            System.out.print(" " + fibMemo[i] + " ");
        }
        Long stopTimeMemo = System.nanoTime();
        System.out.println("");
        System.out.println("Memoization Time:" + (stopTimeMemo - startTimeMemo));

    }


    //fib by memoization

    public static int fibByRecMemo(int num){

        if(num == 0){
            fibMemo[0] = 0;
            return 0;
        }

        if(num ==1 || num ==2){
          fibMemo[num] = 1;
          return 1; 
        }

        if(fibMemo[num] == 0){
            fibMemo[num] = fibByRecMemo(num-1) + fibByRecMemo(num -2);
            return fibMemo[num];
        }else{
            return fibMemo[num];
        }

    }


    public static int[] fibByRec(int num) {
        int fib[] = new int[num];

        for (int i = 0; i < num; i++) {
            fib[i] = fibRec(i);
        }

        return fib;
    }

    public static int fibRec(int num) {
        if (num == 0) {
            return 0;
        } else if (num == 1 || num == 2) {
            return 1;
        } else {
            return fibRec(num - 1) + fibRec(num - 2);
        }
    }

    public static int[] fib(int num) {
        int fibSum[] = new int[num];
        for (int i = 0; i < num; i++) {
            if (i == 0) {
                fibSum[i] = i;
                continue;
            }

            if (i == 1 || i == 2) {
                fibSum[i] = 1;
                continue;
            }

            fibSum[i] = fibSum[i - 1] + fibSum[i - 2];

        }
        return fibSum;
    }

}

Aqui estão os resultados:

By For Loop
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
For Loop Time:347688
By Using Recursion
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
Recursion Time:767004
By Using Memoization Technique
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
Memoization Time:327031

Portanto, podemos ver que a memorização é a melhor opção em termos de tempo e que o loop for corresponde de perto.

Mas a recursão leva mais tempo e pode ser que você deva evitar na vida real. Além disso, se você estiver usando recursão, certifique-se de otimizar a solução.

Pritam Banerjee
fonte
1
"Aqui podemos ver que o loop é o melhor horário"; "For Time Loop: 347688"; "Tempo de memorização: 327031"; 347688> 327031.
AjahnCharles
@ CodeConfident Sim, eu vi esse erro hoje e estava prestes a corrigi-lo. Obrigado de qualquer forma :).
Pritam Banerjee
7

Este é o melhor vídeo que eu descobri que explica completamente a recursão e a sequência de Fibonacci em Java.

http://www.youtube.com/watch?v=dsmBRUCzS7k

Este é o código para a sequência e sua explicação é melhor do que eu jamais poderia tentar digitar.

public static void main(String[] args)
{
    int index = 0;
    while (true)
    {
        System.out.println(fibonacci(index));
        index++;
    }
}
    public static long fibonacci (int i)
    {
        if (i == 0) return 0;
        if (i<= 2) return 1;

        long fibTerm = fibonacci(i - 1) + fibonacci(i - 2);
        return fibTerm;
    }
user2718538
fonte
5

Para uma solução recursiva de fibonacci, é importante salvar a saída de números menores de fibonacci, enquanto recupera o valor de um número maior. Isso é chamado de "Memoizing".

Aqui está um código que usa a memorização dos valores menores de fibonacci, enquanto recupera um número maior de fibonacci. Esse código é eficiente e não faz várias solicitações da mesma função.

import java.util.HashMap;

public class Fibonacci {
  private HashMap<Integer, Integer> map;
  public Fibonacci() {
    map = new HashMap<>();
  }
  public int findFibonacciValue(int number) {
    if (number == 0 || number == 1) {
      return number;
    }
    else if (map.containsKey(number)) {
      return map.get(number);
    }
    else {
      int fibonacciValue = findFibonacciValue(number - 2) + findFibonacciValue(number - 1);
      map.put(number, fibonacciValue);
      return fibonacciValue;
    }
  }
}
Amarjit Datta
fonte
4

na sequência de fibonacci , os dois primeiros itens são 0 e 1; o outro item é a soma dos dois itens anteriores. ou seja:
0 1 1 2 3 5 8 ...

portanto, o quinto item é a soma do quarto e do terceiro itens.

yurib
fonte
4

Michael Goodrich e cols. Fornecem um algoritmo realmente inteligente em estruturas de dados e algoritmos em Java, para resolver fibonacci recursivamente em tempo linear, retornando uma matriz de [fib (n), fib (n-1)].

public static long[] fibGood(int n) {
    if (n < = 1) {
        long[] answer = {n,0};
        return answer;
    } else {
        long[] tmp = fibGood(n-1);
        long[] answer = {tmp[0] + tmp[1], tmp[0]};
        return answer;
    }
}

Isso produz fib (n) = fibGood (n) [0].

Rae
fonte
4

Aqui está a solução O (1):

 private static long fibonacci(int n) {
    double pha = pow(1 + sqrt(5), n);
    double phb = pow(1 - sqrt(5), n);
    double div = pow(2, n) * sqrt(5);

    return (long) ((pha - phb) / div);
}

Fórmula de número de Fibonacci da Binet usada para implementação acima. Para entradas grandes, longpode ser substituído por BigDecimal.

Samir
fonte
3

Uma sequência de Fibbonacci é aquela que soma o resultado de um número quando adicionada ao resultado anterior, começando com 1.

      so.. 1 + 1 = 2
           2 + 3 = 5
           3 + 5 = 8
           5 + 8 = 13
           8 + 13 = 21

Depois de entendermos o que é Fibbonacci, podemos começar a decompor o código.

public int fibonacci(int n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
      return 1;
   else
      return fibonacci(n - 1) + fibonacci(n - 2);
}

A primeira, se a declaração procurar um caso base, onde o loop pode ocorrer. A declaração else if abaixo está fazendo o mesmo, mas pode ser reescrita dessa maneira ...

    public int fibonacci(int n)  {
        if(n < 2)
             return n;

        return fibonacci(n - 1) + fibonacci(n - 2);
    }

Agora que um caso base é estabelecido, precisamos entender a pilha de chamadas. Sua primeira chamada para "fibonacci" será a última a ser resolvida na pilha (sequência de chamadas), conforme elas serão resolvidas na ordem inversa da qual foram chamadas. O último método chamado resolve primeiro, depois o último a ser chamado antes desse e assim por diante ...

Portanto, todas as chamadas são feitas primeiro antes que qualquer coisa seja "calculada" com esses resultados. Com uma entrada de 8, esperamos uma saída de 21 (veja a tabela acima).

fibonacci (n - 1) continua sendo chamado até atingir o caso base, então fibonacci (n - 2) é chamado até atingir o caso base. Quando a pilha começar a somar o resultado na ordem inversa, o resultado será mais ou menos assim ...

1 + 1 = 1        ---- last call of the stack (hits a base case).
2 + 1 = 3        ---- Next level of the stack (resolving backwards).
2 + 3 = 5        ---- Next level of the stack (continuing to resolve).

Eles continuam borbulhando (resolvendo para trás) até que a soma correta seja retornada à primeira chamada na pilha e é assim que você obtém sua resposta.

Dito isto, esse algoritmo é muito ineficiente porque calcula o mesmo resultado para cada ramificação em que o código é dividido. Uma abordagem muito melhor é uma abordagem "de baixo para cima", em que não é necessária nenhuma memorização (cache) ou recursão (pilha profunda de chamadas).

Igual a...

        static int BottomUpFib(int current)
        {
            if (current < 2) return current;

            int fib = 1;
            int last = 1;

            for (int i = 2; i < current; i++)
            {
                int temp = fib;
                fib += last;
                last = temp;
            }

            return fib;
        }
Jeffrey Ferreiras
fonte
2

A maioria das soluções oferecidas aqui é executada com complexidade O (2 ^ n). Recalcular nós idênticos na árvore recursiva é ineficiente e desperdiça ciclos da CPU.

Podemos usar a memorização para executar a função fibonacci em O (n) time

public static int fibonacci(int n) {
    return fibonacci(n, new int[n + 1]);
}

public static int fibonacci(int i, int[] memo) {

    if (i == 0 || i == 1) {
        return i;
    }

    if (memo[i] == 0) {
        memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
    }
    return memo[i];
}

Se seguirmos a rota de programação dinâmica Bottom-Up, o código abaixo é simples o suficiente para calcular fibonacci:

public static int fibonacci1(int n) {
    if (n == 0) {
        return n;
    } else if (n == 1) {
        return n;
    }
    final int[] memo = new int[n];

    memo[0] = 0;
    memo[1] = 1;

    for (int i = 2; i < n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n - 1] + memo[n - 2];
}
realPK
fonte
2

Por que essa resposta é diferente

Todas as outras respostas também:

  • Imprime em vez de devoluções
  • Faz 2 chamadas recursivas por iteração
  • Ignora a pergunta usando loops

(à parte: nada disso é realmente eficiente; use a fórmula de Binet para calcular diretamente a enésima termo)

Fibra recursiva da cauda

Aqui está uma abordagem recursiva que evita uma chamada dupla recursiva, passando a resposta anterior E a anterior.

private static final int FIB_0 = 0;
private static final int FIB_1 = 1;

private int calcFibonacci(final int target) {
    if (target == 0) { return FIB_0; }
    if (target == 1) { return FIB_1; }

    return calcFibonacci(target, 1, FIB_1, FIB_0);
}

private int calcFibonacci(final int target, final int previous, final int fibPrevious, final int fibPreviousMinusOne) {
    final int current = previous + 1;
    final int fibCurrent = fibPrevious + fibPreviousMinusOne;
    // If you want, print here / memoize for future calls

    if (target == current) { return fibCurrent; }

    return calcFibonacci(target, current, fibCurrent, fibPrevious);
}
AjahnCharles
fonte
1

É uma sequência básica que exibe ou obtém uma saída de 1 1 2 3 5 8; é uma sequência em que a soma do número anterior, o número atual, será exibida a seguir.

Tente assistir ao link abaixo da sequência Java Recursive Fibonacci Tutorial

public static long getFibonacci(int number){
if(number<=1) return number;
else return getFibonacci(number-1) + getFibonacci(number-2);
}

Clique aqui Assista a sequência de Fibonacci recursiva Java Tutorial para alimentação com colher

Jaymelson Galang
fonte
O que ele precisava entender é como o código funciona e por que está escrito da maneira que está escrito.
Adarsh
Acho que mencionei na minha primeira frase como funciona? eu escrevo o código para torná-lo mais simples. btw, desculpe.
Jaymelson Galang
Nada de errado com o seu código. Só o cara queria entender como esse código funcionava. Verifique a resposta do RanRag. Algo desse tipo :) #
Adarsh
ahh ok, desculpe, eu sou iniciante aqui no stackoverflow. só quero ajudar ^ _ ^ #
Jaymelson Galang
1

Eu acho que é uma maneira simples:

public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int number = input.nextInt();
        long a = 0;
        long b = 1;
        for(int i = 1; i<number;i++){
            long c = a +b;
            a=b;
            b=c;
            System.out.println(c);
        }
    }
}
user3787713
fonte
1

A resposta RanRag (aceita) funcionará bem, mas essa não é a solução otimizada até e a menos que seja memorizada conforme explicado na resposta Anil.

Para uma abordagem recursiva a seguir, as chamadas de método TestFibonaccisão mínimas

public class TestFibonacci {

    public static void main(String[] args) {

        int n = 10;

        if (n == 1) {
            System.out.println(1);

        } else if (n == 2) {
            System.out.println(1);
            System.out.println(1);
        } else {
            System.out.println(1);
            System.out.println(1);
            int currentNo = 3;
            calFibRec(n, 1, 1, currentNo);
        }

    }

    public static void calFibRec(int n, int secondLast, int last,
            int currentNo) {
        if (currentNo <= n) {

            int sum = secondLast + last;
            System.out.println(sum);
            calFibRec(n, last, sum, ++currentNo);
        }
    }

}
M Sach
fonte
1
public class febo 
{
 public static void main(String...a)
 {
  int x[]=new int[15];  
   x[0]=0;
   x[1]=1;
   for(int i=2;i<x.length;i++)
   {
      x[i]=x[i-1]+x[i-2];
   }
   for(int i=0;i<x.length;i++)
   {
      System.out.println(x[i]);
   }
 }
}
msanford
fonte
1

Usando um ConcurrentHashMap interno que teoricamente pode permitir que essa implementação recursiva opere corretamente em um ambiente multithread, implementei uma função fib que usa o BigInteger e o Recursion. Demora cerca de 53ms para calcular os primeiros 100 números de fib.

private final Map<BigInteger,BigInteger> cacheBig  
    = new ConcurrentHashMap<>();
public BigInteger fibRecursiveBigCache(BigInteger n) {
    BigInteger a = cacheBig.computeIfAbsent(n, this::fibBigCache);
    return a;
}
public BigInteger fibBigCache(BigInteger n) {
    if ( n.compareTo(BigInteger.ONE ) <= 0 ){
        return n;
    } else if (cacheBig.containsKey(n)){
        return cacheBig.get(n);
    } else {
        return      
            fibBigCache(n.subtract(BigInteger.ONE))
            .add(fibBigCache(n.subtract(TWO)));
    }
}

O código de teste é:

@Test
public void testFibRecursiveBigIntegerCache() {
    long start = System.currentTimeMillis();
    FibonacciSeries fib = new FibonacciSeries();
    IntStream.rangeClosed(0,100).forEach(p -&R {
        BigInteger n = BigInteger.valueOf(p);
        n = fib.fibRecursiveBigCache(n);
        System.out.println(String.format("fib of %d is %d", p,n));
    });
    long end = System.currentTimeMillis();
    System.out.println("elapsed:" + 
    (end - start) + "," + 
    ((end - start)/1000));
}
e a saída do teste é:
    .
    .
    .
    .
    .
    A fib de 93 é 12200160415121876738
    A fib de 94 é 19740274219868223167
    a fib de 95 é 31940434634990099905
    fib de 96 é 51680708854858323072
    fib de 97 é 83621143489848422977
    fib de 98 é 135301852344706746049
    a fib de 99 é 218922995834555169026
    a fib de 100 é 354224848179261915075
    decorrido: 58,0
George Curington
fonte
1

Aqui está um recursivo de uma linha de febonacci:

public long fib( long n ) {
        return n <= 0 ? 0 : n == 1 ? 1 : fib( n - 1 ) + fib( n - 2 );
}
RonTLV
fonte
1

Tente isto

private static int fibonacci(int n){
    if(n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
markus rytter
fonte
0

Apenas para complementar, se você quiser calcular números maiores, use o BigInteger.

Um exemplo iterativo.

import java.math.BigInteger;
class Fibonacci{
    public static void main(String args[]){
        int n=10000;
        BigInteger[] vec = new BigInteger[n];
        vec[0]=BigInteger.ZERO;
        vec[1]=BigInteger.ONE;
        // calculating
        for(int i = 2 ; i<n ; i++){
            vec[i]=vec[i-1].add(vec[i-2]);
        }
        // printing
        for(int i = vec.length-1 ; i>=0 ; i--){
            System.out.println(vec[i]);
            System.out.println("");
        }
    }
}
Tiago Zortea
fonte
0

http://en.wikipedia.org/wiki/Fibonacci_number em mais detalhes

public class Fibonacci {

    public static long fib(int n) {
        if (n <= 1) return n;
        else return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        for (int i = 1; i <= N; i++)
            System.out.println(i + ": " + fib(i));
    }

}

Faça com que seja tão simples quanto necessário, sem necessidade de usar o loop while e outro loop

vikas
fonte
0
public class FibonacciSeries {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        for (int i = 0; i <= N; i++) {
            int result = fibonacciSeries(i);
            System.out.println(result);
        }
        scanner.close();
    }

    private static int fibonacciSeries(int n) {
        if (n < 0) {
            return 1;
        } else if (n > 0) {
            return fibonacciSeries(n - 1) + fibonacciSeries(n - 2);
        }
        return 0;
    }
}
user3231661
fonte
0

Use while:

public int fib(int index) {
    int tmp = 0, step1 = 0, step2 = 1, fibNumber = 0;
    while (tmp < index - 1) {
        fibNumber = step1 + step2;
        step1 = step2;
        step2 = fibNumber;
        tmp += 1;
    };
    return fibNumber;
}

A vantagem desta solução é que é fácil ler e entender o código, esperando que ajude

Gavriel Cohen
fonte
0

Uma sequência de Fibbonacci é aquela que soma o resultado de um número e, em seguida, adicionamos ao resultado anterior, devemos começar a partir de 1. Eu estava tentando encontrar uma solução baseada em algoritmo, então construo o código recursivo, notei que mantenho o número anterior e eu mudei de posição. Estou pesquisando a sequência de Fibbonacci de 1 a 15.

public static void main(String args[]) {

    numbers(1,1,15);
}


public static int numbers(int a, int temp, int target)
{
    if(target <= a)
    {
        return a;
    }

    System.out.print(a + " ");

    a = temp + a;

    return numbers(temp,a,target);
}
Mathias Stavrou
fonte
-1
 public static long fib(int n) {
    long population = 0;

    if ((n == 0) || (n == 1)) // base cases
    {
        return n;
    } else // recursion step
    {

        population+=fib(n - 1) + fib(n - 2);
    }

    return population;
}
Ian Mukunya Douglas
fonte
-1

Fibonacci simples

public static void main(String[]args){

    int i = 0;
    int u = 1;

    while(i<100){
        System.out.println(i);
        i = u+i;
        System.out.println(u);
        u = u+i;
    }
  }
}
Marcxcx
fonte
2
Bem-vindo ao SO. Enquanto sua resposta calcula a sequência de Fibonacci. Sua resposta não responde ao OP, que perguntou sobre funções recursivas.
James K
-2

@chro está no local, mas ele não mostra a maneira correta de fazer isso recursivamente. Aqui está a solução:

class Fib {
    static int count;

    public static void main(String[] args) {
        log(fibWrong(20));  // 6765
        log("Count: " + count); // 21891
        count = 0;
        log(fibRight(20)); // 6765
        log("Count: " + count); // 19
    }

    static long fibRight(long n) {
        return calcFib(n-2, 1, 1);
    }

    static long fibWrong(long n) {
        count++;
        if (n == 0 || n == 1) {
            return n;
        } else if (n < 0) {
            log("Overflow!");
            System.exit(1);
            return n;
        } else {
            return fibWrong(n-1) + fibWrong(n-2);
        }

    }

    static long calcFib(long nth, long prev, long next) {
        count++;
        if (nth-- == 0)
            return next;
        if (prev+next < 0) {
            log("Overflow with " + (nth+1) 
                + " combinations remaining");
            System.exit(1);
        }
        return calcFib(nth, next, prev+next);
    }

    static void log(Object o) {
        System.out.println(o);
    }
}
taylordurden
fonte