последовательность Фибоначчи

Question

последовательность Фибоначчи

Рейтинг: 2Ответов: 2Опубликовано: 19.04.2015

public class Test {

private static int f(int index) {
    if (index <= 0) {
        return 0;
    } else if (index == 1) {
        return 1;
    } else if (index == 2) {
        return 1;
    } else {
        return f(index - 1) + f(index - 2);
    }
}

public static void main(String[] args) {
    int n = 11;
    for (int i = 1; i <= n; i++) {
        System.out.print(f(i) + " ");
    }
}
}

Ребята, подскажите, пожалуйста, не поминаю как работает часть кода

else { return f(index - 1) + f(index - 2);}

т.е когда n=5, то должно быть (5-1)+(5-2)?? В таком случае ответ не совпадает. Как это работает?

java числа-фибоначчи

Источник: Stack Overflow на русском

Answer 1

▲ 5

Последовательность Фибоначчи:

1 1 2 3 5 8 ...

На пятой позиции (n = 5) у нас находится число 5. Значит f(5) должно вернуть ответ 5, если работает правильно.

Давайте посмотрим по-шагам:

f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)

// После подстановки f(4) и f(3):
f(4) = (f(2) + f(1)) + f(2)
f(5) = [(f(2) + f(1)) + f(2)] + [f(2) + f(1)]

// Так как f(2) = 1 и f(1) = 1, то
f(5) = 1 + 1 + 1 + 1 + 1 = 5

Всё совпадает! =)

Рекурсивные функции играют важную роль в теории алгоритмов.

Answer 2

▲ 4

        return f(index - 1) + f(index - 2);

Этой строчкой метод f(int index) вызывает сам себя, вычисляя промежуточные результаты, после этого возвращает сумму. Такой подход к решению задачи называется рекурсивным. Подробнее о рекурсиях: http://acmp.ru/article.asp?id_sec=1&id_text=1333

последовательность Фибоначчи

Ответы