Рекурсия, так горячо прямо сейчас. Рекурсия.

Подождите, подождите, я обещаю, что могу предложить больше, чем ссылки на Zoolander. Но давайте смотреть правде в глаза — рекурсия — популярная тема в интервью и на сайтах по кодированию, поэтому важно разобраться. Это может быть невероятно полезно в правильных ситуациях, но иногда вам приходится учитывать компромиссы, возникающие при использовании рекурсивного решения.

Давайте используем сортировку слиянием в качестве примера. Здесь я представлю вам два способа сделать это. Сначала:

const merge = (left, right) => {
  if (left.length === 0) return right;
  if (right.length === 0) return left;
return left[0] < right[0]
    ? [left[0], ...merge(left.slice(1), right)]
    : [right[0], ...merge(left, right.slice(1))];
};
const mergeSort = arr => {
  if (arr.length < 2) return arr;
  const middle = parseInt(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle, arr.length);
  return merge(mergeSort(left), mergeSort(right));
}

Это очень компактное решение — вызов mergeSort с массивом, он разбивает этот массив пополам, чтобы вызвать слияние для возвращаемого значения mergeSort для обеих половин, и слияние рекурсивно вызывает себя до тех пор, пока сортировка не закончится.

Так в чем проблема? На моем компьютере он начинает давать сбои для массивов длиной более 10 000 индексов. 10 000! В мире больших данных это совсем мелочь. И почему ломается? Именно из-за того, что делает рекурсию такой полезной: вызовы функций для каждого рекурсивного слияния попадают в стек, как и ожидалось, но если ваш стек не готов обрабатывать невероятное количество вызовов (мой разбивает около 133 000 незавершенных вызовов функций), он будет переполниться.

Конечно, есть способ избежать этого: не втискивайте рекурсию в обе функции. Приведенный выше код вызывает слияние внутри функции слияния, а также слияние и слияниеSort внутри функции слиянияSort. Имея массив из 100 индексов, вы получаете около 740 вызовов функций для сортировки всего массива. Мы можем отсортировать массив аналогичного размера менее чем за 300 вызовов функций (и удобно сортировать массивы с более чем миллионом индексов без сбоев), если просто заменим эти рекурсивные вызовы слияния циклом while. Посмотри:

const merge = (left, right) => {
  let merged = [];
  while (left.length || right.length) {
    if (!left.length) {
      merged.push(right.shift());
      continue;
    }
    if (!right.length) {
      merged.push(left.shift());
      continue;
    }
  left[0] < right[0]
      ? merged.push(left.shift())
      : merged.push(right.shift());
  }
  return merged;
};
const mergeSort = arr => {
  if (arr.length < 2) return arr;
  const middle = parseInt(arr.length / 2);
  let left = arr.slice(0, middle);
  let right = arr.slice(middle, arr.length);
  return merge(mergeSort(left), mergeSort(right));
};

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

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