Симулирана рекурсия

В началото на 60-те C.A. Hoare разработи метода за сортиране Quicksort. Quicksort разделя данните в последователно намаляващи групи. Само по себе си това не звучи кой знае как, но тестовете показват, че Quicksort може да сортира големи обеми от данни десетки или стотици път по-бързо от повечето често използвани алгоритми. Но има един проблем.

Quicksort използва рекурсия- процес, в който процедура или функция извиква сама себе си. Рекурсията е много мощна при решаване на проблеми, при които се повтарят едни и същи въпроси и се изпълняват едни и същи действия, но всеки действие се прилага върху резултатите от предното. Разглеждането на структури от данни като свързани списъци и дървета са идеални за рекурсивно програмиране. В езици като C или Pascal е позволена рекурсията, но в други като Cobol по принцип е забранена. Заобикаляне на ограниченията на езика може да се постигне чрез симулиране на рекурсия, по начин, който може да се приложи към почти всички програмни езици.

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

Симулиране на рекурсия

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

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

Пример за Quicksort чрез симулирана рекурсия

Примерът, който ще представя тук демонстрира симулирана рекурсия в Cobol. Това е най-враждебната среда за рекурсивно програмиране. Идеята е "Ако може да се направи тук, може навсякъде". Данните за Quicksort ще изглеждат:

01  TABLE-TO-BE-SORTED.
   02 TABLE-ENTRY   PIC X(100) OCCURS 32000 TIMES.
*
01  SWAP-ELEMENT     PIC X(100).
01  PIVOT-VALUE      PIC X(100).
*
01  WORKING-INDEXES.
   02 FURST         PIC 9(5) USAGE BINARY.
   02 LAAST         PIC 9(5) USAGE BINARY.
   02 PIVOT         PIC 9(5) USAGE BINARY.
   02 HOW-RETURN    PIC 9(5) USAGE BINARY.
*
01  TABLE-OF-INDEXES.
   02 CURRENT-INDEXES OCCURS 100 TIMES.
       03 FILLER    PIC 9(5) USAGE BINARY.
       03 FILLER    PIC 9(5) USAGE BINARY.
       03 FILLER    PIC 9(5) USAGE BINARY.
       03 FILLER    PIC 9(5) USAGE BINARY.
01  SESSION-INDEX    PIC 9(5) USAGE BINARY.
*
01  LEFT-INDEX       PIC 9(5) USAGE BINARY.
01  RIGHT-INDEX      PIC 9(5) USAGE BINARY.

Тук таблица от 32,000 100-байтови елемента е данните,които ще се сортират. SWAP-ELEMENT и PIVOT-VALUE са работни области, които ще съдържат елементи от време на време. WORKING-INDEXES сочи към елементите на таблицата и са целочислени . FURST и LAAST са указатели към първия и последния елемент от таблицата в текущата група. Размерът и положението на тази група се променя постоянно по време на процеса Quicksort.

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

TABLE-OF-INDEXES е стек от WORKING-INDEXES. При напредване на програмата надолу (извикване на нова итерация на QUICKSORT) или нагоре( връщане към предната итерация) се записват или извличат стойностите на указателите и маркера. Всеки елемент в TABLE-OF-INDEXES е набор от WORKING-INDEXES. SESSION-INDEX е указател към набора от стойности, който се използва в момента. LEFT и RIGHT-INDEX са работни указатели, които се използват във всяка фаза на Quicksort.

Инициализирането е:

INITIALIZE-SORT.

   MOVE LOW-VALUES TO TABLE-OF-INDEXES.
   MOVE 1 TO FURST
             HOW-RETURN
             SESSION-INDEX.
   MOVE 32000 TO LAAST.
   MOVE WORKING-INDEXES TO
       CURRENT-INDEXES (SESSION-INDEX).

Задаваме на стека на работните указатели нули. След това се инициализира набор от работни указатели, като указателят FURST сочи първият елемент от данните, а LAAST сочи последния. Задаването на 1 за HOW-RETURN показва, че това е нова итерация на кода на Quicksort и трябва за започнем от началото. SESSION-INDEX се задава 1 (това е първият индекс) и данните се зареждат в стека.

Кодът за всяка итерация е :

CALL-QUICKSORT.
   MOVE CURRENT-INDEXES (SESSION-INDEX) TO
       WORKING-INDEXES.
   IF HOW-RETURN = 2 GO TO DO-PIVOT-TO-LAST.
   IF HOW-RETURN = 3 GO TO SEE-IF-WE-ARE-ALL-DONE.
   IF FURST NOT <>

Първо извлича данни от стека и ги слага в WORKING-INDEXES. Стойността на SESSION-INDEX определя кои данни да се извлекат. Контрола върху повтарящия се код се извършва чрез стойностите на SESSION-INDEX и HOW-RETURN .

Програмната логика е :

SPLIT-THE-LIST.
   MOVE TABLE-ENTRY (FURST) TO PIVOT-VALUE.
   MOVE FURST TO LEFT-INDEX.
   COMPUTE RIGHT-INDEX = LAAST + 1.
   PERFORM WITH TEST AFTER UNTIL
           RIGHT-INDEX <= LEFT-INDEX         PERFORM WITH TEST AFTER UNTIL             TABLE-ENTRY (LEFT-INDEX) >= PIVOT-VALUE
           ADD 1 TO LEFT-INDEX
       END-PERFORM
       PERFORM WITH TEST AFTER UNTIL
           TABLE-ENTRY (RIGHT-INDEX) <= PIVOT-VALUE             SUBTRACT 1 FROM RIGHT-INDEX         END-PERFORM         IF LEFT-INDEX <>

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

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

Подготвянето на Quicksort за разглеждане на лявата и дясната част е :

DO-FIRST-TO-PIVOT.
   MOVE 2 TO HOW-RETURN.
   MOVE WORKING-INDEXES TO
       CURRENT-INDEXES (SESSION-INDEX).
   COMPUTE LAAST = PIVOT - 1.
   MOVE 1 TO HOW-RETURN.
   ADD 1 TO SESSION-INDEX.
   MOVE WORKING-INDEXES TO
       CURRENT-INDEXES (SESSION-INDEX).
   GO TO CALL-QUICKSORT.

*
DO-PIVOT-TO-LAST.
   MOVE 3 TO HOW-RETURN.
   MOVE WORKING-INDEXES TO
       CURRENT-INDEXES (SESSION-INDEX).
   COMPUTE FURST = PIVOT + 1.
   MOVE 1 TO HOW-RETURN.
   ADD 1 TO SESSION-INDEX.
   MOVE WORKING-INDEXES TO
       CURRENT-INDEXES (SESSION-INDEX).
   GO TO CALL-QUICKSORT.

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

SEE-IF-WE-ARE-ALL-DONE.
    SUBTRACT 1 FROM SESSION-INDEX.
    IF SESSION-INDEX > 0
        GO TO CALL-QUICKSORT.
    STOP RUN.

Каква е разликата между типичното сортиране, където всеки елемент се сравнява с всички останали, и рекурсивният Quicksort? При големи обеми от данни разликите при сортирането за забележителни. Рекурсивният Quicksort може да спести минути или дори часове, когато се сортират големи обеми от данни. Рекурсивния процес е много мощен и има много употреби в математическия анализ. Quicksort е само едно от приложенията на този тип програмна логика.

Заключение

Този пример показва употребата на симулиран рекурсивен Quicksort в Cobol, но този процес може да бъде извършен в много други езици като C и Pascal. Използването на рекурсивен Quicksort може дмного да намали времето за сортиране на големи обеми от данни, което е полезно, независимо от програмния език.

Earl е старши консултант в Keane Inc., фирма за ИТ консултации в Бостън