загрузка...
загрузка...
На головну

Питання Рекурсія. Рекурсивні функції.

  1.  C. Питання 41. Показники стану, руху і використання основних фондів
  2.  I. ДО ІСТОРІЇ ПИТАННЯ
  3.  I. Розбір основних питань теми.
  4.  I. Лютнева революція і національне питання
  5.  II. Жовтнева революція і національне питання
  6.  III. Приблизний перелік контрольних питань для самостійної роботи
  7.  IV. Приблизний перелік питань до заліку

Рекурсія - процес повторення елементів самоподібним чином. Наприклад, якщо два дзеркала встановити один навпроти одного, то виникають в них вкладені відображення суть одна з форм нескінченної рекурсії. Термін «рекурсія» використовується в різних спеціальних галузях знань - від лінгвістики до логіки, але найбільш широке застосування знаходить в математики та інформатики. В математики та інформатики рекурсія має відношення до методу визначення функцій: рекурсивно задана функція в своєму визначенні містить себе, зокрема, рекурсивної є функція, задана рекуррентной формулою. Таким чином, можна одним виразом дати нескінченний набір способів обчислення функції, визначити безліч об'єктів через самого себе з використанням раніше заданих окремих ухвал.

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

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

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

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

Є спеціальний тип рекурсії, званий «хвостовій рекурсією». Інтерпретатори і компілятори функціональних мов програмування, що підтримують оптимізацію коду (вихідного або виконуваного), автоматично перетворять хвостову рекурсію до ітерації, завдяки чому забезпечується виконання алгоритмів з хвостової рекурсією в обмеженому обсязі пам'яті. Такі рекурсивні обчислення, навіть якщо вони формально нескінченні (наприклад, коли за допомогою рекурсії організовується робота командного інтерпретатора, що приймає команди користувача), ніколи не призводять до виснаження пам'яті. Однак, далеко не завжди стандарти мов програмування чітко визначають, яким саме умовам повинна задовольняти рекурсивна функція, щоб транслятор гарантовано перетворив її в ітерацію. Одне з рідкісних винятків - мова Scheme (діалект мови Lisp), опис якого містить всі необхідні відомості.

Будь-яку рекурсивную функцію можна замінити циклом і стеком.

12 питання Масиви в мові Паскаль.

Поговоримо про масивах в Паскалі. Масив являє собою послідовність елементів одного типу. Кожен масив характеризується наступними особливостями:

кожен компонент, що входить в масив, можна позначити явно і до нього встановлюється прямий доступ,

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

Щоб позначити компонент масиву, використовують ім'я змінної (змінної-масиву), а також індекси, які вказують необхідний елемент. Індекс може мати тільки порядковий тип (за винятком longint). Часто використовують інтервальний тип (відрізок, діапазон). Наведемо опис типу масиву:

ім'я типу - правильний ідентифікатор;

список індексів - сукупність одного, або декількох індексних типів, які відокремлюються один від одного комами;

тип - всякий тип даних.

При роботі з програмою в Паскалі масиви можна або ввести, так і виводити, лише по одному елементу.

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

Ось приклад програми на одновимірний масив: введення і виведення.

Визначення змінної в якості масиву можливо при її описі без початкового опису типу використовуваного масиву:

У разі, коли масиви a і b описуються наступним чином:

то у змінних a і b буде різний тип. Щоб забезпечити сумісність типів необхідно описати змінні через початкове опис типу. Якщо масиви мають ідентичні типи, то у вихідному коді програми один масив можна привласнити іншому. Відповідно до цього значення змінних одного масиву привласнюються значенням елементів іншого масиву. Для масивів в Паскалі не визначені операції відносини. Порівняння двох масивів можливо тільки по кожному елементу.

Багатовимірні масиви - масиви, кожним елементом яких є масиви.

Уявімо приклади опису двовимірних масивів.

Приклад 1.

Приклад 2.

Глибина вкладеності масивів представляється довільній, внаслідок цього розмірність масиву (число елементів, що входять до складу списку індексних типів) не обмежена, але не може перевищувати 65520 байт.

При роботі з багатовимірними масивами ми організуємо вкладені цикли. Наприклад, для заповнення двовимірного масиву (матриці) випадковими числами користуються такими командами:

Щоб красиво вивести на екран двовимірний масив, використовуйте конструкцію виду:

 




 Питання Коротка історія розвитку обчислювальної техніки (ОТ). |  Питання Поняття про машинному мовою |  Питання 3 Мова Паскаль. Структура Паскаль-програми. |  Питання Типи даних в мові Паскаль. |  Команда введення (зчитування) з клавіатури значення змінних під час роботи програми |  Питання Об'єктно-орієнтоване програмування. |  Питання Основні етапи моделювання. |  Питання 18. Структура і архітектура ЕОМ. |  Питання Процесор. |  Питання Внутрішня і зовнішня пам'ять |

загрузка...
© um.co.ua - учбові матеріали та реферати