ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Юрист по наследству
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

         
     
    Рекурсія
         

     

    Інформатика, програмування

    Рекурсія.

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

    Наприклад, рекурентні співвідношення

    xi = xi-2 + xi-1, де x1 = 1, x2 = 2

    задає правило обчислення так званих чисел Фібоначчі.

    Іншим прикладом рекурентних співвідношень можуть служити правила обчислення членів арифметичної прогресії

    an 1 = an + d , Де d - різниця прогресії,

    або геометричній прогресії

    an +1 = q an, де q - коефіцієнт прогресії.

    Ця ідея рекурсії реалізована і в мові Pascal.

    Визначення 16.1. Функція (процедура) на мові Pascal називається рекурсивної, якщо в ході свого виконання вона звертається до самої себе.

    Наприклад, ми можемо визначити обчислення функції n!
    рекурсивно. Як це зробити, показано на малюнку 16.1

    function Factorial (n: integer): integer;

    begin if n> 0 then Factorial: = Factorial (n-1) * n

    else if n = 0 then Factorial: = 1

    else writeln ( 'значення n менше 0')

    end (Factorial)

    Рис. 16.1. Функція обчислення n! в рекурсивної формі.

    Розглянемо детальніше, як буде виконуватися звернення до цієї функції, напрмер, при n = 4.

    На малюнку 16.2 показаний процес обчислення для випадку Factorial (4).

                                   

    24                        

    Рис. 16.2. Обчислення функції Factorial (n) для n = 4.

    Спочатку утворюється так званий рекурсивний фрейм № 1 при n = 4. Для цього фрейму відводиться пам'ять і в ньому фіксуються всі значення змінних тіла функції при n = 4. Відзначимо, що в рекурсивної фреймі фіксуються значення всіх змінних функції, окрім глобальних.

    Потім відбувається виклик Factorial (n) при n = 3. Утворюється фрейм № 2, де фіксуються значення змінних тіла функції при n = 3. При цьому фрейм № 1 також зберігається в пам'яті. З фрейма № 2 відбувається звернення до Factorial (n) при n = 2. У результаті цього звернення утворюється фрейм № 3, де фіксуються значення змінних тіла функції при n = 2 і т.д. до тих пір, поки при черговому зверненні до функції Factorial умова n> 0 не прийме значення false.

    Це відбудеться в фреймі № 5. У цьому фреймі ми отримаємо значення Factorial = 1 і передамо це значення в фрейм № 4. Після цього фрейм № 5 буде знищений, так як звернення Factorial (n) при n = 0 буде виконано.

    У фреймі № 4 ми обчислимо значення Factorial (n) для n = 1. Після чого ми передамо це значення у фрейм № 3, а фрейм № 4 буде закрито, оскільки звернення до Factorial (n) при n = 1 буде закінчено.

    Так ми будемо згортати цю ланцюжок фреймів в послідовності, зворотній тій, в якій ми їх породжували, поки не звернемо фрейм № 1. Після чого обчислення функції буде закінчено.

    Рекурсія можлива не тільки в випадку функцій, але і процедур. Приклад рекурсії для процедур наведено на малюнку 16.3. Там показано опис рекурсивної процедури для роздруківки (виведення на друк) рядка символів в порядку, зворотному їх введенню.

    Procedure BackPrint;

    var символ: char;

    begin read (символ);

    if символ = EOL (EOL - End Of Line - спеціальне значення типу

    СHAR, відповідне закінчення введення)

    then writeln (); (перед початком виведення треба переконатися, що

    друкувати будемо з нового рядка)

    else begin BackPrint; write (символ) end

    end (Procedure)

    Рис 16.3. Приклад рекурсивної процедури.

    (Непряма рекурсія.) Ітерація і рекурсія.

    Неважко помітити схожість між циклічними конструкціями (повтореннями) і рекурсією. На малюнку показана 16.4 схема циклу виду while do і його рекурсивного аналога.        

    Цикл            

    Рекурсія             

    while Умова Циклу   

    do Тіло Циклу         

    Procedure Рекурсивний Цикл;   

    begin   

    if Умова Циклу   

    then   begin Тіло Циклу;   

    Рекурсивний Цикл   

      else (закінчення   рекурсії)   

      end     

    Рис. 16.4. Схема організації циклу виду while do

    і його рекурсивного еквівалента.

    Зверніть увагу, що в правій частині рис. 16.4 можливо зациклення! Треба бути дуже обережним і кожного разу, застосовуючи рекурсивну поцедуру або функцію, переконатися в їх коректне завершення. Розглянемо приклад. На малюнку 16.5 наведено алгоритм Евкліда, з яким ми познайомилися на лекції 1, для обчислення НОД (найбільшого загального дільника) у формі звичайної і рекурсивної функції на мові Pascal.

    Function НОД (a, b: integer): integer;           

    begin repeat   

    if a> b then a: = a-b   

    else b: = b-a   

    untile a = b;   

    НОД: = a   

    end            

    begin if a = b then НОД: = a;   

    if a> b then НОД: = НОД (ab, b);   

    else НОД: = НОД (ba, a);   

    end        

    Рис. 16.5. Циклічна і рекурсивна функції

    для обчислення НОД.

    Як видно з наведених прикладів на рисунках 16.1 і 16.5, ітерація, тобто цикл завжди може бути замінений його рекурсивним аналогом за схемою, наведеної на малюнку 16.4.

    З зворотним твердженням про заміну рекурсії итерацией все складніше. На малюнку 16.6 наведено приклад рекурсивної функції, де за схемою (рис. 16.4) рекурсію итерацией замінити не вдається.

    в інших випадках

    Рис. 16.6. Рекурсивна функція Аккермана.

    Способи повторного використання процедур і функцій.

    Отже, процес абстракції у формі процедури складається з трьох кроків:

    Іменування. Присвоїти рутинному алгоритму унікальне ім'я, яке потім будемо використовувати як ім'я відповідної процедури.

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

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

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

    Реалізувати вийшла абстракцію рутинного алгоритму або у формі процедури, або функції.

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

    Приєднання. Цей спосіб передбачає, що якщо у нас є процедура P1 c передумовою Q1 і постусловіем R1 і процедура P2 c перед-і c постусловіямі Q2 і R2 відповідно, (причому R1

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status