Вопрос о функции Фибоначчи

Question

Я вычислял последовательность Фибоначчи и наткнулся на этот код, который я много видел:

    int Fibonacci (int x)
{
    if (x<=1) {
        return 1;
    }
    return Fibonacci (x-1)+Fibonacci (x-2);
}

Что я не понимаю, так это как это работает, особенно возвращаемая часть в конце: она снова вызывает функцию Фибоначчи? Может ли кто-нибудь пройти через эту функцию?

Answer 1

Да, функция вызывает сама. Например,

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

Обратите внимание, что функция Фибоначчи здесь вызывается 9 раз. В общем, наивная рекурсивная функция Фибоначчи имеет экспоненциальное время работы , что обычно является плохой вещью.

Answer 2

Это классический пример рекурсивной функции , функции, которая вызывает сама себя.

Если вы внимательно прочитаете его, вы увидите, что он будет вызывать сам себя, или, recurse , снова и снова, пока не достигнет так называемого базового случая , когда x <= 1 В этот момент он начнет «отслеживать» и суммировать вычисленные значения.

Следующий код четко распечатывает след алгоритма:

public class Test {

    static String indent = "";

    public static int fibonacci(int x) {

        indent += "    ";
        System.out.println(indent + "invoked with " + x);

        if (x <= 1) {

            System.out.println(indent + "x = " + x + ", base case reached.");
            indent = indent.substring(4);

            return 1;
        }

        System.out.println(indent + "Recursing on " + (x-1) + " and " + (x-2));
        int retVal = fibonacci(x-1) + fibonacci(x-2);
        System.out.println(indent + "returning " + retVal);
        indent = indent.substring(4);
        return retVal; 

    }


    public static void main(String... args) {
        System.out.println("Fibonacci of 3: " + fibonacci(3));
    }
}

Вывод следующий:

invoked with 3
Recursing on 2 and 1
    invoked with 2
    Recursing on 1 and 0
        invoked with 1
        x = 1, base case reached.
        invoked with 0
        x = 0, base case reached.
    returning 2
    invoked with 1
    x = 1, base case reached.
returning 3

Fibonacci of 3: 3

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

                               fib 4
               fib 3             +           fib 2
    fib 2        +    fib 1              fib 1 + fib 0
fib 1 + fib 0           1                  1       1
  1       1

При написании рекурсивных функций следует учитывать следующие важные моменты:

1. Позаботьтесь о базовом случае

Что бы произошло, если бы мы забыли if (x<=1) return 1; в приведенном выше примере?

2. Удостоверьтесь, что рекурсивные вызовы как-то уменьшаются по отношению к базовому случаю Что бы произошло, если бы мы случайно изменили алгоритм для возврата fibonacci(x)+fibonacci(x-1);

Answer 3

возврат Фибоначчи (х-1) + Фибоначчи (х-2);

Это ужасно неэффективно. Я предлагаю следующую линейную альтернативу:

unsigned fibonacci(unsigned n, unsigned a, unsigned b, unsigned c)
{
    return (n == 2) ? c : fibonacci(n - 1, b, c, b + c);
}

unsigned fibonacci(unsigned n)
{
    return (n < 2) ? n : fibonacci(n, 0, 1, 1);
}

Последовательность Фибоначчи может быть выражена более кратко на функциональных языках.

fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

> take 12 fibonacci
[0,1,1,2,3,5,8,13,21,34,55,89]

Answer 4

Поскольку ваш вопрос помечен как C ++, я вынужден отметить, что эта функция также может быть реализована во время компиляции в качестве шаблона, если у вас есть переменная времени компиляции для ее использования.

template<int N> struct Fibonacci {
    const static int value = Fibonacci<N - 1>::value + Fibonacci<N - 2>::value;
};
template<> struct Fibonacci<1> {
    const static int value = 1;
}
template<> struct Fibonacci<0> {
    const static int value = 1;
}

Прошло некоторое время с тех пор, как я написал такое, так что это может быть немного, но это должно быть так.

Answer 5

Это классическая функция рекурсии. http://en.wikipedia.org/wiki/Recursive_function должен начать вас. По существу, если x меньше или равно 1, возвращается 1. В противном случае уменьшается x, запуская Фибоначчи на каждом шаге.

Answer 6

Да, функция Фибоначчи вызывается снова, это называется рекурсией.

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

Обратите внимание, что рекурсия сложна, поскольку вы можете бесконечно вызывать одну и ту же функцию и заполнять стек вызовов. Эта ошибка называется «переполнением стека» (вот она!)

Answer 7

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

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

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

Сама рекурсия не ужасна. Фактически, цикл, который я только что описал (и любой цикл), может быть реализован как рекурсивная функция:

int Fibonacci (int x, int a = 1, int p = 0) {
    if ( x == 0 ) return a;
    return Fibonacci( x-1, a+p, a );
} // recursive, but with ideal computational properties

Answer 8

Или, если вы хотите быть быстрее, но использовать больше памяти, используйте это.

int *fib,n;
void fibonaci(int n) //find firs n number fibonaci
{
 fib= new int[n+1];
 fib[1] = fib[2] = 1;
 for(int i = 3;i<=n-2;i++)
     fib[i] = fib[i-1] + fib[i-2];
}

и для n = 10 для примера у вас будет: fib [1] fib [2] fib [3] fib [4] fib [5] fib [6] fib [7] fib [8] fib [9] fib [10] 1 1 2 3 5 8 13 21 34 55``