Рекурсията не е трудна: стъпка по стъпка за тази полезна техника на програмиране

Ще кажа това веднага. Знаете ли събитията, които се случват при извикване на функция? Не? Тогава оттам ще започнем.

Извикване на функция

Когато извикаме функция, контекстът на изпълнение се поставя в стека за изпълнение. Нека разделим това още малко.

Първо, какво е стек?

Стекът е структура от данни, която работи на база „Последно влизане, първо излизане“. Елементът се „натиска“ върху стека, за да се добави към него, а елементът се „изскача“ от стека, за да се премахне.

Използването на стека е метод за нареждане на определени операции за изпълнение.

Сега, да се върнем към това, което е контекст на изпълнение? Контекст на изпълнение се формира при извикване на функция. Този контекст се поставя върху стека за изпълнение, ред на операциите. Елементът, който винаги е първи в този стек, е глобалният контекст на изпълнение. Следват контекстите, създадени от всяка функция.

Тези контексти на изпълнение имат свойства, обект за активиране и обвързване “this”. Обвързването „това“ е препратка към този контекст на изпълнение. Обектът за активиране включва: предадени параметри, декларирани променливи и декларации за функции.

Така че всеки път, когато поставяме нов контекст в стека, обикновено разполагаме с всичко необходимо за изпълнение на код.

Защо казвам обикновено ?

С рекурсия чакаме връщаните стойности, идващи от други контексти на изпълнение. Тези други контексти са по-нагоре в стека. Когато последният елемент от стека завърши изпълнението, този контекст генерира възвръщаема стойност. Тази възвръщаема стойност се предава като възвръщаема стойност от рекурсивния случай към следващия елемент. След това този контекст на изпълнение се изскача от стека.

Рекурсия

И така, какво е рекурсия?

Рекурсивната функция е функция, която се извиква, докато „базово условие“ е вярно и изпълнението спре.

Макар и да е фалшив, ние ще продължим да поставяме контексти за изпълнение върху стека. Това може да се случи, докато имаме „преливане на стека“. Препълването на стека е, когато ни свърши паметта за задържане на елементи в стека.

По принцип рекурсивната функция има поне две части: основно състояние и поне един рекурсивен случай.

Нека разгледаме класически пример.

Факториал

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 като аргументът е преминал. Основният случай е false, така че въведете рекурсивното условие.
  2. Изпълнителният стек поставя factorial()втори път с num-1= 4 като аргумент. Основният случай е false, въведете рекурсивно състояние.
  3. Изпълнителният стек поставя factorial()трети път с num-1(4–1) = 3 като аргумент. Основният случай е false, въведете рекурсивно състояние.
  4. Изпълнителният стек поставя factorial()четвърти път с num-1(3–1) = 2 като аргумент. Основният случай е false, въведете рекурсивно състояние.
  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 като крайна стойност.

Рекурсията е доста чиста, нали?

Можехме да направим едно и също нещо с цикъл за или за известно време. Но използването на рекурсия дава елегантно решение, което е по-четливо.

Ето защо ние използваме рекурсивни решения.

Много пъти проблемът, разделен на по-малки части, е по-ефективен. Разделянето на проблем на по-малки части помага за неговото завладяване. Следователно рекурсията е подход „разделяй и владей“ за решаване на проблеми.

  • Подпроблемите са по-лесни за решаване от първоначалния проблем
  • Решенията на подзадачи се комбинират за решаване на първоначалния проблем

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

Нека да разгледаме следните примери. Използвайте 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');

Quicksort

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 отворен курс