Рекурсія не складна: покрокове покрокове керівництво цією корисною технікою програмування

Я збираюся сказати це відразу. Чи знаєте ви події, які відбуваються при виклику функції? Немає? Тоді з цього ми і почнемо.

Виклик функції

Коли ми викликаємо функцію, контекст виконання розміщується у стеці виконання. Давайте розберемо це ще трохи.

По-перше, що таке стек?

Стек - це структура даних, яка працює за принципом "Останній вхід, перший вихід". Елемент "штовхається" на стек, щоб додати до нього, а елемент "вискакує" зі стека, щоб видалити його.

Використання стека - це метод упорядкування певних операцій для виконання.

Тепер повернемось до того, що таке контекст виконання? Контекст виконання формується при виклику функції. Цей контекст розміщується на стеку виконання, порядку операцій. Елемент, який завжди є першим у цьому стеку, є глобальним контекстом виконання. Далі йде будь-який контекст, створений функцією.

Ці контексти виконання мають властивості, об’єкт активації та прив’язку “this”. Прив'язка "це" є посиланням на цей контекст виконання. Об'єкт активації включає: передані параметри, оголошені змінні та оголошення функції.

Тому кожного разу, коли ми розміщуємо новий стек у стеці, ми зазвичай маємо все необхідне для виконання коду.

Чому я кажу зазвичай ?

З рекурсією ми чекаємо повернених значень, що надходять з інших контекстів виконання. Ці інші контексти вищі в стеці. Коли останній елемент у стеку завершує виконання, цей контекст генерує повернене значення. Це повертане значення передається як повернене значення з рекурсивного випадку до наступного елемента. Потім цей контекст виконується зі стека.

Рекурсія

Отже, що таке рекурсія?

Рекурсивна функція - це функція, яка викликає себе до тих пір, поки “базовий стан” не буде істинним, а виконання зупиниться.

Поки false, ми будемо продовжувати розміщувати контексти виконання поверх стека. Це може відбуватися, поки у нас не буде "переповнення стека". Переповнення стека - це коли у нас закінчується пам’ять для зберігання елементів у стеку.

Взагалі, рекурсивна функція має щонайменше дві частини: базовий стан і принаймні один рекурсивний випадок.

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

Факториал

const factorial = function(num) { debugger; if (num === 0 || num === 1) { return 1 } else { return num * factorial(num - 1) }}
factorial(5)

Тут ми намагаємось знайти 5! (п’ять факторіалів). Функція факторіалу визначається як добуток усіх додатних цілих чисел, менших або рівних його аргументу.

Перша умова говорить: "якщо переданий параметр дорівнює 0 або 1, ми вийдемо і повернемо 1".

Далі рекурсивний випадок стверджує:

"Якщо параметр не дорівнює 0 або 1, тоді ми передамо значення в numрази поверненого значення виклику цієї функції ще раз num-1як аргумент".

Отже, якщо ми викликаємо factorial(0), функція повертає 1 і ніколи не потрапляє в рекурсивний випадок.

Те саме справедливо для factorial(1).

Ми можемо побачити, що відбувається, якщо вставити в код оператор налагоджувача та використати devtools, щоб пройти його і спостерігати за стеком викликів.

  1. Стек виконується factorial()з 5, коли аргумент передано. Базовий випадок хибний, тому введіть рекурсивний стан.
  2. Стек виконання factorial()вдруге ставить num-1= 4 як аргумент. Базовий випадок хибний, введіть рекурсивний стан.
  3. Стек виконання factorial()втретє ставить num-1(4–1) = 3 як аргумент. Базовий регістр хибний, введіть рекурсивний стан.
  4. Стек виконання ставить factorial()четвертий раз з num-1аргументом (3–1) = 2. Базовий випадок хибний, введіть рекурсивний стан.
  5. Стек виконання factorial()в п’ятий раз ставить num-1(2–1) = 1 як аргумент. Тепер базовий випадок вірний, тому поверніть 1.

На даний момент ми зменшували аргумент на одиницю при кожному виклику функції, поки не досягнемо умови повернення 1.

6. Звідси завершується останній контекст виконання num === 1, так що функція повертає 1.

7. Далі num === 2, тому повернене значення дорівнює 2. (1 × 2).

8. Далі num === 3, таким чином повертається значення 6, (2 × 3).

Поки що маємо 1 × 2 × 3.

9. Далі,, num === 4(4 × 6). 24 - значення, що повертається до наступного контексту.

10. Нарешті, num === 5(5 × 24), і ми маємо 120 як остаточне значення.

Рекурсія досить акуратна, так?

Ми могли зробити те ж саме за допомогою циклу for або a while. Але використання рекурсії дає елегантне рішення, яке є більш читабельним.

Ось чому ми використовуємо рекурсивні рішення.

Багато разів проблема, розбита на дрібніші частини, є більш ефективною. Поділ проблеми на менші частини допомагає її подолати. Отже, рекурсія - це підхід "розділи і переможи" до вирішення проблем.

  • Підзадачі вирішити простіше, ніж вихідну проблему
  • Рішення підзадач поєднуються для вирішення вихідної проблеми

“Розділяй і володар” найчастіше використовується для обходу або пошуку таких структур даних, як двійкові дерева пошуку, графіки та купи. Він також працює для багатьох алгоритмів сортування, таких як швидке сортування та купірування.

Розглянемо наступні приклади. Використовуйте devtools, щоб зрозуміти, що відбувається де і коли. Пам’ятайте, що слід використовувати оператори налагоджувача та виконувати кроки кожного процесу.

Фібоначчі

const fibonacci = function(num) { if (num <= 1) { return num } else { return fibonacci(num - 1) + fibonacci(num - 2) }}fibonacci(5);

Рекурсивні масиви

function flatten(arr) { var result = [] arr.forEach(function(element) { if (!Array.isArray(element)) { result.push(element) } else { result = result.concat(flatten(element)) } }) return result}
flatten([1, [2], [3, [[4]]]]);

Перевертання рядка

function reverse(str) { if (str.length === 0) return '' return str[str.length - 1] + reverse(str.substr(0, str.length - 1))}
reverse('abcdefg');

Швидкий сорт

function quickSort(arr, lo, hi) { if (lo === undefined) lo = 0 if (hi === undefined) hi = arr.length - 1
 if (lo  partition: ' + p) // sort subarrays quickSort(arr, lo, p - 1) quickSort(arr, p + 1, hi) } // for initial call, return a sorted array if (hi - lo === arr.length - 1) return arr}
function partition(arr, lo, hi) { // choose last element as pivot var pivot = arr[hi] // keep track of index to put pivot at var pivotLocation = lo // loop through subarray and if element <= pivot, place element before pivot for (var i = lo; i < hi; i++) { if (arr[i] <= pivot) { swap(arr, pivotLocation, i) pivotLocation++ } } swap(arr, pivotLocation, hi) return pivotLocation}
function swap(arr, index1, index2) { if (index1 === index2) return var temp = arr[index1] arr[index1] = arr[index2] arr[index2] = temp console.log('swapped' + arr[index1], arr[index2], +' in ', arr) return arr}
quickSort([1, 4, 3, 56, 9, 8, 7, 5])

Важливо практикувати рекурсивні методи. Для вкладених структур даних, таких як дерева, графіки та купи, рекурсія є безцінною.

У наступній статті я обговорюю методи оптимізації зворотних викликів та методів запам'ятовування, які стосуються рекурсії. Дякуємо за читання!

Подальші ресурси

Вікіпедія

Розробка програмного забезпечення

Ще одна хороша стаття

Відкритий навчальний курс MIT