Рекурсія в Python. Приклади розв’язку задач
Зміст
- 1. Поняття рекурсії. Рекурсивні функції
- 2. Приклади розв’язку задач на рекурсію
- 2.1. Функція CalcSumNumbers(). Обчислити суму елементів набору чисел
- 2.2. Функція CalcSumNegativeNumbers(). Обчислити кількість від’ємних чисел у наборі
- 2.3. Функція CalcSumNumbers(). Обчислення суми чисел з підтримкою вкладених списків
- 2.4. Функція GetFibonacciList(). Отримати ряд Фібоначчі
- 2.5. Функція ReverseNumber(). Реверсування числа
- 2.6. Функція Power(x, y). Піднесення числа x до степеня y
- 2.7. Функція GetMaxList(). Визначення максимального елементу списку
- 2.8. Функція Convert_10_to_2(). Перевід з десяткової системи числення в двійкову
- Зв’язані теми
Пошук на інших ресурсах:
1. Поняття рекурсії. Рекурсивні функції
Рекурсія – це спосіб організації циклічного процесу шляхом виклику рекурсивної функції. Рекурсивна функція – це функція, яка містить код виклику самої себе з метою організації циклічного процесу. З допомогою рекурсивних функції можна з мінімальним об’ємом програмного коду розв’язувати деякі задачі, обійшовши використання (оголошення) зайвих структур даних. Рекурсію можна розглядати як альтернативу циклам та ітераціям.
⇑
2. Приклади розв’язку задач на рекурсію
2.1. Функція CalcSumNumbers(). Обчислити суму елементів набору чисел
У прикладі реалізовано рекурсивну функцію CalcSumNumbers(), яка здійснює просумовування чисел у вхідному списку. В роботі функції вхідний список A розділяється на 2 частини:
- перший елемент списку A[0];
- всі інші елементи списку крім першого. Ці елементи виділяються з допомогою зрізу A[1:].
Витягнувши перший елемент зі списку з допомогою зрізу, можна передати цей новоутворений список в наступний рекурсивний виклик функції.
# Рекурсивна функція - повертає суму чисел у вхідному наборі def CalcSumNumbers(A): if A == []: # якщо набір пустий, повернути 0 return 0 else: # Обчислити суму - додати перший елемент набору summ = CalcSumNumbers(A[1:]) # рекурсивний виклик цієї ж функції # Додати до загальної суми перший елемент summ = summ + A[0] return summ # Демонстрація використання функції CalcSumNumbers() # 1. Створити набір чисел L = [ 2, 3, 8, 11, 4, 6 ] # 2. Викликати функцію summ = CalcSumNumbers(L) # 3. Роздрукувати суму print("summ = ", summ)
Результат виконання програми
summ = 34
⇑
2.2. Функція CalcSumNegativeNumbers(). Обчислити кількість від’ємних чисел у наборі
За попереднім прикладом (п. 4.1) реалізується функція CalcSumNegativeNumbers(), яка обчислює кількість від’ємних чисел у списку (наборі). Знову ж таки, з вхідного списку виділяється перший елемент та всі інші елементи.
# Рекурсивна функція - повертає кількість від'ємних чисел у списку def CalcSumNegativeNumbers(A): if A == []: # якщо набір пустий, повернути 0 return 0 else: # Обчислити кількість, перейти до подальшої обробки # без першого елементу count = CalcSumNegativeNumbers(A[1:]) # рекурсивний виклик цієї ж функції # Збільшити кількість на 1 при умові, що поточне число від'ємне if A[0]<0: count = count + 1 return count # Демонстрація використання функції CalcSumNumbers() # 1. Створити набір чисел L = [ -2, 3, 8, -11, -4, 6 ] # 2. Викликати функцію n = CalcSumNegativeNumbers(L) # 3. Роздрукувати суму print("n = ", n)
Результат виконання програми
n = 3
⇑
2.3. Функція CalcSumNumbers(). Обчислення суми чисел з підтримкою вкладених списків
Якщо потрібно, щоб рекурсивна функція обробляла вкладені списки, то в тілі функції потрібно реалізувати цикл обходу елементу списку. Потім цей елемент потрібно перевіряти, чи він є списком за зразком
if not isinstance(t, list): ...
тут t – елемент, який перевіряється з допомогою функції isinstance().
# Рекурсивна функція - повертає суму чисел, обробляє вкладені списки def CalcSumNumbers(A): summ = 0 # тут потрібно реалізувати обхід в циклі for t in A: # Обробляється елемент t if not isinstance(t, list): # перевірити, чи t - список summ = summ + t # якщо t - не є список, то додати його до суми else: # отримати суму з наступних рекурсивних викликів summ = summ + CalcSumNumbers(t) return summ # Демонстрація використання функції CalcSumNumbers() # 1. Створити набір чисел L = [ -2, 3, 8, 11, [-4, 6, [ 2, [-5, 4] ] ] ] # 2. Викликати функцію summ = CalcSumNumbers(L) # 3. Роздрукувати суму print("summ = ", summ)
Результат виконання програми
summ = 23
⇑
2.4. Функція GetFibonacciList(). Отримати ряд Фібоначчі
Ряд Фібоначчі містить числа, в яких наступне число визначається як сума двох попередніх чисел:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...
Нижченаведена рекурсивна функція формує ряд Фібоначчі у вигляді списку для заданого максимального значення у списку.
# Рекурсивна функція - повертає ряд Фібоначчі у вигляді списку, # Параметр n - максимальне значення у списку. def GetFibonacciList(n, L): # Перевірити, чи довжина списку коректна count = len(L) if len(L)<2: return [] # Отримати останні числа у списку L num1 = L[count-2] num2 = L[count-1] # Формула розрахунку наступного числа if (num1+num2) < n: L = L + [num1+num2] return GetFibonacciList(n, L) # викликати рекурсивно функцію else: return L # якщо досягнуто кінець, то звичайний вихід # Викликати функцію GetFibonacciList() LL = GetFibonacciList(100, [0, 1]) print("LL = ", LL)
Результат виконання програми
LL = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
⇑
2.5. Функція ReverseNumber(). Реверсування числа
У прикладі наводиться функція ReverseNumber() представлення числа у зворотному порядку. Наприклад, для числа 12345 результат буде 54321.
Функція отримує вхідним параметром ціле число number. Функція повертає ціле реверсоване число.
# Рекурсія. Реверсування числа import math # Рекурсивна Функція def ReverseNumber(num): # 1. Перевірка, чи число задано коректно if num<0: return -1 # 2. Перевірка, чи число рівне 0 if num==0: return 0 # 3. Якщо число коректне (num>0), то обробити його # 3.1. Визначити порядок числа (кількість цифр у числі) n_digit = 0 # порядок числа num2 = num # копія num while num2>0: n_digit = n_digit+1 num2 = num2//10 # 3.2. Взяти останню цифру з числа t = num%10 # 123456 => 6 # 3.3. Помножити останню цифру на 10^n_digit res = t * int(math.pow(10, n_digit-1)) # 3.4. Повернути суму з викликом рекурсивної функції return res + ReverseNumber(num//10) # Демонстрація використання функції num = 1234000567 rnum = ReverseNumber(num) # rnum = 7650004321 print("rnum = ", rnum)
Результат виконання функції
rnum = 7650004321
⇑
2.6. Функція Power(x, y). Піднесення числа x до степеня y
Рекурсивна функція Power(x, y) повертає результат піднесення дійсного числа x до цілого степеня y. Попередньо передбачається, що значення y>0.
# Рекурсія. Піднесення числа x до степеня y # Рекурсивна функція def Power(x, y): if y>0: return x * Power(x, y-1) else: return 1 # Демонстрація використання функції Power() x = 3 y = 4 res = Power(x, y) print("res = ", res)
Результат виконання програми
res = 16
⇑
2.7. Функція GetMaxList(). Визначення максимального елементу списку
У прикладі реалізовано функцію GetMaxList(), яка обчислює максимальний елемент списку. Вся робота функції поділена на 2 частини:
- виконання дій, якщо в списку два і більше чисел;
- виконання дій, якщо список закінчується, тобто розглядається останній елемент.
Кожен рекурсивний виклик функції розглядає список як дві складові:
- перший елемент списку (елемент з індексом 0);
- наступні за першим елементи списку (елементи з індексами 1, 2, і т.д.).
# Рекурсивна функція. Визначити максимальний елементу списку def GetMaxList(L): if len(L)>1: # Отримати максимум з наступних рекурсивних викликів Max = GetMaxList(L[1:]) # Порівняти максимум з першим елементом списку if L[0]<Max: return Max else: return L[0] if len(L)==1: # останній елемент в списку return L[0] # повернути цей елемент # Демонстрація використання функції Power() L = [ 500, 2300, 800, 114, 36] res = GetMaxList(L) print("res = ", res)
Результат виконання програми
res = 2300
⇑
2.8. Функція Convert_10_to_2(). Перевід з десяткової системи числення в двійкову
У даному прикладі, з метою порівняння, реалізовано 2 функції, які конвертують ціле число з десяткової системи числення в його аналог у двійковій системі числення:
- Convert_10_to_2_R() – це є рекурсивна функція конвертування числа;
- Convert_10_to_2() – не рекурсивна функція.
Для забезпечення розв’язку задачі, в нерекурсивній версії Convert_10_to_2() вводиться додаткова змінна k, яка визначає порядок отримуваного двійкового числа. Для того, щоб зберігати цей порядок k у рекурсивній версії функції Convert_10_to_2_R(), потрібно його передавати в цю функцію другим параметром.
import math # Рекурсивна функція. Перевід числа з 10-ї системи числення у двійкову. # Функція повертає результат у вигляді числа: 13 => 1101. # Параметри: # - n - число в десятковій системі числення; # - k - поточний порядок (кількість цифр) числа у двійковій системі. def Convert_10_to_2_R(n, k): if n>0: t = n%2 return Convert_10_to_2_R(n//2, k+1) + int(t*math.pow(10,k)) else: return 0 # Не рекусивна функція переводу def Convert_10_to_2(n): summ = 0 # сума чисел: 5 => 100 + 0 + 1 => 101 k = 0 # порядок числа у двійковій системі числення while n>0: t = n%2 summ = summ + int(t*math.pow(10,k)) k = k+1 n = n//2 return summ # Демонстрація використання функцій res1 = Convert_10_to_2_R(126, 0) # Виклик рекурсивної функції res2 = Convert_10_to_2(126) # Виклик нерекурсивної функції print("res1 = " , res1) print("res2 = " , res2)
Результат виконання програми
res1 = 1111110 res2 = 1111110
⇑
Зв’язані теми
- Поняття функції. Загальна форма. Приклади оголошення та використання функцій
- Передача функції як аргументу. Структури даних, що містять перелік функцій. Повернення функції з іншої функції оператором return. Приклади
⇑