Рекурсія – це спосіб організації циклічного процесу шляхом виклику рекурсивної функції. Рекурсивна функція – це функція, яка містить код виклику самої себе з метою організації циклічного процесу. З допомогою рекурсивних функції можна з мінімальним об’ємом програмного коду розв’язувати деякі задачі, обійшовши використання (оголошення) зайвих структур даних. Рекурсію можна розглядати як альтернативу циклам та ітераціям.
Основною ідеєю рекурсії є поступове спрощення обчислювальних дій, допоки обчислювана функція не прийме у якості аргумента найменше можливе значення. Тим не менше, у сучасній реалізації мови Пайтон при використанні рекурсії транслятор мови зберігає всі рекурсивно викликані функції у стек. Цей стек має обмеження у кількості повторів (глибини рекурсії) у 1000 раз. У модулі sys метод sys.getrecursionlimit() повертає акnуальне значення цієї велиини. Також її можна збільшити, використавши метод sys.setrecursionlimit(), який у якості аргумента приймає нове значення величини стеку рекурсій. Однак сильно збільшувати його не варто, оскільки можна отримати помилки типу Stak Overflow чи Buffer Overflow. Слід відмітити, що виконання обчислень шляхом рекурсії є набагато простішим у написанні, ніж виконання тих самих обислень але прямим методом. Тим не менше, рекурсивний алгоритм, будучи простішим у написанні є відчутно повільнішим за прямі обчислення. У якості прикладу - зверніть увагу на додані класичні рекурсивні алгоритми - обчислення факторіалу прямими обчисленнями і рекурсією, обчисленя ряду чисел Фібоначчі, алгоритм Евкліда та алгоритм зведення у степінь (який тут не наводиться через свою простоту).
Однак! Існують задачі, в основному пов'язані з побудовою самоподібних структур (фракталів), які виконуються виключно через рекурсивні алгоритми. Як приклади таких алгоритмів - демонструю алгоритми побудови "сніжинки Коха" та "дерева рекурсії". Прошу звернути увагу на те, що у кожній реалізації рекурсивної функції ОБОВ'ЯЗКОВО вказується умова досягнення ліміту рекурсії. Зазвичай вона має вигляд if <досягнуто якогось значення>: return <що-небудь>. У всіх наданих алгоритмах тим чи іншим чином вона присутня.
Вам вже відомий простий послідовний алгоритм обчилення факторіалу заданого числа, який йде від найменшого значення, до заданого:
a = int(input('enter number to get factorial of: '))
factorial = 1
for i in range(1, n + 1):
factorial *= i
print('Factorial of %d is %d' % (a, factorial))Але існує його рекурсивний аналог, всередині якого викликається функція факторіалу, починаючи з заданого значення і рухаючись до найменшого:
def recursive_factorial(n):
if n==1:
return n
else:
return n*recursive_factorial(n-1)
n = int(input('enter number to get factorial of: '))
factorial = recursive_factorial(n)
print('Factorial of %d is %d' % (n, factorial))Як бачимо, у цій варіації алгоритму функція викликає саму себе, допоки не буде виконано умову n==1 (кінець рекурсії). Прошу звернути увагу, що такий рекурсивний алгоритм дуже легко може перевищити ліміт рекурсій, наприклад при рекурсивному обчисленні факторіалу числа 999. Тому у такому випадку варто застосувати інструкції типу:
import sys
print('current recursion limit is:', sys.getrecursionlimit())
n = int(input("set recursion limit (default is 1000): "))
sys.setrecursionlimit(n)Ці інструкції виведуть вам у консоль актуальну величину cтека рекурсій, та дозволять задати його розміри за бажанням.
Ряд Фібоначчіі – це послідовність чисел, кожне наступне число якого є сумою двох попередніх. У природі числа Фібоначчі часто трапляються в різних спіральних формах. Так, черешки листя примикають до стебла по спіралі, що проходить між двома сусідніми листками: 1/3 повного оберту в ліщини, 2/5 — у дуба, 3/8 — у тополі і груші, 5/13 — у верби; лусочки на ялиновій шишці, насіння соняшника розташовані спіралями, причому кількості спіралей кожного напрямку також, як правило, числа Фібоначчі.
Послідовність названа на честь математика XIII століття Леонардо Фібоначчі з Пізи. Його книга 1202 року — Книга абака — представила цю послідовність спільноті західноєвропейських математиків, хоча така послідовність вже була описана раніше як числа Вараханка в індійській математиці. Послідовність, описана в «Книзі абака», починалася з F1 = 1.
Якщо створювати алгоритм пошуку чисел у Ряді Фібоначчі, то алгоритм буде мати наступний вигляд:
n = int(input('enter how many numbers U ann get in Fibonachi route: '))
first = 0
second = 1
for i in range(n):
print(first, sep=',', end=' ')
temp = first
first = second
second = temp+secondУ даному випадку алгоритм починає з найменших значень і поступово додає їх до досягнення відповідного елементу послідовності, роздруковуючи результати обчислень у один рядок через кому.
Рекурсивна версія даного алгоритму йде у зворотньому напрямку, викликаючи саму себе, допоки не досягне мінімального значення:
def fibonacchi(n):
if n<=1: return n
return fibonacchi(n-1)+fibonacchi(n-2)
number = int(input('enter length of Fibonacchi range: '))
for i in range(number):
print(fibonacchi(i), sep=',', end=' ')Зверніть увагу, що рекурсивний виклик функції здійснюється всередині інструкції return
Найбільший спільний дільник (НСД) — найбільше натуральне число, на яке без остачі ділиться кожне з даних. Щоб знайти НСД двох або кількох чисел, необхідно:
- розкласти дані числа на прості множники;
- скласти добуток усіх спільних простих множників;
- обчислити складений добуток.
Саме завдяки наявності першого пункту у цьому алгоритмі його простіше за все виконати за допомогою рекурсії.
def nsd(a,b):
if b==0:
return a
else:
return nsd(b, a % b)
num1 = int(input('enter first number: '))
num2 = int(input('enter second number: '))
print('biggest common denominator of %d and %d is: %d' %(num1,num2,nsd(num1,num2)))Коли ми з вами розглядали різні алгоритми сортування списків чи інших масивів, ви могли звернути увагу на алгоритм сортування злиттям. Його особливістю є те, що він поступово поділяє список навпіл, допоки не дійде до одного елемента, а потім поступово зливає їх, порівнююи між собою:
# функція злиття двох відсортованих списків
def merge_list(a, b):
c = []
N = len(a)
M = len(b)
i = 0
j = 0
while i < N and j < M:
if a[i] <= b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1
c += a[i:] + b[j:]
return c
# функція рекурсивного поділу списків та їх злиття у відсортований список
def split_and_merge_list(a):
N1 = len(a) // 2
a1,a2 = a[:N1],a[N1:] # поділ масиву на дві приблизно рівні частини
if len(a1) > 1: # якщо довжина поділеного списку більше 1 - ділимо далі
a1 = split_and_merge_list(a1)
if len(a2) > 1: # якщо довжина другої половини списку більше 1 - ділимо далі
a2 = split_and_merge_list(a2)
return merge_list(a1, a2) # викликаємо злиття та сортування двох поділених списків
a = [9, 5, -3, 4, 7, 8, -8]
print(split_and_merge_list(a))Крива́ Ко́ха — фрактальна крива, описана 1904 року шведським математиком Хельге фон Кохом. Крива Коха є типовим геометричним фракталом. Процес її побудови виглядає так: беремо одиничний відрізок, поділяємо на три рівні частини і замінюємо середній інтервал рівностороннім трикутником без цього сегмента. У результаті утворюється ламана, що складається з чотирьох ланок з довжиною 1/3 довжини початкового відрізка. На наступному кроці повторюємо операцію для кожного з чотирьох отриманих ланок і так далі. Гранична крива і є кривою Коха. Три копії кривої Коха, побудовані (вістрями назовні) на сторонах правильного трикутника, утворюють замкнену криву, так звану сніжинку Коха.
Типовий алгоритм для побудови Сніжинки Коха на Пайтон буде виглядати так:
from turtle import*
def snowflake_side(length, level): # створюємо одну криву Коха
if level==0: #задаємо межу рекурсії
forward(length)
return
length/=3.0 # ділимо довжину відрізку на 3
snowflake_side(length, level-1)# і рекурсивно викликаємо самих себе
left(60)
snowflake_side(length, level-1)
right(120)
snowflake_side(length, level-1)
left(60)
snowflake_side(length, level-1)
def create_snowflake(length, depth): # збираємо з трьох кривих Коха, одну Сніжинку Коха
for _ in range(3):
snowflake_side(length, depth)
right(120)
speed(0)
hideturtle()
penup()
goto(-200,200) #перемщуємо перо у лівий верхній кут поля
pendown()
create_snowflake(250,2) #задаємо параметри довжини кривої та глибини рекурсії
exitonclick()Даний алгоритм є чудовим прикладом самоподібних структур. У даному випадку кожен раз після малювання лінії здійснюється перехід на нову гілку, повернення до початку попередньої і початок малювання симметричної першій гілки.
import turtle
turtle.hideturtle() #ховаємо черепашку, щоб працювала швидше
turtle.speed(0) # задаємо максимальну швидкість черепашки
turtle.penup()
turtle.goto(0,-300) # переходимо вниз полотна
turtle.pendown()
turtle.left(90) # повертаємо вверх, оскільки початку черепашка дивиться направо
def tree(sizes, depth):
if depth==0: # здаємо умову припинення рекурсії
return
turtle.width(depth)
turtle.forward(sizes)
x=30
turtle.right(x) # повертаємо направо н величину Х від початкової гілки
tree(sizes*0.7, depth-1) # викликаємо самі себе, щоб намалювати нову, меншу гілку
turtle.left(2*x) # повертаємо наліво на величину 2х щоб гілки були симметричними
tree(sizes*0.7, depth-1) # знову викликаємо самі себе щоб намалювати меншу гілку
turtle.right(x) #повертаємось на кут материнської гілки
turtle.backward(sizes) #повертаємось до розгалуження
tree(100,5)
turtle.exitonclick()За потреби, алгоритм можна ускладнити, змінивши кількість розгалуджень, їх кут та довжину кожної окремої гілки, отримуючи досить реалістичні зображення рослиноподібних структур.