Рекурсия: глави или опашки

Рекурсивна функция е тази, която извиква сама себе си. Независимо дали се гмуркате по-дълбоко в смисъла на живота, като питате „защо“ отново и отново (спойлер: отговорът е пица), или преминаване през вложени структури от данни, рекурсията играе критична роля.

За мнозина итерацията е първият основен инструмент на програмиста в динамичното програмиране. Като цяло е по-лесно да се научи и в много случаи итерацията има незначителни разлики в производителността спрямо рекурсията.

Нека да разгледаме изчисляването на 4! както итеративно, така и рекурсивно.

Итеративно:

function iterativeFactorial(num) {
  let result = 1;
  for (let i = 1; i < num + 1; i++) {
    result *= i;
  }
  return result;
}
iterativeFactorial(4);
=> 24

Рекурсивно:

function recursiveFactorial(num) {
  if (num === 0) {
    return 1;
  }
  
  return num * factorial(num - 1);
}
recursiveFactorial(4);
=> 24

В такива случаи истинската печалба е само подобряването на четимостта на кода. Рекурсивният пример използва един ред код по-малко и премахва по-сложната циклична логика на итеративния пример. Голяма работа ли е? Вероятно не.

Има, от друга страна, моменти, когато рекурсията е почти необходима. Всъщност обичаен случай на употреба е преминаването през вложени структури от данни.

Разгледайте структурата на данните по-долу с привидно неизвестно количество вложени масиви:

const data = [
  { id: "0" },
  {
    id: "1",
    children: [
      {
        id: "1.1",
        children: [
          {
            id: "1.1.1",
            children: [
              {
                id: "1.1.1.1",
                children: [
                  { id: "1.1.1.1.1" },
                  { id: "1.1.1.1.2" },
                  { id: "1.1.1.1.3" }
                ]
              },
              { id: "1.1.1.2" },
              { id: "1.1.1.3" }
            ]
          },
          { id: "1.1.2" },
          { id: "1.1.3" },
        ]
      },
      { id: "1.2" },
      { id: "1.3" }
    ]
  },
  { id: "2" },
  { id: "3" }
];

Ако искаме да съберем всички стойности на id на обектите в един масив, итерацията не е осъществима. Моля, включете компютъра си за сметало, ако смятате да преброите ръчно колко е вложен всеки обект. Ами ако използваме API и горното е динамично изобразен JSON? Имаме нужда от решение, което работи динамично.

Въведете рекурсия.

Рекурсивна функция, връщаща масив от всички идентификатори, може да бъде:

function returnIdArr(data, result = []) {
  for (let i = 0; i < data.length; i++) {
    result.push(data[i].id);
    
    if (data[i].children) {
      returnIdArr(data[i].children, result);
    }
  }
  
  return result;
}
returnIdArr(data);
=> ['0', '1', '1.1', '1.1.1', '1.1.1.1', '1.1.1.1.1', '1.1.1.1.2', '1.1.1.1.3', '1.1.1.2', '1.1.1.3', '1.1.2', '1.1.3', '1.2', '1.3', '2', '3']

Функцията преминава през масива и ако някой от обектите включва свойство „деца“, функцията рекурсивно се извиква върху вложения масив от деца ad infinitum (или докато няма повече „деца“). Всеки идентификатор се изпраща към масива с резултати, който сам по себе си се предава като аргумент с всяко рекурсивно извикване.

Разбиване на нишката на изпълнение за първите няколко кадъра:

...
// the first iteration of the loop pushes '0' into the result array
result.push(data[0].id); // result = ['0']
if (data[0].children)... // false
/* ------------------------------------------------ */
...
// the second iteration pushes '1' into the result array
result.push(data[1].id); // result = ['0', '1']
// now true:
if (data[1].children) {
  returnIdArr(data[1].children, ['0', '1']);
/* recursively calls the function with the children and current result array as arguments */
...
/* ------------------------------------------------ */
/* the first iteration of this new loop (nested one level down) pushes '1.1' into the result array */
result.push(data[0].id); // result = ['0', '1', '1.1']
// true again:
if (data[0].children)...
returnIdArr(data[1].children, ['0', '1', '1.1']);
// and recursion again...
...

Можем да видим стойността на рекурсията в примери като този - нашата сравнително проста функция returnIdArr действа като швейцарско ножче, което връща масив от идентификатори за всяка версия на тази структура от данни. Той е ефективен, четим и динамичен.

Сега, като разгледаме горните кадри в стека на повикванията с по-внимателно око, може дори да започнем да обмисляме последиците върху паметта. Нито един от фреймовете в стека за извикване не може да изскочи, докато всеки елемент в текущия масив не бъде обходен. Това означава, че всички дъщерни свойства в текущия масив също трябва да бъдат оценени първо, както и дъщерните свойства в тях. Всъщност първото ниво на масива, завършващо с обект, чието свойство id е ‘3’, остава в стека за повиквания през цялото време, докато всеки друг вложен масив не бъде напълно обработен.

Има ли други начини за справяне с това?

Всъщност има две общи реализации в този тип директна рекурсия: рекурсия на главата и опашката.

Главната рекурсия извиква рекурсивната функция в началото преди други процеси. Обикновено функцията определя, че е необходима рекурсия и се извиква с намален параметър.

Ето малко (измислена) рекурсия на главата в действие:

function headCount(num) {
  if (num === 0) {
    return;
  } else {
    countDown(num - 1);
  }
  console.log(num);
}
count(3)
// 1
// 2
// 3

Функцията headCount оценява дали нейният аргумент num е 0. Ако не, функцията се извиква рекурсивно с намаленото число като аргумент.

Двете неща, които трябва да се отбележат, са:

Рекурсията се случва в горната част или в началото на функцията/обработката
Записаните числа започват от 1 (а не от 3) и нарастват

От друга страна с опашната рекурсия е обратното - обработката се извършва преди рекурсивното извикване.

Ето малко (също измислена) рекурсия на опашката:

function tailCount(num) {
  if (num === 0) {
    return;
  } else {
    console.log(num)
  }
  countDown(num - 1);
}
countDown(3)
// 3
// 2
// 1

За разлика от нашата функция headCount, tailCount извежда числа, започващи от 3 и след това намаляващи. За да съществува тази разлика, кадрите на съответните стекове за извикване трябва да са различни при достигане на изразите console.log.

Функцията headCount трябва да създава рамки за всеки контекст на изпълнение от всяко рекурсивно повикване. Само след достигане на основния случай, num === 0, кадрите могат да започнат да изскачат от стека, като по този начин достигат до всеки съответен console.log.

От друга страна, функцията tailCount замества своя контекст на изпълнение с всяко рекурсивно извикване. Извиканата рекурсивна функция излиза от своя номер и няма нужда от никакъв контекст от предишното извикване. Поради оптимизирането на опашката на извикванията, много компилатори гарантират, че съществува само един кадър в стека на повикванията през цялата продължителност на нишката на изпълнение.

Незначителна разлика в действителния написан код, но огромна разлика в поведението.

Рекурсията на обучение идва със стръмна крива и вероятно много неуспешни безкрайни цикли, но нюансираните печалби в производителността и необходимите случаи на употреба я правят критичен инструмент за всеки програмист.

О, докато сте тук, може да искате да прочетете тази статия: Рекурсия: глави или опашки

Рекурсия: глави или опашки

Подобни въпроси