рекурсия: хранение нескольких значений в переменных

Question

Код показывает рекурсивную функцию, которая принимает число, скажем, n = 5, и возвращает массив, отсчитывающий от n до 1, т.е. [5,4,3,2,1].

Моя путаница заключается в прямо перед тем, как мы заменим sh числа / значения n на countArray . Я понимаю, что countup (n - 1) , будет генерировать числа (скажем, n = 5) 5,4,3,2,1 ... но я не понимаю, где / как они хранятся . Я бы подумал, что n окажется его последним определенным значением, n = 1 или пустым массивом. Но это неправда, и все они каким-то образом помещены в массив, который, в моем понимании, никогда не создавался / не определялся до того, как в него вставили. Итак, эти две строки с комментариями - две, которые мне нужно понять.

tl; dr: (1) как значения 5-> 1 сохраняются без перезаписи до конечного значения 1 до того, как они будут помещены в массив? (2) Где / как countArray определен как массив до того, как мы поместили sh в него;

function countup(n) {
  if (n < 1) {
    return [];
  } else {
    const countArray = countup(n - 1);  //the storing of 5,4,3,2,1 I don't understand
    countArray.push(n); //I don't understand when countArray was defined as an array
    return countArray;
  }
}
console.log(countup(5)); // [ 1, 2, 3, 4, 5 ]

редактировать: заголовок этого сообщения вероятно, потребуется изменить массив, а не переменную или et c.

Answer 1

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

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

Calling with 5
|   Calling with 4
|   |   Calling with 3
|   |   |   Calling with 2
|   |   |   |   Calling with 1
|   |   |   |   |   Calling with 0
|   |   |   |   |   Returning [] (base case)
|   |   |   |   Pushing 1 to []
|   |   |   |   Returning [1]
|   |   |   Pushing 2 to [1]
|   |   |   Returning [1,2]
|   |   Pushing 3 to [1,2]
|   |   Returning [1,2,3]
|   Pushing 4 to [1,2,3]
|   Returning [1,2,3,4]
Pushing 5 to [1,2,3,4]
Returning [1,2,3,4,5]

Итак, массив был определен в базовом случае . Затем, когда мы вернулись к стеку вызовов, мы добавили его. Есть альтернативные способы сделать это, но это один из распространенных и разумных способов go об этом.

Вы можете увидеть, как я добавил ведение журнала, в следующем фрагменте:

const log = (depth, message) => 
  console .log ('|   '.repeat (depth - 1)  + message)


function countup(n, depth = 1) {
  log(depth, `Calling with ${n}`)
  if (n < 1) {
    log(depth, `Returning [] (base case)`)
    return [];
  } else {
    const countArray = countup(n - 1, depth + 1);  //the storing of 5,4,3,2,1 I don't understand
    log(depth, `Pushing ${n} to [${countArray}]`)
    countArray.push(n); //I don't understand when countArray was defined as an array
    log(depth, `Returning [${countArray}]`)
    return countArray;
  }
}

countup(5)

.as-console-wrapper {min-height: 100% !important; top: 0}

Обновление

Возможно, более ясным будет следующий результат:

/ Calling with 5
|   / Calling with 4
|   |   / Calling with 3
|   |   |   / Calling with 2
|   |   |   |   / Calling with 1
|   |   |   |   |   / Calling with 0
|   |   |   |   |   \ Returning [] (base case)
|   |   |   |   | Pushing 1 to []
|   |   |   |   \ Returning [1]
|   |   |   | Pushing 2 to [1]
|   |   |   \ Returning [1,2]
|   |   | Pushing 3 to [1,2]
|   |   \ Returning [1,2,3]
|   | Pushing 4 to [1,2,3]
|   \ Returning [1,2,3,4]
| Pushing 5 to [1,2,3,4]
\ Returning [1,2,3,4,5]

Что включает лишь незначительные изменения в ведении журнала выписки:

const log = (depth, message) => 
  console .log ('|   '.repeat (depth - 1)  + message)
  
function countup(n, depth = 1) {
  log(depth, `/ Calling with ${n}`)
  if (n < 1) {
    log(depth, `\\ Returning [] (base case)`)
    return [];
  } else {
    const countArray = countup(n - 1, depth + 1);  //the storing of 5,4,3,2,1 I don't understand
    log(depth, `| Pushing ${n} to [${countArray}]`)
    countArray.push(n); //I don't understand when countArray was defined as an array
    log(depth, `\\ Returning [${countArray}]`)
    return countArray;
  }
}

countup(5)

.as-console-wrapper {min-height: 100% !important; top: 0}

Answer 2

Каждая рекурсивная функция, которая по крайней мере завершается, будет иметь условие остановки.

Для вашей функции

if (n < 1) {
 return [];
}

Другая часть рекурсивной функции - это фактическая рекурсия.

Это происходит здесь

const countArray = countup(n - 1);

Вы вызываете функцию с n, что на единицу меньше.

Вы нажмете это ветвь и запускайте рекурсию, пока не дойдете до <1. В этот момент массив создается и возвращается.

После этого вы получаете значения pu sh в этом массиве.

Очень важно, чтобы вы return countArray;, таким образом массив передается вызывающим функциям.

Скорее всего, вам не хватает того, что при вызове функции вызывающая функция ожидает ее завершения, а затем идет дальше.

Обычно вы поймете рекурсивные функции, если попытаетесь сопоставить стек и сопоставить все вызовы функций.

Answer 3

( Я знаю, что это должен быть комментарий, но я не могу добавить код в раздел комментариев ).

Я думаю, лучший способ понять, где создается массив, сам следует за потоком. Это поможет вам понять лучше, чем все слова, из которых можно составить объяснение.

Просто выполните следующие шаги:

1. Откройте консоль в браузере. Нажмите F12, затем щелкните консоль вкладку
2. Вставьте код с выражением debugger:

-

function countup(n) {
  debugger;
  if (n < 1) {
    return [];
  } else {
    const countArray = countup(n - 1);  //the storing of 5,4,3,2,1 I don't understand
    countArray.push(n); //I don't understand when countArray was defined as an array
    return countArray;
  }
}
console.log(countup(5)); // [ 1, 2, 3, 4, 5 ]

Используйте кнопки step in и step over Удачи!

Answer 4

В этот момент

const countArray = countup(n - 1);

функция «ждет» и вызывает вызов самой себя, который останавливается только при условии остановки if (n < 1) на countup (0), которое возвращает пустой массив и возвращается к предыдущему вызову countup (1). В этот момент countArray получает значение, возвращаемое функцией countup (0), равное [], и объявляется как массив, который также делает действительными будущие push вызовы.

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

Возможно, вы захотите узнать больше о рекурсии и стеке вызовов.

Answer 5

TL; DR

Он определен в return [];.

Параметр (n) уменьшается каждый раз, когда вы вводите функцию, и массив будет создан, если он достигнет 0.

---

Допустим, вы звоните countup(2).

Это дойдет до else, который вызовет countup(1). Этот процесс повторяется и вызывает countup(0).

Это не go в ветке else, а вместо этого создает и возвращает пустой массив.

Вызывающий метод countup(1) добавляет 1 к нему (и возвращает результат), а вызывающий countup(2) добавляет 2.

Я попытаюсь визуализировать рекурсию:

countup(2)
  2<1 --> false --> else
  countArray=countup(1)
    1<1 --> false --> else
      countArray=countup(0)
        0<1 --> true --> if
        return []
      push 1 --> [1]
      return countArray --> [1]
  push 1 -->[1,2]
  return countArray -->[1,2]