Рекурсия, стек

Други функции могат да бъдат извикани в тялото на функцията за изпълнение на подзадачи.

Специален случай на извикване е, когато функция се извиква. Това се нарича рекурсия.

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

Сега ще видим примери.

Тази глава е предназначена за читатели, които все още не са запознати с тази тема и искат да разберат по-добре как функционират функциите.

Pow (x, n) мощност чрез рекурсия

Като първи пример за използване на рекурсивни повиквания, помислете за проблема с повишаването на числото x до естествена степен n .

Тя може да бъде представена като комбинация от по-просто действие и по-проста задача от същия тип по следния начин:

Тоест, x n = x * x n-1 .

Например, нека изчислим pow (2, 4), като последователно преминем към по-прост проблем:

  1. пуд (2, 4) = 2 * пуд (2, 3)
  2. пуд (2, 3) = 2 * пуд (2, 2)
  3. пуд (2, 2) = 2 * пуд (2, 1)
  4. прах (2, 1) = 2

На стъпка 1 трябва да изчислим pow (2,3), така че правим стъпка 2, след това се нуждаем от pow (2,2), правим стъпка 3, след това стъпка 4 и можем да спрем на нея, защото е очевидно е, че резултатът, вдигащ число до степен 1, е равен на самото число.

Освен това, имайки резултат в стъпка 4, той се замества обратно в стъпка 3, след това имаме pow (2,2) - заместен в стъпка 2 и на стъпка 1 вече получаваме резултата.

Казва се, че "функцията pow се извиква рекурсивно" до n == 1 .

Стойността, при която завършва рекурсията, се нарича база на рекурсията. В горния пример основата е 1 .

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

Максималната дълбочина на рекурсия в браузърите е ограничена, определено можете да разчитате на 10 000 вложени повиквания, но някои интерпретатори позволяват повече.

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

Контекст на изпълнение, стек

Сега ще видим как работят рекурсивните разговори. За да направим това, ще разгледаме как функционират обикновено функциите, какво се случва, когато се обадите.

Всяко извикване на функция има свой "контекст на изпълнение".

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

Например извикването на pow (2, 3) от примера по-горе ще създаде контекст на изпълнение, който съхранява променливите x = 2, n = 3. Ще го очертаем така:

След това функцията pow започва да се изпълнява. Изразява се изразът n! = 1 - той е равен на true, тъй като в текущия контекст n = 3. Следователно първият клон, ако е включен:

За да оцените израза x * pow (x, n-1), трябва да стартирате pow с нови аргументи.