РЕКУРСИВНІ АЛГОРИТМИ R
ГЛАВА 6
РЕКУРСИВНІ АЛГОРИТМИ R
Поняття рекурсії P
Коли рекурсію використовувати не потрібно P
Приклади рекурсивних программ P
РЕКУРСИВНІ АЛГОРИТМИ
Рекурсивним називається об'єкт, що частково складається або визначається за допомогою самого себе. Рекурсія зустрічається не тільки в математиці,… Приклад 1. Рекурсивне визначення натуральних чисел:
а) 0 – число натуральне,
Рекурсивні алгоритми особливо підходять для задач, де оброблювані дані визначаються в термінах рекурсії. Однак це не означає, що таке рекурсивне… Програми, у яких варто уникати алгоритмічної рекурсії, можна охарактеризувати… або P ≡ S; if В then P (1)
6.3.1. Алгоритми «Розділяй і пануй»
Мабуть, найбільш значущім і найбільш використовуваним методом проектування ефективних алгоритмів є метод, що зветься…
У трьох позиціях, що залишилися, число з першої позиції бути присутнім не може, тобто набір можливих чисел, що можуть бути в позиціях позначених “*”… В наведеному розсуді було розглянуто роботу з першим елементом кожного… {===== Програмний приклад 6.6 =====}
Задача про вісьмох ферзів.Вісім ферзів треба так розставити на шаховій дошці, щоб жоден з них не загрожував іншому.
Оскільки ферзь вбиває всі фігури, що знаходяться на тій самій вертикалі,… {===== Програмний приклад 6.8 =====}
ВПРАВИ
1. На яких питаннях необхідно зосередити увагу при розробці рекурсивних алгоритмів?
2. Напишіть рекурсивну підпрограму сортування злиттям.
3. Рекурсивна та ітераційна підпрограми виконують однакове завдання. Порівняйте час їх виконання, поясніть свою відповідь.
4. Пояснить, що таке ”пряма” та ”косвенна” рекурсія, наведіть приклади.
5. Що таке рекурсивні структури даних , наведіть приклади.
6.
__________