Заміна рекурсивних алгоритмів ітеративними
Оскільки новий контекст створюється кожен раз, коли черговий екземпляр рекурсивної підпрограми (сам ще залишаючись незавершеним) заново викликає себе ж, то пам'ять комп'ютера витрачається дуже швидко. Тому рекурсию при всій її наочності можна віднести до економічних методів програмування. Існує навіть спеціальна наука - динамічне програмування. вивчає способи заміни рекурсивних алгоритмів адекватними ітеративними алгоритмами. Ми не будемо зараз заглиблюватися в виклад принципів динамічного програмування, а обмежимося лише прикладами перетворення рекурсивних програм в нерекурсівние.
Якщо виконання підпрограми приводить тільки кільком особам цієї ж самої підпрограми, то така рекурсія називається лінійної. Лінійну рекурсію досить легко замінити ітеративним алгоритмом. Наприклад, можна реалізувати функцію факторіала. певну на початку пункту "Рекурсія", двояко.
Якщо ж кожен екземпляр підпрограми може викликати себе кілька разів, то рекурсія називається нелінійної або "ветвящейся". Для того щоб перетворити таку рекурсію в ітеративний алгоритм, доведеться докласти багато зусиль і, можливо, навіть внести деякі зміни в оброблювану структуру даних. Прикладом "ветвящейся" рекурсії може служити розглянута вище процедура розкладання числа на множники.
Приклад порівняння рекурсивного і нерекурсівние алгоритму
Завдання. Двоє друзів вирішили піти в похід, зібрали і зважили всі необхідні речі. Як їм розділити набір предметів на дві частини найбільш чесним чином?
(Є набір натуральних чисел, можливо, з повтореннями. Необхідно розділити його на два поднабора так, щоб різниця між сумою ваг була мінімальною.)
рекурсивний алгоритм
Потрібно перебрати всі можливі підмножини заданого набору ваг. Для вирішення цього завдання існує кілька класичних алгоритмів, ми скористаємося найпростішим, який носить назву "повний перебір". У повній відповідності зі своєю назвою, цей алгоритм перебирає всі можливі варіанти наборів.
Реалізація рекурсивного алгоритму
Повний перебір з відсіканням
Наведена вище програма робить багато зайвої роботи. Скажімо, нема чого продовжувати генерування чергового набору після того, як поточна різниця вже перевищила раніше знайдений мінімум. Крім того, якщо в певний момент часу мінімум раптом виявиться рівним 1 або 0 (в залежності від парності вхідних даних), то подальші зусилля також стають непотрібними, оскільки все одно нічого меншого бути не може.
З урахуванням цих зауважень можна вдосконалити текст програми. Ми залишаємо цю нескладну роботу бажаючим.
нерекурсивний алгоритм
Тут нам потрібно кілька додаткових міркувань і лінійних масивів.
Основна частина приводиться нижче програми є итеративной реалізацією алгоритму повного перебору всіх можливих варіантів, що задовольняють вхідним обмеженням. Її основна відмінність від рекурсії - використання малого об'єму пам'яті для зберігання поточних даних. Вся інформація зберігається в масивах ves. take і dif. Для обчислень на кожному кроці використовується тільки ця інформація. Такий підхід дозволяє уникнути безперервних Перевичісленіе, які і є причиною "ваговитості" рекурсивного алгоритму.
Отже, перша частина програми повинна займатися підрахунком і упорядкуванням вводяться предметів по спадаючій їх ваг. Для економії місця ми не станемо приводити детальну реалізацію цього блоку: тут годиться будь-який метод сортування (див. Лекцію 4). Важливо лише, що в результаті цієї сортування все вхідні дані будуть записані в два лінійних масиву довжини k (кількість різних ваг).
Вважаємо тепер, що масив ves зберігає різні ваги предметів, впорядковані за спаданням, а масив kol - кількість предметів кожного ваги.
Крім того, в процесі введення даних проводиться підсумовування ваг всіх предметів, цей загальна вага записується в змінну sum. Правда, потім ця ж змінна буде зберігати не весь загальна вага, а тільки його половину (з урахуванням парності вихідної суми) - для зручності подальших порівнянь.
Ми не наводимо в тексті програми і реалізацію функції min () - як що не представляє особливого інтересу.