Python. Рекурсія. Приклади розв’язку задач




Рекурсія в Python. Приклади розв’язку задач


Зміст


Пошук на інших ресурсах:

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

 


Зв’язані теми