Подтвердить что ты не робот

Как "работает" рекурсивная функция Фибоначчи?

Я новичок в Javascript и читаю на нем, когда я пришел к главе, в которой описана функция рекурсии. Он использовал примерную функцию для поиска n-го числа последовательности Фибоначчи. Код выглядит следующим образом:

function fibonacci(n) {
   if (n < 2){
     return 1;
   }else{
     return fibonacci(n-2) + fibonacci(n-1);
   }
}

console.log(fibonacci(7));
//Returns 21

У меня возникли проблемы с пониманием того, что делает эта функция. Может кто-нибудь объяснить, что здесь происходит? Я застрял на 5-й строке, где функция вызывает себя. Что здесь происходит?

4b9b3361

ОТВЕТЫ

Ответ 1

Вы определяете функцию в терминах самой себя. В общем, fibonnaci(n) = fibonnaci(n - 2) + fibonnaci(n - 1). Мы просто представляем это отношение в коде. Итак, для fibonnaci(7) можно наблюдать:

  • fibonacci(7) равен fibonacci(6) + fibonacci(5)
  • fibonacci(6) равен fibonacci(5) + fibonacci(4)
  • fibonacci(5) равен fibonacci(4) + fibonacci(3)
  • fibonacci(4) равно fibonacci(3) + fibonacci(2)
  • fibonacci(3) равен fibonacci(2) + fibonacci(1)
  • fibonacci(2) равен fibonacci(1) + fibonacci(0)
  • fibonacci(1) равен 1
  • fibonacci(0) равен 1

Теперь у нас есть все части, необходимые для оценки fibonacci(7), что было нашей первоначальной целью. Обратите внимание, что основной случай - return 1, когда n < 2 - делает это возможным. Это то, что останавливает рекурсию, поэтому мы можем начать процесс разворачивания стека и суммировать значения, возвращаемые нами на каждом шаге. Без этого шага мы продолжаем называть fibonacci меньшими и меньшими значениями вплоть до окончательной сбой программы.

Это может помочь добавить несколько операторов ведения журнала, которые иллюстрируют это:

function fibonacci(n, c) {
    var indent = "";
    for (var i = 0; i < c; i++) {
        indent += " ";
    }
    console.log(indent + "fibonacci(" + n + ")");
    if (n < 2) {
        return 1;
    } else {
        return fibonacci(n - 2, c + 4) + fibonacci(n - 1, c + 4);
    }
}

console.log(fibonacci(7, 0));

Вывод:

fibonacci(7)
    fibonacci(5)
        fibonacci(3)
            fibonacci(1)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
        fibonacci(4)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
    fibonacci(6)
        fibonacci(4)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
        fibonacci(5)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
            fibonacci(4)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
                fibonacci(3)
                    fibonacci(1)
                    fibonacci(2)
                        fibonacci(0)
                        fibonacci(1)

Значения на том же уровне отступов суммируются для получения результата для предыдущего уровня отступов.

Ответ 2

Здесь есть много хороших ответов, но я сделал эту диаграмму, которая помогает лучше объяснить результат функции. Единственными значениями, которые когда-либо будут возвращены, являются 1 или 0 (ваш пример возвращает 1 для n < 2, но вместо этого должен возвращать n).

Это означает, что каждый рекурсивный вызов в конечном итоге приведет к возврату либо 0, либо 1. В конечном итоге они "кэшируются" в стеке и "переносятся" в исходный вызов и добавляются вместе.

Итак, если бы вы рисовали эту же диаграмму для каждого значения "n", вы могли бы вручную найти ответ.

Эта диаграмма примерно иллюстрирует, как каждая функция возвращается для fib (5).

! [Диаграмма дерева диаграммы Fibonacci

Здесь показан поток управления, то есть порядок выполнения для функций. Помните, что код всегда выполняется слева- > справа и сверху- > снизу. Поэтому всякий раз, когда вызывается новая функция, она приостанавливается, а затем происходит следующий вызов.

Ниже показан фактический поток управления на основе вашего исходного сообщения. Обратите внимание, что базовое условие if (n <= 0) {return 0} else if (n <= 2) {return 1;} для упрощения:

1. fib(5) {
    return fib(4) + fib(3);
2.   fib(4) {
      return fib(3) + fib(2);
3.     fib(3) {
        return fib(2) + fib(1);
4.       fib(2) {
A=        return 1;
         };
5.       fib(1) {
B=        return 1;
         };
C=      return 2; // (1 + 1)
       };
6.     fib(2) {
D=      return 1;
       };
E=    return 3; // (2 + 1)
     };
7.   fib(3) {
      return fib(2) + fib(1);
8.     fib(2) {
F=      return 1;
       };
9.     fib(1) {
G=      return 1;
       };
H=    return 2; // (1 + 1)
     };
I=  return 5; // (3 + 2)
   };

Ответ 3

Шаг 1) Когда fibonacci(7) вызывается, представьте себе следующее (обратите внимание, как я изменил все n на 7):

function fibonacci(7) {
    if (7 < 2){
        return 1;
    }else{
        return fibonacci(7-2) + fibonacci(7-1);
    }
}

Шаг 2) Так как (7 < 2), очевидно, ложно, мы переходим к fibonacci(7-2) + fibonacci(7-1);, который переводит на fibonacci(5) + fibonacci(6); Так как fibonacci(5) на первом месте, которое вызывается (меняет n на 5 в этот раз):

function fibonacci(5) {
    if (5 < 2){
        return 1;
    }else{
        return fibonacci(5-2) + fibonacci(5-1);
    }
}

Шаг 3) И также вызывается вызов fibonacci(6), так что произошло для вызова всех fibonacci 2 новых fibonacci.

Визуализация:

      fibonacci(7)
      ____|_____
     |          |
fibonacci(5)  fibonacci(6)
____|____     ____|_____
|        |    |         |
fib(3)  fib(4) fib(4)   fib(5)

Посмотрите, как это происходит? Когда он остановится? Когда n становится меньше 2, вот почему у вас if (n < 2). В этот момент ветвление прекращается, и все складывается вместе.

Ответ 4

Надеюсь, следующее поможет. Призвание:

fibonacci(3)

перейдет к строке 5 и выполните:

return fibonacci(1) + fibonacci(2);

первое выражение снова вызывает функцию и возвращает 1 (поскольку n < 2).

Вторая снова вызывает функцию, попадает в 5-ю строку и делает:.

return fibonacci(0) + fibonacci(1);

оба выражения возвращают 1 (поскольку n < 2 для обоих), поэтому этот вызов функции возвращает 2.

Итак, ответ 1 + 2, который равен 3.

Ответ 5

Я думаю, что эти две функции дали мне более ясное объяснение рекурсии (из этого сообщения ):

function fibDriver(n) {
  return n === 0 ? 0 : fib(0, 1, n);
}

function fib(a, b, n) {
  return n === 1 ? b : fib(b, a + b, n-1);
}

Ответ 6

Для вычисления n-го числа фибоначчи отношение F (n) = F (n-2) + F (n-1).

Если мы реализуем отношение в коде, то для n-го числа мы вычисляем (n-2) -й и (n-1) -й числа, используя тот же метод.

Каждое последующее число представляет собой сумму двух предыдущих чисел. Таким образом, седьмое число представляет собой сумму шестого и пятого чисел. В более общем случае n-е число представляет собой сумму n-2 и n-1, если n > 2. Поскольку рекурсивным функциям требуется условие остановки, чтобы остановить рекурсию, здесь n < 2 является условием.

f (7) = F (6) + F (5);

в свою очередь, F (6) = F (5) + F (4)

F (5) = F (4) + F (3)... он продолжается до тех пор, пока n < 2

F (1) возвращает 1

Ответ 7

Функция вызывает себя. Это просто определение рекурсивной функции. В 5-й строке это передача выполнения самому себе путем передачи параметров, которые приведут к значению.

Чтобы гарантировать, что рекурсивная функция не превратится в бесконечный цикл, должно быть какое-то условие, которое не вызывает себя. Цель вашего кода в вопросе - выполнить вычисления последовательности фибоначчи.

Ответ 8

 
   /*
* Steps Fibonacci recursion
* 1) 3 gets passed. (3 is printed to the screen during this call)
* 2) Fibonacci A gets decrements by 2 and recursion happens passing 1 as a param. (1 is printed to the screen during this call)
* 3) Fibonacci A hits the base case returning 1 and it "unwinds". (No recursion here)
* 4) Fibonacci B gets called, decrementing the previous value of n (3 was the previous value of n before A made the returning call) to 2. (2 is printed to the screen during this call)
* 5) Fibonacci A is called again subtracting 2 from n (2-2=0) and passes 0 as a param. (1 is printed to the screen during this call since it converted from 0)
* 6) Fibonacci A hits the base case and "unwinds" (no recursion here)
* 7) Fibonacci B is called subtracting 1 from 2 (2 was the previous value of n before A made the returning call) and passes 1 as a param. (1 is printed to the screen during this call)
* 7) Fibonacci B now hits the base case, returning 1 and "unwinds" (no recursion here)
* 8) Fibonacci B retraces it steps back through All previous fucntion calls and values of n (n=2 in our case) and adds [them] to the copy of n=1 stored in its local scope
* 9) Once Fibonacci B completes the "unwinding" process, it returns the calculated value to the original caller (no recursion here)

 Note* 
    Each instance of Fibonacci recursion creates its own scope and stores the returned value in a copy of n (in our case 1). 
    As it the function "unwinds" it executes subsequent code that receive the value of n at that time. (all functions that call other functions "unwind" back through previous calls once they return)

    In the last call of our Fibonacci example, Fibonacci B receives the value of n=2 as Fibonaccci A "unwinds" since that was the last value before it made the returning call.
    Once Fibonacci B reached the base case and "unwound", it retraced its steps back through all previous values of n (in our case just n=2) and added [them] to its local copy of n=1.

* The result when passing the number 3 is: 
                3
                 1
                 2
                  1
                  1
            (3)
*/

var div = document.getElementById('fib');

function fib( n, c ) {
  var indent = "";
  for (var i = 0; i < c; i++) {
    indent += " ";
}
  var v = n===0 ? 1 : n
  var el = document.createElement('div'),
  text = indent + "fibonacci(" + v + ")";
  el.innerHTML = text;
  div.appendChild(el);
  if(n<2){
     return 1;
  } 
  return fib(n-2, c + 4)  + fib(n-1, c + 4);

}

Ответ 9

Алгоритм Фибоначчи с рекурсивной функцией на основе ES6

const fibonacci = ( n, k = 1, fib2 = 0, fib1 = 1 ) => {
  return k === n ? 
    (() => { return fib1; })() 
    : 
    (() => {
      k++;
      return fibonacci(n, k, fib1, fib1 + fib2);
    })();  
}
console.info(' fibonacci ' + 11 + ' = ' + fibonacci(11));

Ответ 10

смотри, выдумка

t (n) = t (n - 1) + n;

если n = 0, то 1

так что давайте посмотрим, как работает рекурсия, я просто заменяю n в t(n) на n-1 и так далее. это выглядит:

t (n-1) = t (n - 2) + n + 1;

t (n-1) = t (n-3) + n + 1 + n;

t (n-1) = t (n - 4) + n + 1 + n + 2 + n;

,

,

,

t (n) = t (nk) +... + (nk-3) + (nk-2) + (nk-1) + n;

мы знаем, что если t(0)=(nk) равно 1 то nk=0 поэтому n=k заменим k на n:

t (n) = t (nn) +... + (n-n + 3) + (n-n + 2) + (n-n + 1) + n;

если мы опускаем nn то:

t (n) = t (0) +... + 3 + 2 + 1 + (n-1) +n;

поэтому 3+2+1+(n-1)+n - натуральное число. рассчитывается как Σ3+2+1+(n-1)+n = n(n+1)/2 => n²+n/2

результат для fib: O(1 + n²) = O(n²)

Это лучший способ понять рекурсивное отношение