Java-рекурсивная последовательность Фибоначчи

156

Пожалуйста, объясните этот простой код:

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

Я запутался с последней строкой, особенно потому, что, например, если n = 5, то будут вызваны fibonacci (4) + fibonacci (3) и так далее, но я не понимаю, как этот алгоритм вычисляет значение по индексу 5 этим метод. Пожалуйста, объясните с большим количеством деталей!

Индекс Хакер
источник
8
Обратите внимание, что это рекурсивно и выполняется в экспоненциальном времени. Это неэффективно для больших значений N. Используя итеративный подход, я смог вычислить первые 10000 чисел в последовательности. Их можно найти здесь - goo.gl/hnbF5
Адам
@AdamFisher: Не могли бы вы поделиться кодом, который вы использовали для последовательного вычисления 10 000 чисел? Я на самом деле любопытно узнать это.
Шумаил
4
@AdamFisher Ссылка, на которую вы ссылались, устарела.
iRuth
2
Это видео объяснит, как понимать рекурсивную функцию за 10 минут youtube.com/watch?v=t4MSwiqfLaY
Чатура Палихаккара
2
Существует также итеративный подход, который может быть менее сложным для вас. Отличная статья о рекурсивном и итеративном коде здесь - codeflex.co/java-get-fibonacci-number-by-index
user5495300

Ответы:

165

В последовательности Фибоначчи каждый элемент является суммой двух предыдущих. Итак, вы написали рекурсивный алгоритм.

Так,

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

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

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

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

Теперь вы уже знаете fibonacci(1)==1 and fibonacci(0) == 0. Таким образом, вы можете впоследствии рассчитать другие значения.

Сейчас,

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

И из последовательности Фибоначчи 0,1,1,2,3,5,8,13,21....мы видим, что для 5th elementпоследовательности Фибоначчи возвращается 5.

Смотрите здесь для обучения рекурсии .

RanRag
источник
он будет работать, но не оптимизирован до тех пор, пока не будет оптимизирован. Пожалуйста, посмотрите на мой ответ. Дайте мне знать в случае предложений / комментариев
M Sach
52

Есть 2 проблемы с вашим кодом:

  1. Результат сохраняется в int, который может обрабатывать только первые 48 чисел Фибоначчи, после этого целое заполнение минус бит и результат неверный.
  2. Но вы никогда не сможете запустить Фибоначчи (50).
    Код
    fibonacci(n - 1) + fibonacci(n - 2)
    очень неправильный.
    Проблема в том, что он вызывает Фибоначчи не в 50 раз, а гораздо больше.
    Сначала он называет Фибоначчи (49) + Фибоначчи (48),
    затем Фибоначчи (48) + Фибоначчи (47) и Фибоначчи (47) + Фибоначчи (46)
    Каждый раз, когда он становится Фибоначчи (n) хуже, поэтому сложность экспоненциальная. введите описание изображения здесь

Подход к нерекурсивному коду:

 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
источник
4
Хотя некоторые другие ответы объясняют рекурсию более четко, это, вероятно, наиболее актуальный ответ на более глубоком уровне.
Hal50000
1
Что означает «заполнить минус бит»?
Ричард
1
@ Richard, речь идет о том, как хранится целое число. Когда int достигнет 2 ^ 31-1, следующий бит будет о знаке, поэтому число станет отрицательным.
Chro
Гораздо быстрее, чем рекурсивный. Единственная оговорка в том, что он не будет работать при n = 1.
Требуется
1
«Каждый раз, когда это становилось на 2 ^ n хуже», на самом деле количество полных вызовов функций 2*fibonacci(n+1)-1увеличивается, поэтому оно растет с той же сложностью, что и сами числа
Фибоначчи
37

В псевдокоде, где n = 5, имеет место следующее:

Фибоначчи (4) + Фибоначчи (3)

Это разбивается на:

(Фибоначчи (3) + Фибоначчи (2)) + (Фибоначчи (2) + Фибоначчи (1))

Это разбивается на:

(((Фибоначчи (2) + Фибоначчи (1)) + (((Фибоначчи (1) + Фибоначчи (0))) + (((Фибоначчи (1) + Фибоначчи (0)) + 1))

Это разбивается на:

((((Фибоначчи (1) + Фибоначчи (0)) + 1) + ((1 + 0)) + ((1 + 0) + 1))

Это разбивается на:

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

В результате: 5

Учитывая, что последовательность Фибоначчи равна 1 1 2 3 5 8 ... , 5-й элемент равен 5. Вы можете использовать ту же методологию, чтобы выяснить другие итерации.

Дэн Хардикер
источник
Я думаю, что этот ответ объясняет вопросы наилучшим образом. Действительно просто
Амит
Это аккуратно. Объясняет как значение в n-м семестре, так и ряд, за которым он следует.
запятой
12

Иногда рекурсию трудно понять. Просто оцените это на небольшом листе бумаги:

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

Я не уверен, как Java на самом деле оценивает это, но результат будет таким же.

Тим
источник
во второй строке откуда берутся 1 и 0 в конце?
Pocockn
1
@pocockn fib (2) = fib (1) + fib (0)
тим
Таким образом, у вас есть fib (4), поэтому n-1 и n-2 будут fib (3) + fib (2), затем вы снова делаете n-1 и n-2, и вы получаете -> fib (2) + fib (1). ), откуда у вас + fib (1) + fib (0)? Добавлено в конец
pocockn
@pocockn fib (2) + fib (1) из fib (3), fib (1) + fib (0) из fib (2)
Тим
12

Вы также можете упростить свою функцию следующим образом:

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

    return fibonacci(n - 1) + fibonacci(n - 2);
}
Отавио Феррейра
источник
Чем это отличается от этого или этого или этого ответа?
Тунаки
6
Это просто короче и проще для чтения, какие алгоритмы всегда должны быть =)
Отавио Феррейра
@OtavioFerreira единственный ответ, который сумел решить мою проблему, хорошая работа
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)

Важно отметить, что этот алгоритм является экспоненциальным, поскольку он не хранит результат предыдущих вычисленных чисел. например, F (n-3) вызывается 3 раза.

Для более подробной информации обратитесь к алгоритму dasgupta глава 0.2

Амандип Камбой
источник
Существует методология программирования, с помощью которой мы можем избежать вычисления F (n) для одного и того же n снова и снова, используя динамическое программирование
Amit_Hora
8

Большинство ответов хороши и объясняют, как работает рекурсия в Фибоначчи.

Вот анализ трех методов, включая рекурсию:

  1. Для петли
  2. Рекурсия
  3. мемоизации

Вот мой код для проверки всех трех:

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

}

Вот результаты:

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

Следовательно, мы видим, что памятование - лучшее время и для циклических совпадений.

Но рекурсия длится дольше, и, возможно, вам следует избегать в реальной жизни. Также, если вы используете рекурсию, убедитесь, что вы оптимизируете решение.

Притам Банерджи
источник
1
«Здесь мы видим, что цикл - лучшее время»; «Время цикла: 347688»; «Время памятки: 327031»; 347688> 327031.
AjahnCharles
@CodeConfident Да, я только что увидел эту ошибку сегодня и собирался ее исправить. В любом случае спасибо :).
Притам Банерджи
7

Это лучшее видео, которое я нашел, которое полностью объясняет рекурсию и последовательность Фибоначчи в Java.

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

Это его код последовательности, и его объяснение лучше, чем я когда-либо пытался его напечатать.

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
источник
5

Для рекурсивного решения Фибоначчи важно сохранить вывод меньших чисел Фибоначчи, извлекая при этом значение большего числа. Это называется «памятка».

Вот код, который использует запоминание меньших значений Фибоначчи при получении большего числа Фибоначчи . Этот код эффективен и не выполняет несколько запросов одной и той же функции.

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;
    }
  }
}
Амарджит Датта
источник
4

в последовательности Фибоначчи первые два элемента равны 0 и 1, каждый другой элемент является суммой двух предыдущих элементов. то есть:
0 1 1 2 3 5 8 ...

таким образом, 5-й элемент - это сумма 4-го и 3-го элементов.

YuriB
источник
4

Майкл Гудрич и др. Предлагают действительно умный алгоритм в структурах данных и алгоритмах на Java для рекурсивного решения фибоначчи за линейное время, возвращая массив [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;
    }
}

Это дает fib (n) = fibGood (n) [0].

Рей
источник
4

Вот решение 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);
}

Формула числа Фибоначчи Бине используется для реализации выше. Для больших входов longможно заменить на BigDecimal.

Samir
источник
3

Последовательность Фиббоначи - это последовательность, которая суммирует результат числа при добавлении к предыдущему результату, начинающемуся с 1.

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

Как только мы поймем, что такое Fibbonacci, мы можем начать разбивать код.

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

Первый if statment проверяет базовый случай, где цикл может разорваться. Оператор else if ниже делает то же самое, но его можно переписать так ...

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

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

Теперь, когда базовый случай установлен, мы должны понять стек вызовов. Ваш первый вызов «fibonacci» будет последним, который разрешит стек (последовательность вызовов), поскольку они разрешаются в обратном порядке, из которого они были вызваны. Сначала вызывается последний вызываемый метод, затем последний, вызываемый перед этим, и так далее ...

Таким образом, все вызовы выполняются в первую очередь, прежде чем что-либо «рассчитывается» с этими результатами. При вводе 8 мы ожидаем выход 21 (см. Таблицу выше).

Фибоначчи (n - 1) продолжают вызывать до тех пор, пока они не достигнут базового случая, затем Фибоначчи (n - 2) вызывают до тех пор, пока он не достигнет базового случая. Когда стек начнет суммировать результат в обратном порядке, результат будет примерно таким ...

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

Они продолжают пузыриться (разрешаться в обратном направлении) до тех пор, пока правильная сумма не будет возвращена первому вызову в стеке, и вот как вы получите свой ответ.

Сказав это, этот алгоритм очень неэффективен, потому что он вычисляет один и тот же результат для каждой ветви, на которую разбивается код. Гораздо лучший подход - это подход «снизу вверх», где не требуется Memoization (кэширование) или рекурсия (глубокий стек вызовов).

Вот так...

        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;
        }
Джеффри Феррейрас
источник
2

Большинство предлагаемых здесь решений работают в O (2 ^ n) сложности. Пересчет идентичных узлов в рекурсивном дереве неэффективен и тратит впустую циклы ЦП.

Мы можем использовать памятку, чтобы заставить функцию Фибоначчи запускаться за время 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];
}

Если мы пойдем по пути динамического программирования снизу вверх, приведенный ниже код достаточно прост для вычисления Фибоначчи:

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
источник
2

Почему этот ответ отличается

Любой другой ответ либо:

  • Печатает вместо возврата
  • Делает 2 рекурсивных вызова за одну итерацию
  • Игнорирует вопрос с помощью циклов

(в сторону: ни один из них на самом деле не эффективен; используйте формулу Бине для прямого вычисления n- го члена)

Хвост Рекурсивный Фиб

Вот рекурсивный подход, который позволяет избежать двухрекурсивного вызова, передавая как предыдущий, так и предыдущий ответ.

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
источник
1

Это базовая последовательность, которая отображает или получает вывод 1 1 2 3 5 8, это последовательность, в которой сумма предыдущего числа, текущее число будет отображаться следующим.

Попробуйте посмотреть ссылку ниже Java Рекурсивная последовательность Фибоначчи Учебник

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

Нажмите здесь, чтобы посмотреть Java Рекурсивное руководство по последовательности Фибоначчи для кормления ложкой

Джеймелсон Галанг
источник
Ему нужно было понять, как работает код и почему он написан так, как написано.
Адарш
Я думаю, что я упоминаю в своем первом предложении, как это работает? я пишу код, чтобы сделать его более простым. кстати, извините.
Джеймелсон Галанг
Ничего плохого в вашем коде. Только парень хотел понять, как работает этот код. Проверьте ответ по RanRag. Что-то в этом роде :)
Adarsh
ааа, извините, я новичок здесь в stackoverflow. просто хочу помочь ^ _ ^
Джеймелсон Галанг
1

Я думаю, что это простой способ:

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
источник
1

Ответ RanRag (принятый) будет работать нормально, но это не оптимизированное решение до тех пор, пока оно не будет запомнено, как объяснено в ответе Анила.

Для рекурсивного подхода, описанного ниже, вызовы методов TestFibonacciминимальны

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

}
М Сач
источник
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
источник
1

Используя внутренний ConcurrentHashMap, который теоретически может позволить этой рекурсивной реализации правильно работать в многопоточной среде, я реализовал функцию fib, которая использует как BigInteger, так и Recursion. Требуется около 53 мс, чтобы вычислить первые 100 чисел 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)));
    }
}

Тестовый код:

@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));
}
и вывод из теста:
    ,
    ,
    ,
    ,
    ,
    FIB 93 составляет 12200160415121876738
    FIB 94 - 19740274219868223167
    FIB 95 составляет 31940434634990099905
    FIB 96 составляет 51680708854858323072
    ФИБ 97 составляет 83621143489848422977
    FIB 98 составляет 135301852344706746049
    FIB 99 составляет 218922995834555169026
    FIB 100 - 354224848179261915075
    истекшее: 58,0
Джордж Кьюрингтон
источник
1

Вот одна строка фебоначчи рекурсивная:

public long fib( long n ) {
        return n <= 0 ? 0 : n == 1 ? 1 : fib( n - 1 ) + fib( n - 2 );
}
RonTLV
источник
1

Попробуй это

private static int fibonacci(int n){
    if(n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
Маркус Риттер
источник
0

Просто чтобы дополнить, если вы хотите иметь возможность рассчитывать большие числа, вы должны использовать BigInteger.

Итерационный пример.

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("");
        }
    }
}
Тьяго Зортея
источник
0

http://en.wikipedia.org/wiki/Fibonacci_number более подробно

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

}

Сделать это так просто, как нужно, не нужно использовать цикл while и другой цикл

Викас
источник
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
источник
0

Используйте 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;
}

Преимущество этого решения в том, что его легко читать и понимать, надеясь, что это поможет

Гавриил Коэн
источник
0

Последовательность Fibbonacci - это последовательность, которая суммирует результат числа, которое мы добавили к предыдущему результату, мы должны начать с 1. Я пытался найти решение на основе алгоритма, поэтому я строю рекурсивный код, заметил, что я сохраняю предыдущий номер, и я изменил позицию. Я ищу последовательность Фиббоначи от 1 до 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);
}
Матиас Ставру
источник
-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;
}
Ян Мукуня Дуглас
источник
-1

Простые Фибоначчи

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
источник
2
Добро пожаловать в ТАК. Пока ваш ответ вычисляет последовательность Фибоначчи. Ваш ответ не отвечает ОП, который спросил о рекурсивных функциях.
Джеймс К
-2

@chro находится на месте, но он / она не показывает правильный способ сделать это рекурсивно. Вот решение:

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
источник