У меня есть вопрос о рекурсии: как я должен «думать», чтобы обрабатывать, хранить и отлаживать рекурсию в моей голове? Поясню: например, у нас есть функция, вычисляющая число Фибоначчи:
function fib(n) {
if(n < 3) return 1;
return fib(n - 1) + fib(n - 2);
}
Выглядит очень просто. Упростим отладку:
function fib(n) {
if(n < 3) return 1;
var r1 = fib(n - 1);
var r2 = fib(n - 2);
var result = r1 + r2;
return result;
}
Теперь посмотрим, как будет работать эта функция, если n = 5:
fib(5) //n > 2, we need go deeper r1 = fib(n - 1) -> call fib(4)
->fib(4) //n > 2, we need go deeper r1 = fib(n - 1) -> call fib(3)
->fib(3) //n > 2, we need go deeper r1 = fib(n - 1) -> call fib(2)
->fib(2) n < 3 -> return 1
Теперь позвольте мне написать все еще раз (пожалуйста, читайте снизу вверх, начиная с fib(2)):
fib(5) n = 5; r1 = fib(4) -> 3; r2 = fib(3)//here we go one more time:
r1 = fib(2) return [1]
r2 = fib(1) return [1]
r = r1 + r2 = 1 + 1 = [2]
So fib(3) -> [2];
Only now we can calculate fib(5):
n = 5; r1 = 3; r2 = 2 ->
r = r1 + r2 = 3 + 2 = 5; //Answer
->fib(4) n = 4; r1 = fib(3) -> 2; r2 = fib(2) -> 1; r = r1 + r2 = 2 + 1 = [3]
->fib(3) n = 3; r1 = fib(2) -> 1; r2 = fib(1) -> 1; r = r1 + r2 = 2 + 1 = [2]
->fib(2) return [1]
А теперь посмотрим нерекурсивную функцию для числа Фибоначчи:
function fn(number) {
if(number === 0) return 0;
var fib = [1, 1];
for(var i = 2; i < number; i++) {
var temp = fib[i - 1] + fib[i - 2];
fib.push(temp);
}
return fib[fib.length - 1];
}
Эта функция имеет немного больше кода, но она содержит только один цикл, и я могу легко держать все в голове без этого огромного количества рекурсивных уровней.
Рекурсивная функция, которую я показываю в качестве примера, не моя, и я не понимаю, как я должен думать, чтобы реализовать такие функции. С циклом все очень просто:
- у нас есть массив с двумя значениями arr = [1, 1].
- Мы хотим получить следующее значение?
- Нет проблем: просто подсчитайте сумму для arr[n] = arr[n - 1] + arr[n - 2]; вернуть обр[н];
И это все :)
Не поймите меня неправильно, я потратил несколько месяцев, чтобы понять, как «разбирать» рекурсивные функции в голове, но так и не нашел решения. Мне помогает только использование бумаги и многочасовые размышления.
