Рекурсія та її реалізація в середовищі Python

Рекурсія та її реалізація в середовищі Python

Функції

Раніше була задача обчислення числа сполучень з n елементів по k, для чого необхідно обчислення факторіалів трьох величин: n, k і n-k. Для цього можна зробити три цикли, що призводить до збільшення розміру програми за рахунок триразового повторення схожого коду. Замість цього краще зробити одну функцію, яка обчислює факторіал будь-якого даного числа n і тричі скористатися цією функцією в своїй програмі. Відповідна функція може виглядати так:

 def factorial (n):

    f = 1

    for i in range (2, n + 1):

        f * = i

    return f

Цей текст повинен йти на початку програми, вірніше, до того місця, де ми захочемо скористатися функцією factorial. Перший рядок цього прикладу є описом нашої функції. factorial - ідентифікатор, тобто ім'я нашої функції. Після ідентифікатора в круглих дужках йде список параметрів, які отримує наша функція. Список складається з перерахованих через кому ідентифікаторів параметрів. У нашому випадку список складається з однієї величини n. В кінці рядка ставиться двокрапка.

Далі йде тіло функції, оформлене у вигляді блоку, тобто з відступом. Усередині функції обчислюється значення факторіала числа n і воно зберігається в змінної f. Функція завершується інструкцією return f, яка завершує роботу функції і повертає значення змінної f. Інструкція return може зустрічатися в довільному місці функції, її виконання завершує роботу функції і повертає вказане значення в місце виклику.

Якщо функція не повертає значення, то інструкція return використовується без значення, що повертається, також у функціях, які не повертають значення, інструкція return може бути відсутнім.

Тепер ми можемо використовувати нашу функцію кілька разів. У цьому прикладі ми тричі викликаємо функцію factorial для обчислення трьох факториалов: factorial (n), factorial (k), factorial (n-k).

n = int (input ())

k = int (input ())

print factorial (n) // (factorial (k) * factorial (n - k))

Ми також можемо, наприклад, оголосити функцію binomial, яка приймає два цілочисельних параметра n і k і обчислює число поєднань з n по k:

 def binomial(n, k)

    return factorial(n)//(factorial (k)*factorial(n - k))

Тоді в нашій основній програмі ми можемо викликати функцію binomial для знаходження числа сполучень:

print binomial (n, k)

Повернемося до задачі знаходження найбільшого з двох або трьох чисел. Функцію знаходження максимуму з двох чисел можна написати так:

 def max (a, b):

    if a> b:

        return a

    else:

        return b

Тепер ми можемо реалізувати функцію max3, що знаходить максимум трьох чисел:

 def max3(a, b, c):

    return max(max(a, b), c)

Функція max3 двічі викликає функцію max для двох чисел: спочатку, щоб знайти максимум з a і b, потім щоб знайти максимум з цієї величини і c.

---------------------------------------------------------------------------------------------------------------------

Локальні і глобальні змінні

Усередині функції можна використовувати змінні, оголошені поза цієї функції

 def f():

    print a

a = 1

f()

Тут змінній a присвоюється значення 1, і функція f друкує це значення, незважаючи на те, що вище функції f ця змінна не ініціалізується. Але в момент виклику функції f змінної a вже присвоєно значення, тому функція f може вивести його на екран.

Такі змінні (оголошені поза функцією, але доступні всередині функції) називаються глобальними.

Але якщо форматувати якусь змінну всередині функції, використовувати цю змінну поза функції не вдасться,

наприклад:

 def f():

    a = 1

f()

print (a)

Отримаємо NameError: name 'a' is not defined. Такі змінні, оголошені всередині функції, називаються локальними. Ці змінні стають недоступними після виходу з функції.

Цікавим вийде результат, якщо спробувати змінити значення глобальної змінної всередині функції:

 def f():

    a = 1

    print(a)

a = 0

f()

print (a)

Будуть виведені числа 1 і 0. Тобто незважаючи на те, що значення змінної a змінилося всередині функції, то поза функцією воно залишилося колишнім! Це зроблено з метою "захисту" глобальних змінних від випадкової зміни з функції (наприклад, якщо функція буде викликана з циклу по змінній i, а в цій функції буде використана змінна i також для організації циклу, то ці змінні повинні бути різними). Тобто якщо всередині функції модифікується значення деякої змінної, то змінна з таким ім'ям стає локальної змінної, і її модифікація не приведе до зміни глобальної змінної з таким же ім'ям.

Більш формально: інтерпретатор Пітон вважає змінну локальної, якщо всередині неї є хоча б одна інструкція, що модифікує значення змінної (це може бути оператор =, + = і т.д., або використання цієї змінної в якості параметра циклу for, то ця змінна вважається локальної і не може бути використана до ініціалізації. При цьому навіть якщо інструкція, що змінює змінну ніколи не буде виконана: інтерпретатор це перевірити не може, і змінна все одно вважається локальної. Приклад:

 def f():

    print(a)

    if False:

        a = 0

a = 1

f()

Виникає помилка: UnboundLocalError: local variable 'a' referenced before assignment. А саме, у функції f ідентифікатор a стає локальної змінної, тому що в функції є команда, що модифікує змінну a, нехай навіть ніколи і не виконується (але інтерпретатор не може це відстежити). Тому висновок змінної a призводить до звернення до неініціалізованої локальної змінної.

Щоб функція могла змінити значення глобальної змінної, необхідно оголосити цю змінну всередині функції, як глобальну, за допомогою ключового слова global:

def f():

    global a

    a = 1

    print(a)

a = 0

f()

print(a)

У цьому прикладі на екран буде виведено 1   1, так як змінна a оголошена, як глобальна, і її зміна всередині функції призводить до того, що і поза функцією змінна буде доступна.

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

Якщо потрібно, щоб функція повернула не одне значення, а два або більше, то для цього функція може повернути кортеж з двох або кількох значень:

 return (a, b)

Тоді результат виклику функції теж потрібно присвоювати кортежу:

 (N, m) = f (a, b)

---------------------------------------------------------------

Рекурсія

        епіграф:

def ShortStory():

    print( "У попа була собака, він її любив.")

    print( "Вона з'їла шматок м'яса, він її убив,")

    print( "В землю закопав і напис написав:")

ShortStory ()

Як ми бачили вище, функція може викликати іншу функцію. Але функція також може викликати і саму себе! Розглянемо це на прикладі функції обчислення факторіала. Добре відомо, що 0! = 1, 1! = 1. А як обчислити величину n! для великого n?

Якби ми могли вирахувати величину (n-1)! , то тоді ми легко обчислимо n !, оскільки n! = N (n-1) !. Але як обчислити (n-1) !? Якби ми вирахували (n-2) !, то ми зможемо обчислювальні і (n-1)! = (N-1) (n-2) !. А як обчислити (n-2) !? Якби ... Зрештою, ми дійдемо до величини 0 !, яка дорівнює 1. Таким чином, для обчислення факторіала ми можемо використовувати значення факторіала для меншого числа. Це можна зробити і в програмі на C ++:

 def factorial(n):

    if n == 0:

        return 1

    else:

        return n * factorial(n-1)

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

Рекурсивні функції є потужним механізмом у програмуванні. На жаль, вони не завжди ефективні (про це мова піде пізніше). Також часто використання рекурсії призводить до помилок, найбільш поширена з таких помилок - нескінченна рекурсія, коли ланцюжок викликів функцій ніколи не завершується і триває, поки не скінчиться вільна пам'ять в комп'ютері. Приклад нескінченної рекурсії наведено в епіграфі до цього розділу. Дві найбільш поширені причини для нескінченної рекурсії:

- Неправильне оформлення виходу з рекурсії. Наприклад, якщо ми в програмі обчислення факторіала забудемо поставити перевірку

 if n == 0, то factorial (0) викличе factorial (-1), той викличе factorial (-2) і т.д.

- Рекурсивний виклик з неправильними параметрами. Наприклад, якщо функція factorial (n) буде викликати factorial (n), то також вийти нескінченний ланцюжок.

Тому при розробці рекурсивної функції необхідно перш за все оформляти умови завершення рекурсії і думати, чому рекурсія коли-небудь завершить роботу.

Розглянемо кілька прикладів (насправді ці приклади є «навчальними» і всі перераховані завдання набагато краще вирішувати за допомогою циклів, а не рекурсією).

Обчислення суми натуральних чисел від 1 до n

Якщо, то сума дорівнює. Інакше сума чисел від до дорівнює сумі чисел від до, яку можна обчислити за допомогою рекурсії плюс число n.

def sum(n):

    if n == 1:

        return 1

    else:

        return n + sum (n - 1)

Перевірка рядка на паліндромність

Рядок є паліндромом, якщо вона однаково читається як справа наліво, так і зліва направо. Напишемо функцію IsPalindrome, яка повертає значення типу bool в залежності від того, чи є рядок паліндромом.

Крайнє значення - порожній рядок або рядок з одного символу завжди паліндром. Рекурсивний перехід - рядок є паліндромом, якщо у неї збігаються перший і останній символ, а також рядок, отримана видаленням першого і останнього символу є паліндромом.

def IsPalindrome (S):

    if len(S)<=1:

        return True

    else:

        return S[0] == S[-1] and IsPalindrome(S[1:-1])

Підсумовування списку

Дан список чисел, необхідно підсумувати його.

Крайній випадок - порожній список, сума чисел у ньому дорівнює 0. Інакше потрібно обчислити суму чисел в зрізі списку без одного елемента і додати значення цього елемента.

def Sum (A):

    if len(A) == 0:

        return 0

    else:

        return Sum(A[:-1])+A[-1]

Найбільше значення в списку

Дано список чисел, необхідно знайти найбільше значення в ньому.

Крайній випадок - список з одного елемента, найбільше значення в ньому так само єдиному елементу. Інакше потрібно обчислити найбільше значення в зрізі списку без одного елемента і взяти максимум з цього числа і значення цього елемента.

def Max(A):

    if len(A) == 1:

        return A[0]

    else:

        return max(Max(A[:-1]), A[-1])

Числа Фібоначчі

Числа Фібоначчі - це ряд чисел, в якому кожне наступне число дорівнює сумі двох попередніх: 1, 1, 2, 3, 5, 8, 13, .... Іноді ряд починають з нуля: 0, 1, 1, 2, 3, 5, .... В даному випадку ми будемо дотримуватися першого варіанту.

Формула:

F1 = 1

F2 = 1

Fn = Fn-1 + Fn-2

Приклад обчислення:

F3 = F2 + F1 = 1 + 1 = 2

F4 = F3 + F2 = 2 + 1 = 3

F5 = F4 + F3 = 3 + 2 = 5

F6 = F5 + F4 = 5 + 3 = 8

1.

def Fib(n):

    if n<=1:

        return n

    else:

        return Fib(n-1)+Fib(n-2)

2.

def fibonacci(n):

    if n in (1, 2):

        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))

--------------------------------------------------------------------------------------------------------------------

Запитання

1. Навіщо використовуються функції користувача?

2. Як описується функція та яким має бути її ім’я?

3. Коли та навіщо використовується інструкція return?

4. Які правила розташування визначень функцій користувача?

5. Які змінні називаються локальними і які глобальними ?

6. Що таке рекурсія і в яких задачах її можна використовувати ?