Рекурсія - це виклик функції всередині самої себе.
Якщо ви чекаєте гостей і раптом помітили на своїй сукні пляму, не засмучуйтеся це поправимо.
Наприклад, плями від рослинного масла легко виводяться бензином.
Плями від бензину легко знімаються розчином лугу.
Плями від лугу зникають від оцтової есенції.
Сліди від оцтової есенції потрібно потерти соняшниковою олією.
А як видаляти плями від олії, ви вже знаєте.
Наприклад, у нас є коробка, в якій складені інші коробки. В одній з цих коробок є ключ. Потрібно його знайти.
Можна скористатись таким алгоритмом:
1) Скласти всі коробки в купу
2) Взяти коробку і відкрити її
3) Якщо всередині інша коробка, то покласти її на купу для подальшого пошуку
4) Якщо всередині лежить ключ, то пошук завершено
5) Повторити поки в купі є коробки
Або таким:
1) Переглянути вміст коробки
2) Якщо знайдете коробку, повернутись до кроку 1
3) Якщо всередині лежить ключ, то пошук завершено
Розглянемо випадок, коли у червоній коробці лежать синя (у ній - чорна та фіолетова), жовта (в ній - сіра) та зелена.
За першим алгоритмом, ми відкриваємо червону коробку. Бачимо в ній синю, жовту та зелену, кладемо їх на купу. Тоді відкриваємо синю, бачимо чорну та фіолетову, кладемо їх на купу. Перевіряємо жовту, з неї додаємо на купу сіру. Тоді зелену, чорну, фіолетову та сіру.
З другим алгоритмом, відкривши синю коробку, і побачивши у ній дві, відкриваємо їх. Тоді переходимо до наступної - жовтої, і сірої у ній. А тоді - зелена.
Не можна сказати, що один з цих алгоритмів ефективніший чи кращий (зрештою, все залежить від того, де ж ключ). Але один з них має лаконічніший запис, який може бути зручнішим для пояснення.
Дуже важливо передбачити базовий випадок, інакше отримаємо безконечну рекурсію. Наприклад:
def rec ( n ) :
print ( n )
rec (n-1)
rec (10)
Програма буде друкувати числа від 10 до мінус безконечності, якщо ми не зупинимо програму (комбінація клавіш Ctrl+C).
Важливо вказати базовий випадок, який буде точкою зупинки. Наприклад, друкувати числа лише до нуля.
def rec ( n ) :
print ( n )
if n>0:
rec( n-1 )
else:
return
rec(10)
Три правила рекурсії
1) Рекурсія повинна мати базовий випадок
2) Рекурсія повинна містити зміну стану та можливість переходу до базового випадку
3) Рекурсія повинна викликати саму себе
Задача 1. Підняти число до степеня
def stepin (base, exp):
res=1
for i in range(exp):
res=res*base
return res
якщо число рівне 1, то
повернути створити список з одного елемента, що містить список [1] (верхній елемент трикутника)
інакше
створити список з елементом 1 (перша одиниця ряду)
результат = рекурсивний виклик цієї функції для попереднього числа
останній рядок = останній елемент результату (елемент номер -1)
для всіх елементів результату
дописати у список суму (елемент+наступний за ним)
до списку додати елемент 1 (остання одиниця ряду)
до результату додати утворений список
повернути результат
Виклик функції для числа 5 дає такий результат:
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Залишається вивести його на екран у зручному вигляді.
Варто пам'ятати, що Python дозволяє виконувати дію множення над пробілами " "
Розв'язки самостійних задач:
def triangle(n):
if n == 0:
return []
elif n == 1:
return [[1]]
else:
new_row = [1]
result = triangle(n-1)
last_row = result[-1]
for i in range(len(last_row)-1):
new_row.append(last_row[i] + last_row[i+1])
new_row += [1]
result.append(new_row)
return result
answer=triangle(5)
print(answer)
for element in answer:
print(" "*(len(answer)-answer.index(element)), end=" ")
for el in element:
print(el, end=" ")
print()
Рекурсія в літературі
Приклад. Віршик про індіанців
One little, two little, three little Indians
Four little, five little, six little Indians
Seven little, eight little, nine little Indians
Ten little Indian boys.
Ten little, nine little, eight little Indians
Seven little, six little, five little Indians
Four little, three little, two little Indians
One little Indian boy
Викликаємо функцію. Якщо число в функції не 10, то якщо воно не кратне 3, то друкувати число і little, якщо кратне 3, то друкувати число і little Indians. І запускаємо цю ж функцію для наступного числа.
Якщо ж число кратне 10, то друкувати число і little Indian boys.
def boys(k):
if k!=10:
if k%3!=0:
print(k, "little,")
else:
print(k,"little Indians")
boys(k+1)
print(k,"little Indian boys")
n=boys(1)
Самостійно створіть функцію для завершення віршика (відлік у зворотньому порядку)
Ще приклад рекурсивного вірша:
Лічилка про десять індійчат (у перекладі Вадима Хазіна):
Десять індійчат пообідать сіли;
Захлинулося одне— дев'ять залишилось.
Дев'ять індійчат по обіді спали;
Не прокинулось одне— вісім їх зосталось.
Вісім індійчат Девоном блукали;
Повернулись сім назад— одного не стало.
Індійчаток семеро дрівця заготовляли;
Зарубали одне з них— шестеро зосталось.
Шість вже індійчат на пасіці зібрались;
Так одне там вжалив джміль, що їх п'ять зосталось.
П'ять веселих індійчат слідство учинили;
Вирок винесли одному— четверо лишилось.
Вдень четвірко індійчат в морі пустувало;
На гачок одне спіймалось— то вже троє стало.
Троє індійчат у звіринці стрілись;
Пригорнув ведмідь одне— двоє залишилось.
Двоє індійчат на осонні грілись;
Раптом постріл пролунав— вмить одне лишилось.
Тут самотнє індійчатко гірко заридало;
Шию зашморгом стягнуло;— й нікого не стало.
