Рекурсія, глибоке копіювання об'єктів

Рекурсивний виклик функції

Рекурсія - самоподібність. Тобто, це коли об'єкт містить свою самоподібну копію в собі.

Зображення на тему рекурсії
Рекурсія в природі

У програмуванні рекурсивним викликом називається випадок, коли функція викликає сама себе в своєму тілі.

З рекурсіями потрібно бути обережним - неакуратний виклик може створити "вічну" рекурсію, яка з'їсть всю доступну їй пам'ять і підвісить браузер.

З одним варіантом рекурсії ми вже познайомилися на прикладі масивів. Додамо до нього рекурсивний виклик функції:


				var a = [];

				a[0] = a;

				console.log(a);


				function recur(a){

				  console.log(a);

				  if (a < 1000000) { recur(a*2); }

				}

				recur(1);

Глибина рекурсії.

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

Порахуйте глибину рекурсії у попередньому прикладі.

Пряма та непряма рекурсія.

При прямій рекурсія викликає саму себе, як у попередньому прикладі.

При непрямій рекурсії функція A викликає функцію B, а та в свою чергу викликає функцію A:


				function fun1(){

				  ...

				  fun2();

				  ...

				}

				function fun2(){

				  ...

				  fun1();

				  ...

				}

				fun1();

Ланцюжок може бути значно довшим, функції по черзі викликатимуть одна одну, і остання - викликатиме першу.

Завдання.

Виведіть в консоль рекурсією цифри від 10 до 0.

Виведіть в консоль строки:

Внесіть невеликі зміни, щоб отримати:

Практичне застосування рекурсії

Пошук шляху.

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

Розглянемо приклад пошуку шляху по лабіринту.

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


				function goTo(x, y){

				  console.log('we are in position', x, y);

				  ...

				  if (noWall(x - 1, y)) { goTo(x - 1, y); }    // left

				  if (noWall(x + 1, y)) { goTo(x + 1, y); }    // right

				  if (noWall(x, y - 1)) { goTo(x, y - 1); }    // up

				  if (noWall(x, y + 1)) { goTo(x, y + 1); }    // down

				}

				goTo(1, 1);

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

Ігри.

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

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

Фрактали.

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

Генерація віртуальних світів.

В жанрі ігор Rogue локації генеруються випадково за допомогою рекурсій.

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

Наприклад, весь світ гри Minecraft будується рекурсіями та фракталами. Завдяки цьому створюються гарні дивовижні структури, унікальні в межах всього світу розмірами 3,6 млрд. км² (площа всієї планети Земля - 0,51 млрд. км²). До того ж, в Minecraft можна створювати майже безкінечно велику кількість різноманітних світів.

Генератор ландшафта

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

Є невелика стара програмка Terragen версій 0.9.*, що дозволяє генерувати гірські пейзажі.

Сучасна версія програми значно потужніша:

Сортування.

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

Детальніше можна почитати за посиланнями:
TVD: Рекурсия и рекурсивные алгоритмы,
Хабра: Рекурсия. Тренировочные задачи.

Рекурсивне копіювання об'єктів

Раніше ми розглянули копіювання об'єкта за допомогою оператора for-in.

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

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


				function copyObj(obj){

				  res = {};

				  for (var key in obj) {

				    if (typeof obj[key] === 'object') {

				      if (obj[key].length !== undefined) {

				        res[key] = copyArr(obj[key]);

				      } else {

				        res[key] = copyObj(obj[key]);

				      }

				    } else {

				      res[key] = obj[key];

				    }

				  }

				  return res;

				}

Єдний ньюанс - при копіюванні масивів також потрібно враховувати тип даних кожного елемента масива.

Домашнє завдання

Виведіть рекурсією цифри від Z до A в консоль (використовуйте коди символів).

* Пошук скарбів.

Дано лабіринт, його представлено у вигляді матриці розмірами 21 х 13:


				var lab = [

				  '111111111111111111111','100010000010001000001','111010111010111011101',

				  '100010101000000000101','101110101010111110111','100000100010100000101',

				  '101111111110101110101','101000100000100010001','111011101110111111111',

				  '100010000010000000001','101111101010111111101','100000001010001000001',

				  '111111111111111111111'

				];

Одиниці - це стіни, нулі - коридори.

У лабіринті довільно розміщується точка початку гри та точка "скарб". Можна створити дві змінні з масивами з двох елементів, що відповідають координатам x та y:


			  var start = [5, 3],

				    gold = [7, 11];

Створіть функцію, яка б вибирала довільно один з коридорів лабіринту і заміняла б його на точку початку.

Застосуйте цю ж функцію для заміни нуля на літеру g.

Відмалюйте лабіринт у браузері, використовуючи теги.

Для відображення клітин коридорів чи стін зручно використовувати тег span, для горизонтальних рядків лабіринту - тег p, для всього лабіринту - тег div.


				div { width: 420px; border-left: 1px solid #999; border-top: 1px solid #999;}

				p { margin: 0; font-size: 0; line-height: 0; }

				span { display: inline-block; width: 19px; height: 19px; border-right: 1px solid #999; border-bottom: 1px solid #999;}

				span.start { background: #080;}

				span.wall { background: #999;}

				span.gold { background: #fa0;}


				// приклад маленького лабіринту:

				div

				 p>.wall*5

				 p>.wall+.start+span*2+.wall

				 p>.wall+span+.wall+span+.wall

				 p>.wall+span+.wall+.gold+.wall

				 p>.wall*5

Замість кольорів бекграунду можна задати текстуру кам'яної стіни, зображення шукача скарбів та скрині з золотом.

Щоб створити лабіринт по заданій матриці - вам знадобляться деякі нові команди JavaScript.

Створення тегів відбувається за допомогою метода document.createElement, елемент при цьому створюється в пам'яті.


				var span = document.createElement('span');

				var p = document.createElement('p');

				var div = document.createElement('div');

Щоб задати елементу клас - використовується властивість className:


				span.className = 'active';

				p.className = 'first';

				div.className = 'labyrinth';

Щоб добавити один елемент в інший - використовується метод appendChild:


				p.appendChild(span);

				div.appendChild(p);

				document.body.appendChild(div);

Створіть функцію, яка б відмальовувала лабіринт у браузері.

Керувати шукачем скарбів будемо вручну.

Добавте на сторінку 4 кнопки з написами "up", "right", "down", "left" (або фоновими зображеннями стрілок).

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

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

Але який же лабіринт без мінотавра? добавте ще одну точку m.

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

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

Наступний етап - автоматична генерація довільних лабіринтів і вже можна починати думати про вихід на комерційний ринок :).