Urutan Fibonacci rekursif Jawa

156

Tolong jelaskan kode sederhana ini:

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

Saya bingung dengan baris terakhir terutama karena jika n = 5 misalnya, maka fibonacci (4) + fibonacci (3) akan dipanggil dan seterusnya, tetapi saya tidak mengerti bagaimana algoritma ini menghitung nilai pada indeks 5 dengan ini metode. Tolong jelaskan dengan banyak detail!

Peretas indeks
sumber
8
Perhatikan bahwa ini adalah rekursif dan berjalan dalam waktu yang eksponensial. Ini tidak efisien untuk nilai-nilai besar dari N. Menggunakan pendekatan berulang saya bisa menghitung 10.000 angka pertama dalam urutan. Mereka dapat ditemukan di sini - goo.gl/hnbF5
Adam
@AdamFisher: Bisakah Anda membagikan kode yang Anda gunakan untuk menghitung 10.000 angka secara berurutan? Saya sebenarnya penasaran untuk mengetahuinya.
Shumail
4
@AdamFisher Tautan yang Anda maksud sudah mati.
iRuth
2
Video ini akan menjelaskan untuk memahami fungsi rekursif dalam 10 menit youtube.com/watch?v=t4MSwiqfLaY
Chathura Palihakkara
2
Ada juga pendekatan berulang yang mungkin tidak terlalu sulit bagi Anda. Artikel hebat tentang Rekursif dan Iteratif dengan kode di sini - codeflex.co/java-get-fibonacci-number-by-index
user5495300

Jawaban:

165

Dalam urutan fibonacci setiap item adalah jumlah dari dua sebelumnya. Jadi, Anda menulis algoritma rekursif.

Begitu,

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

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

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

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

Sekarang kamu sudah tahu fibonacci(1)==1 and fibonacci(0) == 0. Jadi, Anda selanjutnya dapat menghitung nilai lainnya.

Sekarang,

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

Dan dari deret fibonacci 0,1,1,2,3,5,8,13,21....kita dapat melihat bahwa untuk 5th elementderet fibonacci kembali 5.

Lihat di sini untuk Tutorial Rekursi .

RanRag
sumber
itu akan berfungsi tetapi tidak dioptimalkan sampai dan kecuali itu dioptimalkan. Silakan lihat jawaban saya. Beritahu saya jika ada saran / komentar
M Sach
52

Ada 2 masalah dengan kode Anda:

  1. Hasilnya disimpan dalam int yang hanya dapat menangani 48 angka fibonacci pertama, setelah ini integer mengisi minus bit dan hasilnya salah.
  2. Tapi Anda tidak pernah bisa menjalankan fibonacci (50).
    Kode
    fibonacci(n - 1) + fibonacci(n - 2)
    ini sangat salah.
    Masalahnya adalah bahwa ia memanggil fibonacci bukan 50 kali tetapi lebih.
    Pada awalnya ia memanggil Fibre (49) + fibonacci (48),
    Fibre (48) + Fibre (47) + Fibre (47) + Fibre (46)
    Setiap kali menjadi Fibre (n) lebih buruk, jadi kompleksitasnya eksponensial. masukkan deskripsi gambar di sini

Pendekatan kode non-rekursif:

 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
sumber
4
Meskipun beberapa jawaban lain menjelaskan rekursi dengan lebih jelas, ini mungkin jawaban yang paling relevan di tingkat yang lebih dalam.
Hal50000
1
Apa yang dimaksud dengan "integer fill minus bit"?
richard
1
@ Richard, ini tentang bagaimana integer disimpan. Setelah int mencapai 2 ^ 31-1 bit berikutnya adalah tentang tanda, sehingga angkanya menjadi negatif.
chro
Jauh lebih cepat daripada rekursif. Reservasi satu-satunya adalah itu tidak akan berfungsi untuk n = 1. Diperlukan kondisi tambahan
v0rin
1
"Setiap kali menjadi 2 ^ n lebih buruk" sebenarnya jumlah panggilan fungsi total adalah 2*fibonacci(n+1)-1, sehingga ia tumbuh dengan kompleksitas yang sama dengan angka-angka fibonacci itu sendiri, yaitu 1,618 ^ n bukannya 2 ^ n
Aemyl
37

Dalam kode semu, di mana n = 5, berikut ini terjadi:

fibonacci (4) + fibonnacci (3)

Ini dipecah menjadi:

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

Ini dipecah menjadi:

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

Ini dipecah menjadi:

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

Ini dipecah menjadi:

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

Ini menghasilkan: 5

Mengingat urutan fibonnacci adalah 1 1 2 3 5 8 ... , elemen ke-5 adalah 5. Anda dapat menggunakan metodologi yang sama untuk mencari iterasi lain.

Dan Hardiker
sumber
Saya pikir jawaban ini menjelaskan pertanyaan dengan cara terbaik. Sangat sederhana
Amit
Ini rapi. Menjelaskan nilai pada term n dan seri yang diikuti.
Titik koma
12

Rekursi terkadang sulit untuk dipahami. Cukup evaluasi pada selembar kertas untuk sejumlah kecil:

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

Saya tidak yakin bagaimana Java sebenarnya mengevaluasi ini, tetapi hasilnya akan sama.

tim
sumber
pada baris kedua dari mana 1 dan 0 pada akhirnya berasal?
pocockn
1
@pocockn fib (2) = fib (1) + fib (0)
tim
Jadi Anda memiliki fib (4) sehingga n-1 dan n-2 akan menjadi fib (3) + fib (2) maka Anda melakukan n-1 dan n-2 lagi yang Anda dapatkan -> fib (2) + fib (1 ), dari mana Anda mendapatkan + fib (1) + fib (0) dari? Ditambahkan ke akhir
pocockn
@pocockn fib (2) + fib (1) berasal dari fib (3), fib (1) + fib (0) berasal dari fib (2)
tim
12

Anda juga dapat menyederhanakan fungsi Anda, sebagai berikut:

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

    return fibonacci(n - 1) + fibonacci(n - 2);
}
Otavio Ferreira
sumber
Bagaimana ini berbeda dari ini atau ini atau jawaban ini ?
Tunaki
6
Ini hanya lebih pendek dan lebih mudah dibaca, algoritma mana yang harus selalu =)
Otavio Ferreira
@OtavioFerreira satu-satunya jawaban yang berhasil menyelesaikan masalah saya, pekerjaan bagus
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)

Poin penting yang perlu diperhatikan adalah algoritma ini eksponensial karena tidak menyimpan hasil angka yang dihitung sebelumnya. misal F (n-3) disebut 3 kali.

Untuk lebih jelasnya rujuk algoritma oleh dasgupta bab 0.2

Amandeep Kamboj
sumber
Ada metodologi pemrograman yang dengannya kita dapat menghindari penghitungan F (n) untuk n yang sama berulang-ulang menggunakan Pemrograman Dinamis
Amit_Hora
8

Sebagian besar jawabannya baik dan menjelaskan bagaimana rekursi dalam fibonacci bekerja.

Berikut ini adalah analisis pada tiga teknik yang termasuk rekursi juga:

  1. Untuk Loop
  2. Pengulangan
  3. Memoisasi

Ini kode saya untuk menguji ketiganya:

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;
    }

}

Inilah hasilnya:

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

Oleh karena itu kita dapat melihat memoisasi adalah waktu terbaik dan untuk pertandingan loop erat.

Namun rekursi memakan waktu paling lama dan mungkin Anda harus hindari dalam kehidupan nyata. Juga jika Anda menggunakan rekursi, pastikan Anda mengoptimalkan solusinya.

Pritam Banerjee
sumber
1
"Di sini kita dapat melihat untuk loop adalah waktu terbaik yang bijaksana"; "Untuk Loop Time: 347688"; "Waktu Memoisasi: 327031"; 347688> 327031.
AjahnCharles
@ CodeConfident Ya, saya baru saja melihat kesalahan itu hari ini dan akan memperbaikinya. Terima kasih ya :).
Pritam Banerjee
7

Ini adalah video terbaik yang saya temukan yang sepenuhnya menjelaskan rekursi dan deret Fibonacci di Jawa.

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

Ini adalah kode untuk urutan dan penjelasannya lebih baik daripada yang bisa saya lakukan untuk mencoba mengetiknya.

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;
    }
pengguna2718538
sumber
5

Untuk solusi recursive fibonacci, penting untuk menyimpan output dari angka fibonacci yang lebih kecil, sambil mengambil nilai dari angka yang lebih besar. Ini disebut "Memoizing".

Berikut ini adalah kode yang menggunakan memoizing nilai fibonacci yang lebih kecil, sambil mengambil nomor fibonacci yang lebih besar. Kode ini efisien dan tidak membuat banyak permintaan dengan fungsi yang sama.

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
sumber
4

dalam urutan fibonacci , dua item pertama adalah 0 dan 1, setiap item lainnya adalah jumlah dari dua item sebelumnya. yaitu:
0 1 1 2 3 5 8 ...

jadi item ke-5 adalah jumlah item ke-4 dan ke-3.

yurib
sumber
4

Michael Goodrich et al memberikan algoritma yang sangat pintar dalam Struktur Data dan Algoritma di Jawa, untuk memecahkan fibonacci secara waktu linear secara linier dengan mengembalikan array [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;
    }
}

Ini menghasilkan fib (n) = fibGood (n) [0].

Rae
sumber
4

Inilah solusi 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);
}

Formula nomor Fibonacci Binet digunakan untuk implementasi di atas. Untuk input besar longbisa diganti dengan BigDecimal.

Samir
sumber
3

Urutan Fibbonacci adalah urutan yang menjumlahkan hasil angka ketika ditambahkan ke hasil sebelumnya dimulai dengan 1.

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

Setelah kita memahami apa itu Fibbonacci, kita dapat mulai memecah kode.

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

Statment if pertama memeriksa case dasar, di mana loop dapat keluar. Lain lagi jika pernyataan di bawah ini melakukan hal yang sama, tetapi bisa ditulis ulang seperti itu ...

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

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

Sekarang setelah kasus dasar ditetapkan, kita harus memahami tumpukan panggilan. Panggilan pertama Anda ke "fibonacci" akan menjadi yang terakhir untuk diselesaikan pada tumpukan (urutan panggilan) karena mereka menyelesaikan dalam urutan terbalik dari mana mereka dipanggil. Metode terakhir yang disebut resolves terlebih dahulu, lalu yang terakhir dipanggil sebelum itu dan seterusnya ...

Jadi, semua panggilan dilakukan terlebih dahulu sebelum semuanya "dihitung" dengan hasil tersebut. Dengan input 8, kami mengharapkan output 21 (lihat tabel di atas).

fibonacci (n - 1) terus dipanggil hingga mencapai base case, kemudian fibonacci (n - 2) dipanggil hingga mencapai base case. Ketika tumpukan mulai menjumlahkan hasil dalam urutan terbalik, hasilnya akan seperti ...

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).

Mereka terus menggelegak (menyelesaikan mundur) hingga jumlah yang benar dikembalikan ke panggilan pertama di tumpukan dan itulah cara Anda mendapatkan jawaban Anda.

Karena itu, algoritma ini sangat tidak efisien karena menghitung hasil yang sama untuk setiap cabang yang dipecah dengan kode. Pendekatan yang jauh lebih baik adalah pendekatan "bottom-up" di mana tidak diperlukan Memoisasi (caching) atau rekursi (tumpukan panggilan yang mendalam).

Seperti ...

        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
sumber
2

Sebagian besar solusi yang ditawarkan di sini berjalan dalam kompleksitas O (2 ^ n). Menghitung ulang node identik dalam pohon rekursif tidak efisien dan membuang siklus CPU.

Kita dapat menggunakan memoisasi untuk membuat fungsi fibonacci berjalan dalam waktu O (n)

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];
}

Jika kita mengikuti rute Bottom-Up Dynamic Programming, kode di bawah ini cukup sederhana untuk menghitung 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
sumber
2

Mengapa jawaban ini berbeda

Setiap jawaban lainnya:

  • Mencetak alih-alih pengembalian
  • Melakukan 2 panggilan rekursif per iterasi
  • Abaikan pertanyaan dengan menggunakan loop

(selain: tidak ada yang benar-benar efisien; gunakan rumus Binet untuk langsung menghitung angka ke- n istilah )

Tail Recursive Fib

Berikut ini adalah pendekatan rekursif yang menghindari panggilan rekursif ganda dengan melewati kedua jawaban sebelumnya DAN yang sebelumnya.

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
sumber
1

Ini adalah urutan dasar yang menampilkan atau mendapatkan output 1 1 2 3 5 8 itu adalah urutan bahwa jumlah dari angka sebelumnya, angka saat ini akan ditampilkan berikutnya.

Cobalah untuk menonton tautan di bawah Tutorial urutan Fibonacci Recursive Java

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

Klik Di Sini Tonton Tutorial Java Recursive Fibonacci sequence untuk sendok makan

Jaymelson Galang
sumber
Apa yang perlu dia pahami adalah bagaimana kode itu bekerja dan mengapa kode itu ditulis sebagaimana mereka ditulis.
Adarsh
Saya pikir saya menyebutkan dalam kalimat pertama saya cara kerjanya? saya menulis kode untuk membuatnya lebih sederhana. btw, maaf
Jaymelson Galang
Tidak ada yang salah dengan kode Anda. Hanya pria yang ingin memahami bagaimana kode itu bekerja. Periksa jawabannya oleh RanRag. Semacam itu :)
Adarsh
ahh ok, maaf saya pemula di sini di stackoverflow. hanya ingin membantu ^ _ ^
Jaymelson Galang
1

Saya pikir ini adalah cara sederhana:

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);
        }
    }
}
pengguna3787713
sumber
1

Jawaban RanRag (diterima) akan berfungsi dengan baik tetapi itu bukan solusi yang dioptimalkan sampai dan kecuali dihafal seperti yang dijelaskan dalam jawaban Anil.

Untuk pertimbangan rekursif di bawah pendekatan, pemanggilan metode TestFibonacciminimal

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
sumber
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
sumber
1

Dengan menggunakan ConcurrentHashMap internal yang secara teoritis memungkinkan implementasi rekursif ini beroperasi dengan baik di lingkungan multithreaded, saya telah mengimplementasikan fungsi fib yang menggunakan BigInteger dan Rekursi. Butuh sekitar 53ms untuk menghitung 100 bilangan fib pertama.

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)));
    }
}

Kode tes adalah:

@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));
}
dan output dari tes ini adalah:
    .
    .
    .
    .
    .
    fib 93 adalah 12200160415121876738
    fib 94 adalah 19740274219868223167
    Fib 95 adalah 31940434634990099905
    Fib 96 adalah 51680708854858323072
    fib dari 97 adalah 83621143489848422977
    Fib 98 adalah 135301852344706746049
    Fib 99 adalah 218922995834555169026
    Fib 100 adalah 354224848179261915075
    berlalu: 58,0
George Curington
sumber
1

Berikut ini adalah satu baris febonacci rekursif:

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

Coba ini

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

Sebagai pelengkap, jika Anda ingin dapat menghitung angka yang lebih besar, Anda harus menggunakan BigInteger.

Contoh berulang.

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
sumber
0

http://en.wikipedia.org/wiki/Fibonacci_number lebih terinci

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));
    }

}

Jadikan sesederhana yang diperlukan tidak perlu menggunakan while dan loop lainnya

vikas
sumber
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;
    }
}
pengguna3231661
sumber
0

Gunakan 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;
}

Keuntungan dari solusi ini adalah mudahnya membaca kode dan memahaminya, berharap itu membantu

Gavriel Cohen
sumber
0

Urutan Fibbonacci adalah salah satu yang merangkum hasil angka kemudian kita tambahkan ke hasil sebelumnya, kita harus mulai dari 1. Saya mencoba mencari solusi berdasarkan algoritma, jadi saya membangun kode rekursif, perhatikan bahwa saya menyimpan nomor sebelumnya dan saya mengubah posisi. Saya mencari urutan Fibbonacci dari 1 hingga 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
sumber
-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
sumber
-1

Fibonacci Sederhana

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
sumber
2
Selamat datang di SO. Sementara jawaban Anda menghitung urutan Fibonacci. Jawaban Anda tidak menjawab OP, yang bertanya tentang fungsi rekursif.
James K
-2

@ chro sangat tepat, tetapi dia tidak menunjukkan cara yang benar untuk melakukan ini secara rekursif. Inilah solusinya:

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
sumber