рагмент стека для B поміщається покажчик клітинки у фрагменті стека для A, в яку належить помістити значення цієї функції (Адреса значення). p> 2. Управління передається першому оператору процедури B. p> 3. При завершенні роботи процедури B управління передається процедурі A за допомогою наступної послідовності кроків: (а) адреса повернення витягується з вершини стека; (б) якщо B - функція, то її значення запам'ятовується в комірці, продиктованої покажчиком на адресу значення; (в) фрагмент стека процедури B вилучають із стека, в вершину ставиться фрагмент процедури A; (г) виконання процедури A поновлюється з команди, зазначеної в адресі повернення.
При виклику підпрограмою самої себе, тобто в рекурсивному випадку, виконується та ж сама послідовність дій.
Цей прийом робить можливою легку реалізацію рекурсивних процедур. Коли процедура викликає сама себе, то для всіх її локальних змінних виділяється нова пам'ять в стеку, і вкладений виклик працює з власним уявленням локальних змінних. Коли вкладений виклик завершується, займана його змінними область пам'яті в стеку звільняється і актуальним стає уявлення локальних змінних попереднього рівня. За рахунок цього в мовах PASCAL і C будь-які процедури і функції можуть викликати самі себе. У мові PL/1, де за замовчуванням прийняті інші способи розміщення локальних змінних, рекурсивна процедура повинна бути визначена з описателем RECURSIVE - тільки тоді її локальні змінні будуть розміщуватися в стек.
Рекурсія використовує стек в прихованому від програміста вигляді, але все рекурсивні процедури можуть бути реалізовані і без рекурсії, але з явним використанням стека. Приклад подібної В«розгорненняВ» рекурсії можна побачити в реалізації швидкого сортування Хоара через стек [21].
Один прохід сортування Хоара розбиває вихідне безліч на два множини. Межі отриманих множин запам'ятовуються в стеку. Потім з стека вибираються кордону, що знаходяться у вершині, і обробляється безліч, визначається цими кордонами. У процесі його обробки в стек може бути записана нова пара кордонів і т.д. При початкових установках в стек заносяться кордону вихідного безлічі. Сортування закінчується з спустошенням стека. p> Хочеться зауважити, що для сортування використовується саме реалізація на основі масиву. Дійсно, основна вимога до сортування - швидкість, а операції з масивом виконуються значно швидше, ніж перехід по вказівниками. Пам'ять же, необхідна під стек в даному алгоритмі -, константа мала, так що для сортування 1 Гб інформації потрібно лише близько 1 Кб стек.
Тут перед нами постає питання практичної оцінки складності алгоритму, яка тепер залежатиме і від використовуваної обчислювальної системи і від програмних механізмів. Аналіз трудомісткості рекурсивних реалізацій алгоритмів, очевидно, пов'язаний як з кількістю операцій, виконуваних при одному виклику функції, так і з кількістю таких викликів. Графічне представлення породжуваної даними ...
