Рекурзија није тешка: корак по корак кроз ову корисну технику програмирања

Рећи ћу ово одмах. Да ли знате догађаје који се дешавају након позивања функције? Не? Тада ћемо тамо почети.

Позивање функције

Када позовемо функцију, контекст извршења се поставља на стек извршења. Раздвојимо ово још мало.

Прво, шта је стек?

Склоп је структура података која функционише на бази „Последњи улаз, први излаз“. Ставка се „гурне“ у стек да би се додала, а ставка се „искочи“ из стека да би се уклонила.

Коришћење стека је метод наређивања одређених операција за извршење.

Сад, да се вратимо на оно што је контекст извршења? Контекст извршења формира се након позива функције. Овај контекст се поставља на стек извршења, редослед операција. Ставка која је увек прва у овом стеку је глобални контекст извршења. Следеће су било које функције створене контекстима.

Ови контексти извршавања имају својства, објекат активације и „ово“ везивање. „Ово“ везивање је референца на овај контекст извршења. Објект активације укључује: прослеђене параметре, декларисане променљиве и декларације функција.

Дакле, сваки пут када на стек поставимо нови контекст, обично имамо све што је потребно за извршавање кода.

Зашто обично кажем ?

Са рекурзијом чекамо повратне вредности које долазе из других контекста извршавања. Ови други контексти су виши у стеку. Када последња ставка у стеку заврши извршење, тај контекст генерише повратну вредност. Ова повратна вредност се преноси као повратна вредност из рекурзивног случаја у следећу ставку. Тај контекст извршења се тада искаче из стека.

Рекурзија

Па, шта је рекурзија?

Рекурзивна функција је функција која се сама позива све док „основни услов“ није истинит и извршење се заустави.

Иако је нетачно, и даље ћемо постављати контексте извршавања на врх стека. То се може догодити док не добијемо „преливање стека“. Преливање стека је када нам понестане меморије за држање предмета у стеку.

Генерално, рекурзивна функција има најмање два дела: основни услов и најмање један рекурзивни случај.

Погледајмо класичан пример.

Фацториал

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).

Можемо видети шта се дешава ако у код уметнемо наредбу за отклањање грешака и помоћу девтоолс-а закорачимо и посматрамо низ позива.

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

Рекурзија је прилично уредна, зар не?

Могли смо да учинимо исту ствар са краткотрајном или краћом петљом. Али коришћење рекурзије даје елегантно решење које је читљивије.

Због тога користимо рекурзивна решења.

Много пута је проблем рашчлањен на мање делове ефикаснији. Дељење проблема на мање делове помаже у његовом решавању. Отуда је рекурзија приступ подељи и победи у решавању проблема.

  • Подпроблеме је лакше решити од оригиналног проблема
  • Решења за под-проблеме комбинују се за решавање изворног проблема

„Дивиде-анд-цонкуер“ се најчешће користи за прелазак или претраживање структура података као што су бинарна стабла претраживања, графикони и гомиле. Такође ради за многе алгоритме за сортирање, попут брзог сортирања и сортирања.

Порадимо на следећим примерима. Користите девтоолс да бисте концептуално схватили шта се дешава где и када. Не заборавите да користите изјаве за отклањање грешака и кораке кроз сваки процес.

Фибонацци

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])

Вежбање рекурзивних техника је важно. За угнежђене структуре података попут стабала, графикона и гомила, рекурзија је непроцењива.

У будућем чланку ћу разговарати о техникама оптимизације и меморисања реп-позива, које се односе на рекурзију. Хвала за читање!

Даљи ресурси

Википедиа

Софтверско инжењерство

Још један добар чланак

МИТ отвори програм за учење