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

Рекурсія (від латин. recursio — повернення) у широкому розумінні — це опис або зображення об’єкта (процесу, явища) через самого себе. Рекурсія застосовується в різних галузях людської діяльності, найчастіше — в математиці й інформатиці. У лінгвістиці рекурсією називають можливість мови породжувати нові мовні конструкції на основі попередньої.

Приклад 1.

Речення «Тип об’єктів визначає синтаксичний смисл оператора» може бути розширено до такого: «Сашко зрозумів, що тип об’єктів визначає синтаксичний смисл оператора», а останнє речення розширено до такого: «Тепер Катря знає, що Сашко зрозумів, що тип об’єктів визначає синтаксичний смисл оператора».

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

Програми обчислення рекурсій оформлюються у вигляді підпрограм (у мові Python —функцій). Реалізація таких функцій заснована на структурі даних, що називають стеком.

У стеку спочатку запам’ятовуються всі дії, що виконуються до моменту обчислення опорного значення, а потім у зворотному порядку вони виконуються.

Наприклад, якщо рекурсивна функція обчислює числа Фібоначчі, то запам’ятовуються всі дії f(n) = f(n–2) + f(n–1) до тих пір, поки не буде знайдене опорне значення, а потім у зворотному порядку виконується обчислення.

Отже, для обчислення рекурсивних функцій потрібен стек і виконання щонайменше удвічі більше операцій, ніж, наприклад, у процесі використання рекурентних обчислень.

Пригадаємо, що рекурентне обчислення значення функції на кожному кроці здійснюється через її значення на попередньому кроці.

Уже відомий вам алгоритм рекурентного обчислення виразу y = xⁿ можна подати так:

У наведенному алгоритмі після того, як вираз i<=n на кроці 6 набуде значення False, виконання алгоритму завершується і змінна y міститиме результат обчислення.

Для рекурсивного обчислення значення xⁿ (n — додатне ціле, x — може бути дійсне) необхідно обчислити значення x^n-1, оскільки xⁿ = x^n-1 * x. У свою чергу, для обчислення x^n-1 потрібно обчислити x^n-2, оскільки x^n-1=x^n-2 * x і т. д. Процес обчислення припиняється після обчислення x⁰, оскільки воно має значення 1.

Усі ці дії запам’ятовуються в стеку. Але отримано не результат, а лише опорне значення функції. Для отримання кінцевого значення функції потрібно реалізувати зворотний процес обчислення, що міститься в стеку.

def st(x,n):
 if n == 0:
 return 1
 else:
 return st(x, n - 1)*x

print("Введіть число x")
x = int(input())
print("Введіть число n")
n = int(input())
print("результат=", st(x,n))

Класичним варіантом рекурсивної функції є обчислення факторіалу заданого числа n, яке виконується за формулою n! = n * (n–1)!, якщо n>0, і n! = 1, якщо n=0.

def fact(n):
 if n == 0:
 return 1
 else:
 return n * fact(n - 1)
print("Введіть число")
n = int(input())
print(fact(n))

Приклад 4.

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

Програма знаходження найбільшого спільного дільника двох цілих чисел без викори станнярекурсивних підпрограм уже розглядалася раніше. Розв’язання задачі засноване на використанні алгоритму Евкліда. Програму реалізації цього алгоритму з використанням рекурсивної функції зображено нижче. Функція має ім’я nod, а числа, для яких обчислюється найбільший спільний дільник, позначені змінними a і b.

def nod(a, b):
 if b == 0:
 return a
 else:
 return nod(b, a % b)
 
print("Введіть число a")
a = int(input())
print("Введіть число b")
b = int(input())
print("nod = ", nod(a, b))

Рекурсія є складним процесом, який вимагає додаткової пам’яті та часу її реалізації. Тому частіше викори стовується рекурентне обчислення. Однак без рекурсії інколи обійтися досить складно, оскільки без неї алгоритм має заплутану логіку.

Ввести код програми за зразком (з коментарями). Записати результат виконання програми

Приклад 1:

Приклад 2:

Приклад 3:

Задача:

Створіть рекурсивну функцію для обчислення суми перших n натуральних чисел.

Умова:

Напишіть програму на мові програмування Python, яка містить рекурсивну функцію для обчислення суми перших n натуральних чисел. Користувач повинен вводити значення n, і програма має виводити суму цих чисел.

Приклад виклику:

Введіть значення n: 5
Сума перших 5 натуральних чисел: 15

Пояснення:

Сума перших n натуральних чисел може бути обчислена рекурсивно за формулою: 1 + 2 + 3 + ... + n.