69103

Рекурсія. Рекурсивні означення та підпрограми

Лекция

Информатика, кибернетика и программирование

Кожний ідентифікатор у програмі характеризується областю дії імені або областю видимості. Область видимості ідентифікатора - це область программ, в якій можна посилатися на даний ідентифікатор. У мові Раsсаl припускається довільна послідовність і кількість розділів, в яких іменуються ті чи інші об’єкти.

Украинкский

2014-09-30

104.5 KB

0 чел.

Лекція 12. Тема:Рекурсія. Рекурсивні означення та підпрограми.

                           Приклади рекурсивних програм. Випереджальне оголошення процедур і функцій.

План:

  1.  Локалізація імен

     2. Різновиди параметрів

     3. Процес виклику підпрограми. Програмний стек.

     4. Процедурні типи. Підпрограми як параметри

1. Локалізація імен

Кожний ідентифікатор у програмі характеризується областю дії імені або областю видимості. Область видимості ідентифікатора - це область программ, в якій можна посилатися на даний ідентифікатор. У мові Раsсаl припускається довільна послідовність і кількість розділів, в яких іменуються ті чи інші об’єкти. Такі розділи можуть належати до різних програмних блоків: процедур, функцій або самих програм. Область дії іменування поширюється від точки, де ідентифікатор було оголошено, до кінця блоку, в якому це оголошения відбулося.

Щойно був сформульований універсальний принцип визначення області видимості ідентифікатора. Застосуємо цей принцип для визначення областей дій імен, шо оголошені в підпрограмах. Отже, процедури та функції можуть містити власні розділи оголошень констант, змінних, інших процедур і функцій. Усі ідентифікатори, оголошені всередні процедури або функції, є локалізованими в ній, тобто вони є невидимими зовні підпрограми. Такі ідентифікатори називаються локальними. Зокрема, локальними є будь-які параметри підпрограми. Мета локалізації змінних полягає в тому, щоб надати доступ лише до тих даних, які потрібні для формулювання задач, що їх розв'язують процедури або функції, і зробити в такий спосіб постановки обчислювальних задач незалежними від методів їх розв'язань.

Крім власних локальних імен всередині підпрограми видимими є й деякі іденифікатори верхнього рівня, тобто ідентифікатори, що їх було оголошено у «зовнішніх» програмних блоках. Ці ідентифікатори називаються глобальными. Зазначимо, що з глобальних імен видимими є лише ті, оголошення яких розташовані до оголошення даної підпрограми.

Ім'я, локалізоване у підпрограмі, може збігатися з будь-яким глобальним именем, оскільки цим іменам зіставляються різні ділянки оперативної пам'яті. У такому випадку локальне ім'я перекриває глобальне та робить його недоступним у підпрограмі. Імена локальних змінних можуть також збігатися з іменами локальних змінних інших підпрограм, такі змінні є абсолютно незалежними, хоч і мають однакові імена.

УВАГА

Різні об'єкти можна іменувати однаково, але в різних програмних блоках. В оголошеннях тієї самої підпрограми або програми усі імена мають бути різними.

Приклад 4.4.

Наведемо програму, в якій використовуються однакові імена для різних об'єктів. Результати роботи програми зображено на рис. 4.5.

program ex4_4;   {демонстрація областей дії ідентифікаторів}

var i: integer;    {глобальна змінна, її область дії – уся програма}

{--------------------процедури--------------------}

procedure p1;

  procedure p2;   {внутрішня відносно р1 процедура}

  var i: integer;   {локальна змінна, її область дії – процедура р2}

  begin

    i:=2;    {і, що оголошена у процедурі р2}

    writeln(‘from p2:’, i);

  end;

begin

  i:=1;     {і, що оголошена в ex4_4}

  p2;

  writeln(‘from p1:’, i);

end;

{--------------------основна програма--------------------}

begin

writeln(‘display scope variables’);

i:=0;     { і, що оголошена в ex4_4}

p1;

writeln(‘from ex4_4:’, i);

end.

У програмі ex4_4 глобальну змінну і ініціалізовано значенням 0. Оскільки в процедурі р1 жодних змінних не оголошено, то використаний в її операторній частині ідентифікатор і посилатиметься саме на глобальну змінну і.  Натомість, у процедурі р2 локальна змінна і перекриває глобальну і тому присвоєння і:=2 жодним чином не впливає на значения глобальної змінної.

Процедура р1 програми ех4_4 модифікує значения глобальної змінної і. Модифікація глобальннх змінних у підпрограмі називається побічним ефектом підпрограми.  Цей ефект вважається явним, якщо він виникає внаслідок виконання операції присвоювання, та неявним, якщо глобальне ім’я вказане у виклику підпрограми як значения параметра, оголошеного зі словом var. Модифікація глобальних змінних у підпрограмах слід уникати, оскільки її наслідки у загальному випадку передбачити важко.

2. Різновиди параметрів

Область оперативної пам'яті, що її використовує програма, поділяється на сегмент коду, сегмент даних та сегмент стеку. В сегмент коду (64 Кбайт) зберігаються команди програми, в сегменті даних (64 К6айт) — значення глобальних змінних, а в сегменті стеку — значення локальних змінних і параметрів підпрограм.

Параметри, що їх імена вказані в заголовку підпрограми, називаються формальними, оскільки під час компіляції їх оголошення вони не прив’язуються до жодного реального об’єкта. Натомість значення, що замінюють формальні параметри під час виклику підпрограми, називаються фактичними параметрами або аргументами. Під час виклику підпрограми між її фактичними та формальними параметрами встановлюється однозначна відповідність щодо кількості параметрів, їх типів та порядку згадування.

Формальні параметри поділяються на параметри-значення, параметри-змінні, параметри-константи та нетипізовані параметри-змінні.

Якщо параметр оголошено як параметр-значення, то під час виклику підпрограми обчислюється значення відповідного аргументу і копія отриманого результата передається підпрограмі. Зміна параметрів-значень усередині підпрограми не впливає на значення змінних, що могли бути вказані як аргументи підпрограми, оскільки змінюються їх копії.

Якщо параметр оголошено як парамет-змінну, то до підпрограми передається покажчик на параметр, тобто адреса певної змінної в сегменті даних оперативної пам’яті. Тому підпрограма виконує дії над значеннями параметрів-змінної, а не над їх копіями, і модифікація параметра-змінної приведе до модифікаціїзмінної, що була вказана як аргумент в операторі виклику підпрограми. Параметри-змінні можна використовувати у процедурах з метою повернення отриманих під час виконання підпрограми значень до точки її виклику. У заголовку підпрограми перед іменем параментра-змінної необхідно записати зарезервоване слово var.

Для параметра-константи копія значення відповідного аргументу під час звернення до підпрограми не створюється. Значення такого параметра не можна змінювати у тілі підпрограми. Параметри-константи дозволяють зекономити оперативну пам’ять та підвищити швидкість виконання програми, оскільки їх використання зменшує витрати часу на виклик підпрограми. У заголовку підпрограми перед іменем параметра-константи треба записати зарезервоване слово const.

Якщо формальний параметр є нетипізованим параметром-змінною, то відповідний йому фактичний параметр може бути покажчиком на змінну довільного типу, тобто адресою сегмента даних оперативної пам’яті, де зберігаються значення, тип яких не відомий. У заголовку підпрограми перед іменем параметра-змінної слід записати слово var, але не треба вказувати тип параметра.

УВАГА

Немає потреби використовувати параметри-змінні в заголовках функцій, оскільки функція повертає значення за своїм іменем, а не за допомогою параметра.

3. Процес виклику підпрограми. Програмний стек.

Нагадаємо, що під час виклику підпрограми їй передається керування. По завершенні роботи вона повертає керування програмі, що її викликала, у ту точку, з якої виклик було здійснено. Перша команда підпрограми називається точкою входу, а адреса такої команди – адресою точки входу. Оператор, що продовжує виконання програми по завершенні роботи підпрограми, називається точкою повернення із підпрограми. Точка повернення із процедури – це наступний за її викликом оператор або умова завершення чи продовження циклу, якщо виклик процедури був останнім оператором в тілі циклу. точкою повернення із функції може бути як оператор, так і окремий операнд певного виразу. У будь-якому разі точка повернення фізично є адресою в сегменті коду оперативної пам’яті.

Коли здійснюється виклик підпрограми, точка повернення з неї запам’ятовується і зберігається до завершення роботи цієї підпрограми. Для збереження точки повернення використовується ділянка оперативної пам’яті. Крім того, під час виклику підпрограми певні ділянки пам’яті зіставляються з її параметрами та локальними змінними. Сукупність усіх цих ділянок пам’яті називаються локальною пам’яттю підпрограми. Якщо підпрограма є функцією, то до її локальної пам’яті додається ділянка для збереження значення, яке функція повертає. Ця ділянка ставиться у відповідність до імені функції.

Перш ніж розпочнеться виконання операторів тіла підпрограми, для неї виділяється локальна пам’ять і в цій пам’яті записується точка повернення. Потім обчислюються значення тих аргументів, що відповідають параметрам-значенням. Ці значення копіюються в локальну пам’ять, і таке копіювання називається підстановкою аргументів за значенням. Якщо процедура має параметр-змінну, то аргументом може бути лише ім’я змінної. Жодного обчислення її значення, тобто розіменування аргументу, не відбувається, а до локальної пам’яті записується адреса змінної-аргументу. Ця адреса ставиться у відповідність до параметра-змінної. Таке зіставлення називається підстановкою аргументу за посиланням, або за адресою.

Підсумовуючи сказане вище, сформулюємо алгоритм виклику підпрограми.

Для підпрограми виділяється локальна пам’ять.

В локальній пам’яті обчислюється й запам’ятовується точка повернення з підпрограми.

Обчислюються значення аргументів, що відповідають параметрам-значенням, і адреси аргументів, що відповідають параметрам-змінним. Здійснюється підстановка аргументів.

Виконуються оператори тіла підпрограми. Якщо підпрограма є функцією, то у локальній пам’яті запам’товується значення, яке функція повертає.

Здійснюється повертання до підпрограми. Якщо програма є функцією, то з локальної пам’яті підпрограми до сегмента даних копіюється значення, яке функція повертає. Управління передається команді, що адресується точкою повернення з підпрограми.

Ділянка оперативної пам’яті, що була задіяна під локальну пам’ять, вважається вільною.

Виконання основної програми починається після завантаження її коду в оперативну пам’ять комп’ютера. При цьому відбувається виділення пам’яті для її змінних. Ці зміння доступні з програми протягом усього часу її виконання, і тому називаються статичними. Область пам’яті, що виділяється під програму та її змінні, також називається статичною. Із локальними іменами і параметрами-значеннями підпрограм, як правило, зіставляються ділянки іншої області пам’яті – автоматичної. Під час виконання викликів підпрограм пам’ять виділяється та звільняється автоматично, без явних вказівок у програмі.

Виділення та звільнення ділянок пам'яті під час виконання викликів підпрограм відбувається за принципом «останнім прийшов - першим пішов» (з англійської  «Last In – First Out» або скорочено LIFO). Якщо складати книжки в стопку і брати їх тільки зверху, то книжка, що потрапила у стопку останньою, забирається першою. Така стопка називається стеком (stack), а кладуть і забирають книжки за принципом LIFO. Тому автоматична пам'ять, що виділяється для підпрограм, програм називається ще программним стеком.

У програмному стеку, як і у стопці книжок, доступним є завжди тільки один елемент - верхній, що зветься вершиною стеку. Внутрішній стан стеку під час виконання програми однозначно визначається функціями Sseg, що повертає адресу сегмента стеку, та Sptr, яка повертає зсув покажчика вершини стеку в межах його сегмента. За замовчуванням розмір стеку дорівнює 16 Кбайт, його можна змінювати за допомогою директиви комтлятора {$М} – Memory Allocation Sizes Directive.

Приклад 4.5.

На прикладі програми ех4_5 продемонструємо принцип використання різних типів параметрів підпрограм та роботу стеку.

program ех4_5;     {робота стеку}

vаr а, b: integer;     {глобальні змінні}

function f (x: integer): integer;   {х - параметр-значення}

begin

  х:= х+1;

  f:=x;

end;

function g (var x: integer):integer;   {х - параметр-змінна}

begin

  x:=x div 2;

  g:=x;

end;

begin       {основна програма}

  a:=12;

  b:=f(g(a));      {виклик функцій}

  writeln (‘a=’, a, ‘b=’,b);

end.

Перед виконанням програм покажчики на функції, а також глобальні та локальні змінні  ще не визначені. Як тільки програма починає виконуватися, визначаються покажчики на функції f та g, що є адресами в сегменті коду. Це – точки входу до функцій. Цілочислові значения глобальних змінних на початку роботи програми ініціалізуються нулями, а перший оператор програми надає змінній а значення 12. Виконання оператора     b:=f(g(a)) починається з виклику функції g(a), або g(12). Її адресу, як і адресу аргументу а, буде записано до стеку. Оскільки аргументом а заміщується параметр-змінна х функції g, то, коли функція g надає змінній х значения 6, це значения буде надане і змінній а. Оператор g: =х здійснює присвоєння значення 6 імені функції g. Точка повернення з функції g(12) є точкою входу до функції f(6), в якій знову змінюється значения локальної змінної х. Це значення стає рівним 7 і присвоюється імені функції f. Точкою повернення з функції f є оператор присвоєння значения 7 змінній b. Отже, в результаті роботи програми змінна а набуде значения 6, а змшна b – значення 7. Значення змінних та вміст стеку під час виконання програми можна переглядати у вікнах Watches і CallStack, що відкриваються за допомогою меню Debug.

Таблиця 4.5. Стан оперативної пам’яті під час виконання програми ех4_5

Оператор, що виконується

Глобальна змінна а

Глобальна змінна b

Локальна змінна х

Стан вікна перегляду стеку

До початку виконання програми

Unknown identifiers

Unknown identifiers

Begin

0

0

Unknown identifiers

ex4_5

a:=12;

12

0

Unknown identifiers

ex4_5

b:=f(g(12))

12

0

12

g(12)

ex4_5

x:=x div 2; g:=x;

6

0

6

g(6)

ex4_5

x:=x+1; f:=x;

6

0

7

f(7)

ex4_5

Writeln(‘a=’,a, ‘b=’,b);

end.

6

7

Unknown identifiers

ex4_5

Після завершення програми

6

7

Unknown identifiers

4. Процедурні типи. Підпрограми як параметри

Основне призначення процедурних типів полягає в тому, щоб надати програмісту можливість передавати процедури або функції як фактичні параметри під час виклику інших процедур або функцій. Потребу у таких параметрах продемонструємо на прикладі задачі табулювання математичних функцій на заданому відрізку (приклад 4.6).

Приклад 4.6.

Припустимо, що треба надрукувати таблиці значень декількох функцій на відрізку [a, b] із кроком h. Нехай це буде многочлен х3-х+1, степенева функція ех-3 та тригонометрична функція sin х. Цю задачу можна було 6 ефективно розв’язати за допомогою процедури, що виводить значення довільної функції на заданому відрізку. Зрозуміло, що сама функція має 6ути аргументом цієї процедури, тобто процедура повинна мати параметр типу «функція». Оскільки параметри підпрограм оголошуються у вигляді пар                         <ім'я параметра>:<ідентифікатор типу>, то типу «функція» треба надати певний ідентифікатор, що можна зробити лише через оголошення цього типу в розділі type. Існує чотири варіанти синтаксису оголошення процедурного типу, наведемо їх:

tуре

<ідентифікатор типу> = procedure (<оголошення параметрів>);

<ідентифікатор типу> = procedure;

<ідентифікатор типу> = function (<оголошення параметрів>): <тип>;

<ідентифікатор типу> = function: <тип>;

Тут <ідентифікатор типу> - ім’я процедурного типу; procedure та function – зарезервовані слова; <оголошення параметрів> - список параметрів (його синтаксис збігається із синтаксисом списків параметрів в оголошеннях підпрограм); <тип> - довільний неструктурований тип значення, що його повертає функція. Імена підпрограм в оголошеннях процедурного типу не зазначаються.

Повернімося до задачі табулювання математичних функцій на певному відрізку. Йдеться про функцію однієї дійсної змінної. Всі такі функції мають один параметр типу real та повертають значення типу real, а отже, можуть розглядатись як функції одного процедурного типу. Оголосимо цей тип:

type func = (x: real): real;

 Підпрограми, що є параметрами процедур, слід компілювати з використанням дальньої моделі пам’яті. Модель пам’яті визначає спосіб виклику підпрограм. Ближня модель припускає виклик підпрограм лише в межах одного сегмента коду. Дальня модель пам’яті дозволяє звертатися до процедур і функцій з будь-якого сегмента і використовується не лише в оголошеннях підпрограм-аргументів, а й в оголошеннях підпрограм, що викликаються з інших модулів. Дальня модель можна встановити за допомогою ключового слова far, що вводиться після заголовка підпрограми. Наприклад:

function <ім’я>(<список параметрів>) : <тип>; far;

Встановити дальню модель можна також за допомогою директиви компілятора Force far calls, що записується в програмі у вигляді коментарів {$F+} та {$F-}. Коментар {$F+} встановлює режим компіляції в дальній моделі, а коментар {$F-} скасовує цей режим. Наприклад,

{$F+}

function <ім’я>(<список параметрів>) : <тип>;

begin

<тіло функції>

end;

{$F-}

Перед тим як навести код программ ех4_6, що здійснює табулювання функцій, зауважимо, що в мові Раsса1 не можна використовувати стандартні математичні функції як аргументи підпрограм. Якщо в цьому виникає потреба, слід написати власну «функцію-оболонку» з іншим ім'ям. Наприклад, у програмі ех4_6 для стандартної математичної функції sin використовується функція-оболонка Sinus. Результат роботи програми табулювання функції зображено на рис. 4.6.

program ex4_6;     {табулювання функцій}

type func=function (x: real): real;   {процедурний тип}

var lower, upper, step: real;    {межі відрізка, крок}

{--------------------------------- поліном ---------------------------------}

function Polynom(x: real): real; far;

begin

  Polynom:=sqr(x)*x-x+1;

end;

{--------------------------------- степенева функція ---------------------------------}

function Exponent(x: real): real; far;

begin

  Exponent:=Еxp(x-3);

end;

{--------------------------------- синус ---------------------------------}

function Sinus(x: real): real; far;

begin

  Sinus:=sin(x-3);

end;

{----------------------- процедура табулювання функції f ----------------------}

procedure Print(a, b, h: real; f: func; s: string);

{а – нижня межа відрізка, b – верхня межа, h – відстань між точками,  f – ім’я функції, s – текстова назва функції}

var x: real;     {значення аргументу f, параметр циклу}

begin

  writeln (‘--------------------’);    {виведення заголовка}

  writeln (‘  x  |  ‘, s);      {таблиці}

  writeln (‘--------------------’);

  x:=a;

  while x<b do     {поки не досягнуто правої межі відрізка}

  begin

     write (x:6, ‘ | ’);

     write (f(x):10:6);     {обчислити і вивести значення f(x)}

     writeln;

     x:=x+h;       {збільшити значення аргументу}

  end;

end;

{--------------------------------- основна програма ---------------------------------}

begin

  writeln (‘enter lower, upper bounds and step’);

  readln (lower, upper, step);

  {}

  Print (lower, upper, step, Polynom, ‘x^3-x+1’);

  {}

  Print (lower, upper, step, Exponent, ‘e^(x-3)’);

  {}

  Print (lower, upper, step, Sinus, ‘sin (x)’);

end.

Контрольні питання

  1.  Локалізація імен

     2. Різновиди параметрів

     3. Процес виклику підпрограми. Програмний стек.

     4. Процедурні типи. Підпрограми як параметри


 

А также другие работы, которые могут Вас заинтересовать

54158. Математика в оточуючому світі 33.5 KB
  Відстань між пристанями А і В дорівнює 40 км. Від А до В за течією річки рухається моторний човен, власна швидкість якого 18 км/год., а від В до А – інший моторний човен, власна швидкість якого 16 км/год. При зустрічі виявилось, що перший човен йшов 1 год., а другий – 1,5 год. Знайдіть швидкість течії річки.
54159. Неможливо бути математиком, не будучи в той же час поетом у душі 92 KB
  Мета: Показати учням звязок математики з літературою, формувати філософське сприймання світу як органічне поєднання духовності і науковості; Розширити кругозір учнів, збагатити їх інтелект, виховувати в них свідоме ставлення до одержання знань.
54160. НАЙРОЗУМНІШИЙ. Математична гра для учнів 5-6 класів 85.5 KB
  Модуль числа це: Завжди невід’ємна величина; Завжди від’ємна величина; Завжди число. Як називається сота частина числа відсоток; ар; міліметр. Натуральні числа. Квадрат числа.
54161. Математика – цариця наук 102.5 KB
  Мета: активізація пізнавальної діяльності учнів; розвиток логічної та загально математичної культури учнів; тренування уваги, пам’яті учнів; підвищення інтересу до вивчення математики.
54162. Інтегрований підхід на уроках математики 1.48 MB
  Львова Підготувала учитель математики вища кв. Для математики спорідненими є фізика чи інформатика а протилежними – християнська етика музика історія основи здоров’я і т. Працюючи багато років вчителем математики я зауважила що досягнути кращих результатів з математики можна поєднуючи її з основами християнської етики. Головним завданням математики є забезпечення міцного і свідомого оволодіння учнями системою математичних знань і умінь необхідних у професійної освіти.
54163. Додавання та віднімання дробів з різними знаменниками 807.5 KB
  Тема уроку: розв’язання вправ за темою Додавання та віднімання дробів з різними знаменниками. Розвивальна мета: розвивати практичні вміння та навички співнавчання та взаємонавчання; розвивати мислення; самостійність. Доданок Доданок Сума 27 Готуючись до уроку я розв’язала ваше домашнє завдання але потім картки впали і переплутались. Розв’язок.
54164. Розвязування задач на відсотки 195 KB
  Крім того, велика частина інформації, яку ми отримуємо, подана у вигляді відсотків. Кожному фахівцю у всіх сферах людської діяльності треба мати справу з відсотками. Отже, наша задача - мати міцні знання про відсоток.Доповідь учнів про історію виникнення поняття відсотка.
54165. Додатні та від’ємні числа. Додавання та віднімання раціональних чисел 246 KB
  Додатні та від’ємні числа. Сьогодні ми продовжимо працювати з додатними і від’ємними числамивдосконалювати вміння додавати...
54166. Означення квадратного рівняння. Неповні квадратні рівняння та їх розв’язки 747.5 KB
  Мета: домогтися свідомого розуміння учнями означення квадратного рівняння зведеного квадратного рівняння неповного квадратного рівняння назви коефіцієнтів квадратного рівняння; сформувати первинні вміння формулювати означення квадратного рівняння та його видів зведеного та неповного визначати коефіцієнти квадратного рівняння та за ними визначити вид квадратного рівняння підготувати учнів до сприйняття розв’язування неповних квадратних рівнянь. Чи рівносильні рівняння: а 3х – 2 = х...