Кто-нибудь может объяснить, как работает этот блок кода? - PullRequest
Новая
       19

Кто-нибудь может объяснить, как работает этот блок кода?

0 голосов
/ 28 апреля 2020 
function f(num) {
    if (num<1) {
        return 1;
    }
    return f(num-1) + f(num-2);
}

f(5); // 13

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

Ответы [ 3 ]

2 голосов
/ 28 апреля 2020

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

1.) У рекурсивного алгоритма должен быть базовый случай.

2.) Рекурсивный алгоритм должен изменить свое состояние и перейти к базовому случаю.

3.) Рекурсивный алгоритм должен вызывать себя рекурсивно.

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

function f(num) {
    if (num<=1) { // (1) Base case condition 
        return 1; // (2.b) moving forward once the base case is true
    }
     // (3) the function calling itself
    // also (2.a) changed state - (i.e., the param value is being decremented or "unwound" with each pass of recursion (i.e., method call)
    return f(num-1) + f(num-2); 
}
f(5); // Fn = Fn-1 + Fn-2 (Fibonacci Number Series)

Ресурсы:

1 голос
/ 28 апреля 2020

Это рекурсия. Это серия Фибоначчи. Пройдите через это медленно.

Начните с простого примера:

f (0) = 1 (как число <1) </p>

Увеличьте до 1

  • f ( 1) = f (0) + f (-1) = 2

(при num = 1, но f (num-1) и f (num-2) меньше 1 ( и поэтому каждый возврат 1)

увеличивается до 2:

f (2) = f (2-1) + f (0) = f (1) + f (-1) = 3

мы уже решили f (1) и f (-1), поэтому мы знаем, что общее возвращаемое значение составляет 2

увеличение до 3: f (3) = f (3-1) ) + f (3-2) = f (2) + f (1) = 3 + 2 = 5

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

f (3) = f (2) + f (1) = (f (1) + f (0)) + (f (0) + f (-1)) = (f (0) + f (-1)) + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 = 5

1 голос
/ 28 апреля 2020

Это простая рекурсивная реализация вычисления числового числа Фибоначчи (1 1 2 3 5 8 ....). И это имеет небольшую ошибку. Это должно быть: 

function f(num) {
    if (num<=1) { // should be <= 1 instead of <, to handle when num = 1, otherwise it'll end up with f(0)+f(-1)
        return 1;
    }
    return f(num-1) + f(num-2);
}

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

Например: 

f(0) -> 0 is less than 1, return 1, thus f(0) = 1
f(1) -> 1 is less than or equal to 1, return 1, thus f(1) = 1
f(2) -> 2 is greater than 1, return f(1) + f(0), which we know from above, is 1 + 1, thus f(2) = 2
f(3) -> 3 is greater than 1, return f(2) + f(1), 2 + 1, thus f(3) = 3
f(4) -> 4 is greater than 1, return f(3) + f(2), 3 + 2, thus f(4) = 5

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

...