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

     

     

     

     

     

         
     
    Рекурсія
         

     

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

    Рекурсія

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

    Наприклад, наведене нижче визначення двійкового коду є рекурсивним:

    <двійковий код>:: = <двійкова цифра> | <двійковий код> <двійкова цифра>

    <двійкова цифра>:: = 0 | 1

    Тут для опису поняття були використані, так звані, металінгвістіческій формули Бекуса-Наура (мова БНФ); знак "::=" означає "за визначенням є ", знак" | "-" або ".

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

    Наведемо інші приклади рекурсивних визначень.

    Приклад 1. Класичний приклад, без якого не обходяться ні в одному оповіданні про рекурсії, - Визначення факторіалу. З одного боку, факторіал визначається так: n! = 1 * 2 * 3 *...* n. З іншого боку, Граничним умовою в даному випадку є n <= 1.

    Приклад 2. Визначимо функцію K (n), яка повертає кількість цифр у заданому натуральному числі n:

    Завдання. За аналогією визначте функцію S (n), яка обчислює суму цифр заданого натурального числа.

    Приклад 3. Функція C (m, n), де 0 <= m <= n, для обчислення біноміального коефіцієнта по такою формулою є рекурсивної.

    Нижче будуть наведені програмні реалізації всіх цих (і не тільки) прикладів.

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

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

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

    Begin Begin Begin

    P; оператори; оператори;

    оператори; P P;

    End; End; оператори

    End;

    рекурсивний підйом рекурсивний спуск і рекурсивний узвіз, і рекурсивний підйом

    Тут P -- рекурсивна підпрограма. Як видно з малюнка, дії можуть виконуватися або на одному з етапів рекурсивного звернення, або на обох відразу. Спосіб організації дій диктується логікою розробляється алгоритму.

    Реалізуємо наведені вище рекурсивні визначення у вигляді функцій і процедур на мові Pascal і у вигляді функцій на мові C.

    Приклад 1.        

    (Функція на Pascal)   

    Function   Factorial (N: integer): Extended;   

      Begin   

      If N <= 1   

      Then Factorial: = 1   

      Else Factorial: = Factorial (N-1) * N   

      End;                  

    (Процедура на Pascal)   

    Procedure Factorial (N: integer; Var   F: Extended);   

    Begin   

      If N <= 1   

      Then F: = 1   

      Else Begin Factorial (N-1, F); F: = F * N End   

    End;                  

    /* Функція на C */   

    double Factorial (int N)   

      (   

      double F;   

      if (N <= 1) F = 1.; else F = Factorial (N-1) * N;   

      return F;   

      )     

    Приклад 2.        

      (Функція на Pascal)   

    Function K (N: Longint): Byte;   

    Begin   

      If N <10   

      Then K: = 1   

      Else K: = K (N div 10) +1   

    End;                  

    (Процедура   на Pascal)   

    Procedure K (N: Longint; Var Kol: Byte)   

    Begin   

      If N <10   

      Then Kol: = 1   

      Else Begin K (N Div 10, Kol); Kol: = Kol 1 End;   

    End;                  

    /*   Функція на C */   

    int K (int N)   

    (int Kol;   

      if (N <10) Kol = 1; else Kol = K (N/10) 1;   

      return Kol;   

    )     

    Приклад 3.        

      (Функція на Pascal)   

    function C (m, n: Byte): Longint;   

    Begin      

      If (m = 0) or (m = n)   

      Then C: = 1   

      Else C: = C (m, n-1) + C (m-1, n-1)   

    End;                  

    (Процедура на Pascal)   

    Procedure C (m, n: Byte; Var R: Longint);   

    Var R1, R2: Longint;   

    Begin   

      If (m = 0) or (m = n)   

      Then R: = 1   

      Else Begin   

    C (m, n-1,   R1);   

    C (m-1, n-1, R2);   

    R: = R1 + R2   

    End;   

    End;                  

    /* Функція на C */   

    int C (int m, int n)   

    (int f;   

    if (m == 0 | | m == n) f = 1; else f = C (m, n-1) + C (m-1, n-1);   

    return f;   

    )     

    Приклад 4. Обчислити суму елементів лінійного масиву.

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

    (Програма   на мові Pascal)   

    Program Rec2;   

    Type LinMas = Array [1 .. 100] Of Integer;   

    Var A: LinMas;   

      I, N: Byte;   

    (рекурсивні функції)   

    Function Summa (N: Byte; A: LinMas):   Integer;   

    Begin   

      If N = 0 Then Summa: = 0 Else Summa: = A [N] + Summa (N - 1, A)   

    End;   

    (Основна   програма)   

    Begin   

    Write ( 'Кількість елементів масиву?');   ReadLn (N); Randomize;   

      For I: = 1 To N Do   

      Begin   

      A [I]: = -10 + Random (21); Write (A [I]: 4)   

      End;   

      WriteLn; WriteLn ( 'Сума:',   Summa (N, A))   

    End.                  

    /* Програма на мові C */   

    # include   

    # include   

    # include   

    # include   

    int summa (int N, int a [100 ]);   

    int i, n, a [100];   

    void main ()   

    (   

      clrscr ();   

      printf ( "nКолічество   елементів масиву? "); Scanf ("% d ", & n);   

      printf ( "nв   сформованому масиві% d чисел: n ", n);   

    randomize ();   

      for (i = 0; i   

      (a [i] = -10 + random (21); printf ( "% d", a [i ]);}   

      printf ( "Сума:   % d ", summa (n-1, a ));   

    )   

    int summa (int N, int a [100])   

    (   

      if (N == 0) return a [0]; else return a [N] + summa (N-1, a);   

    )     

    Приклад 5. Визначити, чи є задана рядок паліндромом, тобто читається однаково зліва направо і справа наліво.

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

    (програма на мові Pascal)   

    Program   Palindrom;   

    (рекурсивна   функція)   

    Function Pal (S: String): Boolean;   

    Begin   

      If Length (S) <= 1   

      Then Pal: = True   

      Else Pal: = (S [1] = S [Length (S)]) and Pal (Copy (S, 2, Length (S) - 2 ));   

    End;   

    Var S: String;   

    (Основна   програма)   

    Begin   

    Write ( 'Введіть рядок:'); ReadLn (S);   

    If Pal (S) Then WriteLn ( 'Рядок є   паліндромом ')   

    Else WriteLn ( 'Рядок не   є паліндромом ')   

    End.                  

    /* програма на мові C */   

    # include   

    # include   

    # include   

    char s [100];   

    int pal (char s [100 ]);   

    void main ()   

    (clrscr ();   

      printf ( "nВведіте рядок:");   gets (s);   

      if (pal (s))   printf ( "Рядок є паліндромом ");   

    else   printf ( "Рядок не є паліндромом ");   

    )   

    int pal (char s [100])   

    (int l; char s1 [100];   

      if (strlen (s) <= 1) return 1;   

      else (l = s [0] == s [strlen (s) -1];   

      strncpy (s1, s 1, strlen (s) -2);   

      s1 [strlen (s) -2] = '

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

     

     

     

     

     

     

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