Опашката рекурсия в Скала
В този пост ще говорим за интересен фиш функционално програмиране - на рекурсия на опашка. Но първо, нека да си спомним какво общото рекурсия. Така че рекурсия - описание на определен обект, който е неразделна част от себе си. Например, един математически израз може да съдържа цифрови операнди, аритметика и други математически изрази.
В тази статия ние се сблъскваме с рекурсивни функции. За да разберете стойността на такава функция за определен набор от входни параметри, необходими за определянето на стойността на тази функция за различен набор от входни параметри. С други думи, функция, която нарича себе си. Най-известният пример на рекурсия е факториел (така казват повечето учебници по програмиране) и числата на Фибоначи. Забравете за факториелите и да видим как изглежда изпълнението на числата на Фибоначи в Java:
Както се вижда от примера, преди връщане на стойност от функция обаждане се извършва два от една и съща функция, но с различни стойности.
опашката рекурсия
Сега обратно към опашката рекурсивния. Рекурсия е на опашката, ако обаждането е рекурсивна функция ще бъде последната операция преди да се върне. Нека да пренапише предишния пример с помощта на опашката рекурсия:
API на класа се е променила: ние все още имаме метод, който връща номера на п-ия Фибоначи. Също така ние имаме нов частен метод fibIter. който включва опашка рекурсия. Много често, за неговото изпълнение, метод на помощник, който се състоянието преди следващата итерация на рекурсията. С тази опашка рекурсия може да се представи като цикъл:
Този код изглежда ужасно и има много места, където можете да се обърка, така че често предпочитан рекурсивни функции поради тяхната краткост и четливост.
Нека разгледайте нашите функции по време на битка и брои 10 000-ия елемент от последователността. За наше огорчение, двата метода - и ПИБ. и fibWithTailRec - хвърлят java.lang.StackOverflowError. Това предполага, че използването на рекурсия в Java да внимателно. И не забравяйте за начина на използване на линия :)
Скала на помощ
И това, което те мислят за рекурсия други езици JVM? Нека да видим как стоят нещата в Скала с рекурсивни функции и пренаписване на двете рекурсивни изпълнението на кода, като се има предвид числата на Фибоначи. Нека се опитаме да направим най-сходния в изпълнение на същите функции:
И сега отново да разчита на Фибоначи номер 10000, но в Скала. Оказва се, че версията на опашката-рекурсивни успешно се справи със задачата. Каква е разликата между почти "едно и също" код в Java и Scala. Нека да погледнем на байт кода от тези методи (javap -C) и проверете какво всъщност трябва да правят компилатори:
Scala компилатор осъзнах, че тази опашка рекурсия, и се разпространява рекурсивно извикване на функция в цикъла, който, както видяхме по-рано, за да напишете не толкова хубаво.
Светът никога няма да е същото
Така че, ние вече знаем как стръмен опашка рекурсия. Време е да се прилагат тези знания. Светът на ОП, нито една програма не е завършено без списък. Опитайте се да осъзнаят, независимо намотка - един от основните операции, включени в списъка (Scala ни предлага две версии - в ляво и дясно) (Той е известен и като се намали стадото.):
Както можете да видите, и двете функции са рекурсивни, но, за ужас на ужасите, foldRight не опашка рекурсия, така че ние сме изправени пред преливане стак. Налице е сравнително просто решение, което е, разбира се, изисква допълнителни разходи, но това не влошава сложността на алгоритъм. Пишем правото на намотка чрез извиване на ляво:
Ако ние не вярваме, ще бъде нашата функция е оптимизиран или не, и ние бихме много сте харесали, можете да използвате анотация @tailrec. А доста често срещано мнение е, че екип от компилатора да направи опашка рекурсия в метод. Но това не е (особено след като преобразуване не винаги е възможно). Това прави само проверка дали маркирани си игрален опашка рекурсия, и ако не, ще има грешка компилация. Причините за това малко и те са лесно да се провери:
- това не е окончателно метод, което означава, че може да се замени в подкласове
- методът не се предизвика, т.е. това не е рекурсивно
- това не е опашка рекурсия.
