Рекурсивні співвідношення

Рекурентним співвідношенням називається формула виду

 a_n+1=F(a_n,a_n-1,...,a_n-k+1), де F деяка функція від k аргументів, 

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

 Рекурентне співвідношення однозначно визначає послідовність a_n, якщо вказано k перших членів послідовності. Рекурентне співвідношення є прикладом рекурсивного визначення послідовності.

Приклади

• Послідовність Фібоначчі:

a_n+1=a_n+a_n-1, a₁=1, a₂=1.

• Рекурентне співвідношення арифметичної прогресії:

a_n+1=a_n+d.

• Рекурентне співвідношення геометричної прогресії:

a_n+1=a_n·q.

• Рекурентне співвідношення послідовності n!:

a_n+1=a_n·(n+1).

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

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

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

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

Приклади

• Факторіал цілого невід'ємного числа n позначається n! і визначається як

  n!=n×(n-1)! при n>0 і n!=1 при n=0

• Числа Фібоначчі визначаються за допомогою рекурсії:

  перше і друге числа Фібоначчі рівні 1;

  для n>2, n-і число Фібоначчі дорівнює сумі (n-1)-го і (n-2)-го чисел Фібоначчі.

• 
  

  Трикутник Серпінського
  Практично всі геометричні фрактали задаються у формі нескінченної рекурсії (наприклад, трикутник Серпінського).
• Задача «Ханойська вежа». Її змістовна постановка така:

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

  Рекурсивний варіант розв'язку задачі:

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

  
  

  
  

       

                                          

  
  

       Контрольна робота з  теми: «Арифметична прогресія. Геометрична прогресія».

  
  

  Варіант  2

  0. Навести приклади послідовностей: а)додатні арифметичні прогресії; б)геометричні прогресії.

  1. Записати перші три члени арифметичної прогресії, якщо:

  1) а₁ = 2;  d = -2;   2) а₁ = 9; d = -6;      3) а₁ = -2х + 1; d = - 3х; 

  4) a₁ = x² + x;    d = -7x - 9x²;      5) a₁ = - 3- 5x²+4x;   d = 2 + 4x - 8x².  

  2. Записати четвертий  член геометричної прогресії, якщо:

  1) b₁ = 2 ;  q = - 6;   2) b₁ = 2 ; q = -1;  3) b₁ =  3; d = - х²; 

  4) b₁ = - x ^{- 8};  q = - 2x⁴;   5) b₁ = 2x⁹;  q = - x ^-12.  

  3. Знайти 41-й член арифметичної прогресії,  якщо: а₇ =11;  а₉ = -11.
  4. Знайти 8-й член геометричної прогресії,  якщо: b₄ = -16;  b₆ = -1.
  5. Задано арифметичну прогресію: a_n = 400; d = 10; a₁ = 10. Знайти n та формулу a(n).

  6. Задано геометричну прогресію: b_n = 2048; q = 4; b₁ = 16. Знайти n та формулу b(n).
  7. Задано геометричну прогресію: b₁ = - 4; b_n= - 512; n = 4. Знайти q та формулу b(n).
  8. Задано арифметичну прогресію: a₁ = 1; a_n= 79; n = 40. Знайти  S_n і d.
  9.  Задано геометричну прогресію: q = -1; b_n = 2; n = 7. Знайти b₁ та S_n.

  10. Знайдіть суму чисел:   S_n  = 1 + 3 + 6 + ... + 1068.

  11. При якому значенні х три числа вигляду 6х – 4, 2х + 4, 2х + 16  будуть послідовними членами геометричної прогресії? Знайдіть ці члени прогресії.

  12. Записати  звичайними дробами такі   числа:

  а) 0,7777… =0,(7);  б) 0,87272… = 0,8(72). Знайти добуток  квадрату півсуми та кубу піврізниці цих чисел.

  Контрольна робота з  теми: «Арифметична прогресія. Геометрична прогресія».

                                              

  Варіант  3

  0. Навести приклади послідовностей: а) від’ємні арифметичні прогресії; б)геометричні прогресії.

  1. Записати перші три членів арифметичної прогресії,  якщо:

  1) а₁ = 3;  d = 5;   2) а₁ = 9; d = -8;      3) а₁ = х + 3; d = - 2х; 

  4) a₁ = 9x²+ 8x;    d =  -7x -  2x²;      5) a₁ = -6 - 6x² - 6x;   d = 9- 5x - 3x².  

  2. Записати перші п’ятий член геометричної прогресії,  якщо:

  1) b₁ = 1 ;  q = -4;   2) b₁ = 3 ; q = -2;  3) b₁ =  2; d = - х; 

  4) b₁ = - x ^-4;  q = -2x²;   5) b₁ = 2x⁸;  q = -5x ^-2.  

  3. Знайти 21-й член арифметичної прогресії, якщо: а₃ = 41;  а₅ = -51.
  4. Знайти 6-й член геометричної прогресії, якщо: b₄ = -81;  b₂ = -1.
  5. Задано арифметичну прогресію: a_n=280; d=20; a₁=10. Знайти n та формулу a(n).
  6. Задано геометричну прогресію: b_n= 2048; q= 2; b₁= 8. Знайти n та формулу b(n).
  7. Задано геометричну прогресію: b₁= -1; b_n= -1024; n = 11. Знайти q та формулу b(n).
  8. Задано арифметичну прогресію: a₁= 1; a_n= 86; n= 50. Знайти  S_n і d.
  9.  Задано геометричну прогресію: q = 3; b_n= 2; n = 7. Знайти b₁ та S_n.

  10. Знайдіть суму чисел:   S_n  =1 + 2 + 4 + ... + 1032.

  11. При якому значенні х три числа вигляду 3х – 2, х + 2, х + 8 будуть послідовними членами геометричної прогресії? Знайдіть ці члени прогресії.

  12. Записати  звичайними дробами такі   числа: а) 0,1111… =0,(1);  б) 0,76363… = 0,7(63). Знайти квадрат суми  півсуми та піврізниці цих чисел.

  
  

   Контрольна робота з  теми: «Арифметична прогресія. Геометрична прогресія».

                                         

  Варіант  4

  0. Навести приклади послідовностей: а) додатні арифметичні прогресії; б)геометричні прогресії.

  1. Записати перші три члени арифметичної прогресії, якщо:

  1) а₁ = 4;  d = -2;   2) а₁ = 99; d = -3;      3) а₁ = -4х + 1; d = - 6х; 

  4) a₁ = x² + 5x;    d = -5x - 7x²;      5) a₁ = - 6- 4x²-9x;   d = 9 – 8x - 7x².  

  2. Записати четвертий  член геометричної прогресії, якщо:

  1) b₁ = 2 ;  q = -3;   2) b₁ = 2 ; q = -1;  3) b₁ =  3; d = - х²; 

  4) b₁ = -x ^-2;  q = -2x⁴;   5) b₁ = 2x⁹;  q = - x^-18.  

  3. Знайти 4-й член арифметичної прогресії,  якщо: а₁₁ =14;  а₉ = -14.
  4. Знайти 7-й член геометричної прогресії,  якщо: b₄ = -5;  b₂ = -125.
  5. Задано арифметичну прогресію: a_n = 800; d= 10; a₁= 20. Знайти n та формулу a(n).
  6. Задано геометричну прогресію: b_n= 2048; q= 4; b₁= 2. Знайти n та формулу b(n).
  7. Задано геометричну прогресію: b₁= - 4; b_n= -512; n= 6. Знайти q та формулу b(n).
  8. Задано арифметичну прогресію: a₁=1; a_n=39; n=180. Знайти  S_n і d.
  9.  Задано геометричну прогресію: q= -1; b_n= 8; n= 9. Знайти b₁ та S_n.

  10. Знайдіть суму чисел:   S_n  =1 + 3 + 6 + ... + 1017.

  11. При якому значенні х три числа вигляду 18х – 12, 6х + 12, 6х + 48  будуть послідовними членами геометричної прогресії? Знайдіть ці члени прогресії.

  
  

  12. Записати  звичайними дробами такі   числа: а) 0,6666… =0,(6);  б) 0,85252… = 0,8(72). Знайти квадрат різниці півсуми та піврізниці цих чисел.

  
  

  
  

  
  

  
  

  
  

  
  

  
  

Рекурсія в програмуванні

Докладніше: Процедура рекурсивна

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

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

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

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

Рекурсія у фізиці

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

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

Побутовий приклад (небажаного) самозбудження — свист у акустичних системах при завеликому підсиленні та/або невдалому розміщенні мікрофона відносно акустичних систем.

Цитати[ред. • ред. код]

Ітерація від людини. Рекурсія — від Бога. — Л. Пітер Дойч (Дональд Кнут. Мистецтво програмування.)

Гумор

Більшість всіх жартів про рекурсію стосується нескінченної рекурсії, у якій немає умови виходу:

• Відоме висловлення: Щоб зрозуміти рекурсію, потрібно спочатку зрозуміти рекурсію.

• Дуже популярний жарт про рекурсію, що нагадує словникову статтю:

  рекурсія 

  див. рекурсія^[1]

• Кілька розповідей Станіслава Лема присвячені можливим казусам при нескінченній рекурсії:
  • Розповідь про Йона Тихого та сепульки («Зоряні щоденники Йона Тихого»), у якому герой послідовно переходить від статті про сепульки до статті про сепуляції, звідти до статті про сепулькарії, у якій знову міститься посилання до статті «сепульки».
  • Розповідь про розумну машину, що мала достатній розум і лінь, щоб для рішення поставленої задачі побудувати собі подібну, і доручити рішення їй (підсумком стала нескінченна рекурсія, коли кожна нова машина будувала собі подібну і передавала завдання їй).

• Російська народна казка-пісня «У попа була собака…» виявляє приклад рекурсії:

  У попа була собака, він її любив

  Вона з'їла шматок м'яса, він її убив

  Убив і закопав,

  А на могилі написав:
  

  «У попа була собака, він її любив

  Вона з'їла шматок м'яса, він її убив

  Убив і закопав,

  А на могилі написав:
  

  «У попа була собака, він її любив

  Вона з'їла шматок м'яса, він її убив

  Убив і закопав,

  А на могилі написав:
  

  …

  (лапки цитат ніколи не закриються)

• Якщо в пошуковій системі Google ввести запит «рекурсія», то в пошуковій видачі побачите слова «Можливо, ви мали на увазі: рекурсія».

Лінійне однорідне рекурентне співвідношення з постійними коефіцієнтами

Лінійним однорідним рекурентним співвідношенням з постійними коефіцієнтами порядку ${\displaystyle k}$ є рівняння

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},}$

де всі коефіцієнти ${\displaystyle c_{i}}$ постійні.

Ті ж самі коефіцієнти визначають характеристичний многочлен (або "допоміжний многочлен")

${\displaystyle p(t)=t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}}$.

Згідно з основною теоремою алгебри існує ${\displaystyle d}$ коренів рівняння ${\displaystyle p(t)=0}$. Ці корені відіграють вирішальну роль в знаходженні послідовності, яка відповідає заданому рекурентному співвідношенню.

Якщо всі корені ${\displaystyle r_{1},r_{2},\dots ,r_{d}}$ різні, то розв'язок рекурсії має вигляд:

${\displaystyle a_{n}=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\cdots +k_{d}r_{d}^{n},}$

де коефіцієнти ${\displaystyle k_{i}}$ визначаються в залежності від значень початкових елементів послідовності ${\displaystyle a_{1},a_{2},\dots ,a_{d}}$.

У випадку коли однакові корені присутні декілька разів (кратні корені) розв'язок рекурсії має інший вигляд. Якщо ${\displaystyle r_{i}\ (i=1,\dots ,s)}$ корінь кратності ${\displaystyle l_{i}}$ (для простого кореня ${\displaystyle l_{i}=1}$), тоді

${\displaystyle a_{n}=\sum _{i=1}^{s}(k_{i1}+k_{i2}n+\cdots +k_{il_{i}}n^{l_{i}-1})r_{i}^{n},}$

де коефіцієнти ${\displaystyle k_{ij}}$ визначаються з початкових елементів послідовності.

Як приклад можна зауважити, що послідовність Фібоначчі задається лінійним однорідним рекурентним співвідношенням з постійними коефіцієнтами порядку два. Застосування наведеного методу дає формулу Біне.

В комбінаториці

Метод розв'язання комбінаторної задачі зведенням до меншої задачі (або задач) називається методом рекурентних співвідношень, а менша задача найчастіше є задачею відносно меншої кількості предметів.^[1]

Вікіпідручник має книгу на тему Розв'язник вправ по дискретній математиці/Комбінаторика/Вправи на рекурсію

В інформатиці

Рекурентні співвідношення мають принципове значення в аналізі алгоритмів.^[2] [3] Якщо алгоритм влаштований так, що він розбивається на декілька менших підзадач, то можна описати час його роботи з допомогою рекурентного співвідношення.

Простий приклад це час, необхідний алгоритму для пошуку елемента в упорядкованому векторі з ${\displaystyle n}$ елементів, в найгіршому випадку.

Примітивний алгоритм полягає в пошуку зліва направо. Найгіршим випадком,буде ситуація в якій потрібний елемент є останнім. В цьому випадку кількість порівнянь буде ${\displaystyle n}$.

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

${\displaystyle c_{1}=1}$

${\displaystyle c_{n}=1+c_{[n/2]}}$,

що буде близько до функції ${\displaystyle \log _{2}(n)}$.