Рекурсія в Python
Термін рекурсія можна визначити як процес визначення чогось у термінах самого себе. Простими словами, це процес, у якому функція викликає саму себе прямо чи опосередковано.
Переваги використання рекурсії
- Складну функцію можна розділити на менші підпроблеми за допомогою рекурсії.
- Створення послідовності простіше через рекурсію, ніж використання будь-якої вкладеної ітерації.
- Рекурсивні функції роблять код простим і ефективним.
Недоліки використання рекурсії
- Рекурсивні виклики займають багато пам’яті та часу, що робить його дорогим у використанні.
- Рекурсивні функції складно налагодити.
- Міркування, що стоять за рекурсією, іноді важко продумати.
Синтаксис:
def func(): <-- | | (recursive call) | func() ----
Приклад 1: Послідовність Фібоначчі — це ціла послідовність чисел 0, 1, 1, 2, 3, 5, 8….
Python3
# Program to print the fibonacci series upto n_terms> # Recursive function> def> recursive_fibonacci(n):> > if> n <> => 1> :> > return> n> > else> :> > return> (recursive_fibonacci(n> -> 1> )> +> recursive_fibonacci(n> -> 2> ))> n_terms> => 10> # check if the number of terms is valid> if> n_terms <> => 0> :> > print> (> 'Invalid input ! Please input a positive value'> )> else> :> > print> (> 'Fibonacci series:'> )> for> i> in> range> (n_terms):> > print> (recursive_fibonacci(i))> |
Вихід
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
приклад 2: Факторіал числа 6 позначається як 6! = 1*2*3*4*5*6 = 720.
Python3
# Program to print factorial of a number> # recursively.> # Recursive function> def> recursive_factorial(n):> > if> n> => => 1> :> > return> n> > else> :> > return> n> *> recursive_factorial(n> -> 1> )> # user input> num> => 6> # check if the input is valid or not> if> num <> 0> :> > print> (> 'Invalid input ! Please enter a positive number.'> )> elif> num> => => 0> :> > print> (> 'Factorial of number 0 is 1'> )> else> :> > print> (> 'Factorial of number'> , num,> '='> , recursive_factorial(num))> |
Вихід
Factorial of number 6 = 720
Що таке хвостова рекурсія?
Унікальний тип рекурсії, де останньою процедурою функції є рекурсивний виклик. Рекурсія може бути автоматизована шляхом виконання запиту в поточному кадрі стека та повернення результату замість створення нового кадру стека. Хвостова рекурсія може бути оптимізована компілятором, що робить її кращою, ніж функції без хвостової рекурсії.
Чи можна оптимізувати програму, використовуючи хвостову рекурсивну функцію замість нехвістової рекурсивної функції?
Розглядаючи наведену нижче функцію для обчислення факториалу n, ми можемо помітити, що спочатку функція виглядає як хвостова рекурсивна, але це не рекурсивна функція. Якщо ми уважно спостерігаємо, то можемо побачити, що значення, яке повертає Recur_facto(n-1), використовується в Recur_facto(n), тому виклик Recur_facto(n-1) не останнє, що робить Recur_facto(n).
Python3
# Program to calculate factorial of a number> # using a Non-Tail-Recursive function.> # non-tail recursive function> def> Recur_facto(n):> > > if> (n> => => 0> ):> > return> 1> > > return> n> *> Recur_facto(n> -> 1> )> > # print the result> print> (Recur_facto(> 6> ))> |
Вихід
720
Ми можемо написати задану функцію Recur_facto як хвостову рекурсивну функцію. Ідея полягає в тому, щоб використати ще один аргумент, а в другому аргументі ми враховуємо значення факториала. Коли n досягне 0, поверніть кінцеве значення факториалу потрібного числа.
Python3
# Program to calculate factorial of a number> # using a Tail-Recursive function.> # A tail recursive function> def> Recur_facto(n, a> => 1> ):> > > if> (n> => => 0> ):> > return> a> > > return> Recur_facto(n> -> 1> , n> *> a)> > # print the result> print> (Recur_facto(> 6> ))> |
Вихід
720
