Каков порядок операций в этой рекурсивной функции? - PullRequest
Новая
       7

Каков порядок операций в этой рекурсивной функции?

2 голосов
/ 16 марта 2020

Рекурсия в javascript ускользает от меня. Я почти на месте, но меня немного смущает порядок операций. Возьмем, к примеру, следующую функцию: 

function rangeOfNumbers(startNum, endNum) {
  if (endNum - startNum === 0) {
    return [startNum];
  } else {
    var numbers = rangeOfNumbers(startNum, endNum - 1);
    numbers.push(endNum);
    return numbers;
  }
}

Вопросы, которые я пытаюсь выяснить:

  1. Создает ли это замыкание вокруг numbers?

  2. Функция rangeOfNumbers возвращает numbers каждый раз или только после полного завершения рекурсии?

  3. Для базового случая: почему мы возвращаем массив только с startNum в качестве «базового условия»? Разве это не перезаписывает переменную numbers при возврате? Я не уверен, как именно работает базовый вариант. Кажется, он всегда возвращает что-то не то, что мы ищем, но он контролирует, когда функция должна прекратить выполнение (при первом запуске вызова функции и / или для ее завершения).

Ответы [ 3 ]

3 голосов
/ 16 марта 2020

Создает ли это замыкание вокруг чисел?

Нет, имя переменной numbers можно ссылаться только внутри одного блока (ну, функция), и оно заканчивается, ничего еще есть ссылка на это. Ничто не сохранило ссылку на него, так что это не замыкание.

Функция rangeOfNumbers возвращает числа каждый раз или только после полной рекурсии?

В каждом рекурсивном случае возвращается переменная numbers. В базовом случае возвращается новый массив. Но поскольку в рекурсивных случаях переменная numbers является ссылкой на массив, возвращаемый рекурсивным вызовом, массив, возвращаемый по цепочке каждый раз, является одним и тем же массивом.

Для базового случая: Почему мы возвращаем массив с только startNum в качестве «базового условия»? Разве это не перезаписывает числовую переменную при возврате?

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

Имейте в виду, что каждый вызов функция приводит к отдельным привязкам для своих переменных. Например, с 

function fn(count) {
  const num = Math.random();
  return num + (count > 1 ? fn(count - 1) : 0);
}

Каждый вызов fn имеет отдельную переменную num, которая является случайным числом. Рекурсивный вызов не перезаписывает ничего из предыдущих вызовов.

Для вашего rangeOfNumbers последний рекурсивный вызов приводит к базовому случаю: массиву [startNum]. Он возвращается рекурсивному вызывающему и сохраняется в переменной numbers для этого конкретного вызывающего в 

var numbers = rangeOfNumbers(startNum, endNum - 1);

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

2 голосов
/ 16 марта 2020

Рассмотрим это изменение в вашей функции, единственное отличие заключается в регистрации: 

function rangeOfNumbers(startNum, endNum) {
  if (endNum - startNum === 0) {
    console.log("Reached base case, returning: ");
    console.log([startNum]);
    return [startNum];
  } else {
    var numbers = rangeOfNumbers(startNum, endNum - 1);
    numbers.push(endNum);
    console.log("Returning " + numbers.join(','));
    return numbers;
  }
}

И затем мы называем это так: 

rangeOfNumbers(0, 7);

И он будет регистрировать 

Reached base case, returning: 
VM60:4 [0]
VM60:9 Returning 0,1
VM60:9 Returning 0,1,2
VM60:9 Returning 0,1,2,3
VM60:9 Returning 0,1,2,3,4
VM60:9 Returning 0,1,2,3,4,5
VM60:9 Returning 0,1,2,3,4,5,6
VM60:9 Returning 0,1,2,3,4,5,6,7

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

1 голос
/ 17 марта 2020

Вот один из способов написать функцию range, увеличив start - 

const range = (start, end) =>
  start > end                             // terminating condition
    ? []                                  // base case
    : [ start, ...range(start + 1, end) ] // recursive step
    
console.log(range(5,10))
// [ 5, 6, 7, 8, 9, 10 ]

И еще мы можем написать range, уменьшив end - 

const range = (start, end) =>
  end < start                             // terminating condition
    ? []                                  // base case
    : [ ...range(start, end - 1), end ]   // recursive step
    
console.log(range(5,10))
// [ 5, 6, 7, 8, 9, 10 ]

Обратите внимание на сходства и различия в каждой программе

...