Объяснение по рекурсии Фибоначчи

Question

Я должен кое-что понять. Кажется, что нет хорошего руководства для объяснения явно. Как выглядит дерево функций?

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

Предполагая, что я Fib(7), я на самом деле понимаю, что это должно выглядеть следующим образом:

Дело в том, что кажется, что дерево, как если fib(7) на самом деле означает fib(6) + fib(5) что должно быть правдой ... Однако, если я понимаю рекурсию, чем fib(7) на самом деле fib(6) + fib(5), но fib(5) еще не сдан с fib(6) теперь называет себя fib(4) + fib(3) и еще раз fib(3) не будет выполнен, так как fib(4) будет называть себя до тех пор, пока он не остановится в состоянии «остановки» ... и чем?

Если fib(7) звонки fib(6) и так далее ..... до fib(1), чем обо всех остальных fib(n-2) функций?

Как он на самом деле возвращает каждый раз результат и говорит мне, что такое значение fib(7)?

Answer 1

хорошо recusion не так легко понять, пока вы не поняли ...

поэтому функция выдумка (7) рассчитывается с Фибо (6) + Фибо (5)

(та же функция вызывается с меньшими значениями, что приводит к вызову функции внутри вызова функции внутри вызова функции)

FIB (6) снова FIB (5) + FIB (4)
и FIB (5) является FIB (4) + FIB (3)

эта цепь продолжается до тех пор, пока достигают Фибо (3) = Фибо (2) + FIB (1) потому fib (1) и fib (2) являются .Это означает, что выдумка (3) имеет значение

теперь вы можете пойти еще один шаг назад и посмотреть на Фибо (4) которая выдумка (3) + Фибо (2) который вычисляет к 2 + 1 который

и на данном этапе мы опять в FIB (5) который FIB (4) + FIB (3) или 3 + 2 или

и в этом стиле вы будете следовать дерево обратно вверх, пока не достигнете Фибо (7) снова, который затем рассчитывает 5 + 8 или , который является правильное значение из седьмой номер строки Фибоначчи

Условие останова должно прекратить вызывать дополнительные функции и начать возвращать действительные значения обратно к функциям, вызывающим функцию.

Надеюсь, это немного поможет.

Answer 2

Он не возвращает значение каждый раз, по крайней мере, не сразу.

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

if (n <= 2) 
{ 
    return 1; 
} 

После того как ваш метод называет себя в последний раз на каждой ветви дерева (когда n <= 2 и метод возвращает 1 вместо вызова себя), он будет раскручивать стек, наконец, оценить все эти вызовы и суммируя возвращаемые значения, возвращая 13 в случае Fib(7).

Answer 3

Позвольте мне объяснить это для 4

//step- 1) you are passing 4 
    static long Fib(4) 
    { //4>2 
     if (n <= 2) 
     { 
      return 1; 
     } 
     return Fib(3)//This will call Fib(3) 
+ Fib(2); 
    } 
    //step-2 
    your n is 3 now 
    static long Fib(3) 
    { //3>2 
     if (n <= 2) 
     { 
      return 1; 
     } 
     return Fib(2)//This will call Fib(2) 
+ Fib(1); 
    } 
    //step-3 
    //your n is 2 now 
    static long Fib(2) 
    { //2=2 
     if (n <= 2) 
     { //here it will return 1 back to step-2 
      return 1; 
     } 
     return Fib(n - 1) + Fib(n - 2); 
    } 
    //step-4 
    static long Fib(3) 
    { 
     if (n <= 2) 
     { 
      return 1; 
     } 
     return Fib(2) 1//we got from step-3 
+ Fib(1)//will call Fib(1) ; 
    } 
    //step-5 
    //your n is 1 
    static long Fib(1) 
    { //1<2 
     if (n <= 2) 
     { //it will return 1 back to step-4 
      return 1; 
     } 
     return Fib(n - 1) + Fib(n - 2); 
    } 
    //step-6 
    static long Fib(3) 
    { 
     if (n <= 2) 
     { 
      return 1; 
     } 
     return Fib(2)//-> 1//we got from step-3 
+ Fib(1)//->1//we got from step-5 ; 
    //(1+1)=2 will be return back to step-1 
    } 
    //step-7 
    static long Fib(4) 
    { 
     if (n <= 2) 
     { 
      return 1; 
     } 
     return Fib(3)//->2//we got it from step-6+ Fib(2)//will call Fib(2); 
    } 
    //step-8 
    static long Fib(2) 
    { //2=2 
     if (n <= 2) 
     { //This will return back to step-7 
      return 1; 
     } 
     return Fib(n - 1) + Fib(n - 2); 
    } 
    //step-9 
    static long Fib(4) 
    { 
     if (n <= 2) 
     { 
      return 1; 
     } 
     return Fib(3)//->2 we already got it from step-6 + Fib(2)//->1// we got it from step-8; 
    //This will return 3(2+1) 
    }