Рекурсія


Рекурсія - це виклик функції всередині самої себе.


Наприклад, у нас є коробка, в якій складені інші коробки. В одній з цих коробок є ключ. Потрібно його знайти.


Можна скористатись таким алгоритмом:

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. Підняти число до степеня

Рекурсивний варіант


Задача 2. Надрукувати числа від 1 до N


Задача 3. Надрукувати числа від N до 1


Задача 4Обчислити суму цифр числа


Задача 5. Перетворити число з десяткового у двійкове


Задача 6. Перетворити число з двійкового у десяткове


Задача 7. З клавіатури вводиться ціле число N. Надрукувати всі двійкові числа довжиною <=N.


Задача 8. Створити трикутник Паскаля:

        1

      1   1

    1   2   1

  1   3   3   1

1   4   6   4   1



Розв'язки самостійних задач:
 
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

Ще приклад рекурсивного вірша:


Задача
. Надрукувати вірш:

Ось хатка, яку збудував собі Джек


А це - комора, в коморі - пшениця,

З якої так смачно пекти паляницю

У хатці, яку збудував собі Джек.


А це - веселая пташка синиця,

Яка викрадає з комори пшеницю,

З якої так смачно пекти паляницю

У хатці, яку збудував собі Джек.


А це - кіт сміливо виходить з воріт,

Бо дуже він хоче спіймати синицю

Яка викрадає з комори пшеницю,

З якої так смачно пекти паляницю

У хатці, яку збудував собі Джек.



Задачі на рекурсію:

http://dn.hoippo.km.ua:8889/problems/?search=&category=8

https://www.e-olymp.com/uk/problems?query=%D1%84%D1%83%D0%BD%D0%BA%D1%86%D1%96%D1%8F&tag=56

Остання зміна: понеділок 13 липня 2020 4:30