Главная » Языки программирования

Программы с рекурсией питон

Содержание
  1. Программы с рекурсией питон
  2. Рекурсивная функция в python
  3. Рекурсивные функции
  4. Вкратце о факториалах
  5. Детали работы рекурсивной функции
  6. Как работает рекурсия
  7. Рекурсивно или итеративно?
  8. Примеры программ с использованием рекурсии на языке Python

Программы с рекурсией питон

  • Program for Tower of Hanoi Algorithm
  • Time Complexity Analysis | Tower Of Hanoi (Recursion)
  • Find the value of a number raised to its reverse
  • Recursively remove all adjacent duplicates
  • Print 1 to n without using loops
  • Print N to 1 without loop
  • Sort the Queue using Recursion
  • Reversing a queue using recursion
  • Mean of array using recursion
  • Binary to Gray code using recursion
  • Sum of natural numbers using recursion
  • Delete a linked list using recursion
  • Product of 2 Numbers using Recursion
  • Decimal to binary number using recursion
  • Sum of array elements using recursion
  • How to Sort a Stack using Recursion
  • Reverse a Doubly linked list using recursion
  • Programs for Printing Pyramid Patterns using Recursion
  • DFS traversal of a Tree
  • Length of longest palindromic sub-string : Recursion
  • Count Set-bits of number using Recursion
  • Print reverse of a string using recursion
  • Print Fibonacci Series in reverse order using Recursion
  • Java Program to Reverse a Sentence Using Recursion
  • Program for length of a string using recursion
  • Sum of digit of a number using recursion
  • Program to calculate value of nCr using Recursion
  • Find geometric sum of the series using recursion
  • Bottom View of a Binary Tree using Recursion
  • Convert a String to an Integer using Recursion
  • Tail recursion to calculate sum of array elements.
  • Write an Interview Experience
  • Share Your Campus Experience
  • Introduction to Recursion – Data Structure and Algorithm Tutorials
  • What is Recursion?
  • Difference between Recursion and Iteration
  • Types of Recursions
  • Finite and Infinite Recursion with examples
  • What is Tail Recursion
  • What is Implicit recursion?
  • Why is Tail Recursion optimization faster than normal Recursion?
  • Recursive Functions
  • Difference Between Recursion and Induction
  • Program for Tower of Hanoi Algorithm
  • Time Complexity Analysis | Tower Of Hanoi (Recursion)
  • Find the value of a number raised to its reverse
  • Recursively remove all adjacent duplicates
  • Print 1 to n without using loops
  • Print N to 1 without loop
  • Sort the Queue using Recursion
  • Reversing a queue using recursion
  • Mean of array using recursion
  • Binary to Gray code using recursion
  • Sum of natural numbers using recursion
  • Delete a linked list using recursion
  • Product of 2 Numbers using Recursion
  • Decimal to binary number using recursion
  • Sum of array elements using recursion
  • How to Sort a Stack using Recursion
  • Reverse a Doubly linked list using recursion
  • Programs for Printing Pyramid Patterns using Recursion
  • DFS traversal of a Tree
  • Length of longest palindromic sub-string : Recursion
  • Count Set-bits of number using Recursion
  • Print reverse of a string using recursion
  • Print Fibonacci Series in reverse order using Recursion
  • Java Program to Reverse a Sentence Using Recursion
  • Program for length of a string using recursion
  • Sum of digit of a number using recursion
  • Program to calculate value of nCr using Recursion
  • Find geometric sum of the series using recursion
  • Bottom View of a Binary Tree using Recursion
  • Convert a String to an Integer using Recursion
  • Tail recursion to calculate sum of array elements.
Читайте также:  Тег INPUT, атрибут value

Источник

Рекурсивная функция в python

Рекурсию не очень просто понять при первом знакомстве, но без ее понимания в разработке будет тяжело. В этом материале рассмотрим:

  • Рекурсивную функцию поиска факториала.
  • Как рекурсивные функции работают в коде.
  • Действительно ли рекурсивные функции выполняют свои задачи лучше итеративных?

Рекурсивные функции

Рекурсивная функция — это та, которая вызывает сама себя.

В качестве простейшего примера рассмотрите следующий код:

 
def factorial_recursive(n): 
if n == 1: 
return n 
else: 
return n*factorial_recursive(n-1) 
 
Вызывая рекурсивную функцию здесь и передавая ей целое число, вы получаете факториал этого числа (n!).
 
Вкратце о факториалах
 
Факториал числа — это число, умноженное на каждое предыдущее число вплоть до 1.
 
 
Например, факториал числа 7:
7! = 7*6*5*4*3*2*1 = 5040
 
 
Вывести факториал числа можно с помощью функции:
 
 
num = 3 
print(f"Факториал это ") 
 
Эта функция выведет: «Факториал 3 это 6». Еще раз рассмотрим эту рекурсивную функцию:
 
def factorial_recursive(n): . 
 
По аналогии с обычной функцией имя рекурсивной указывается после def , а в скобках обозначается параметр n :
 
def factorial_recursive(n): if n == 1: return n else: return n*factorial_recursive(n-1)
 
Благодаря условной конструкции переменная n вернется только в том случае, если ее значение будет равно 1. Это еще называют условием завершения. Рекурсия останавливается в момент удовлетворения условиям.
 
def factorial_recursive(n): if n == 1: return n else: return n*factorial_recursive(n-1)
 
В коде выше выделен фрагмент самой рекурсии. В блоке else условной конструкции возвращается произведение n и значения этой же функции с параметром n-1 .
 
Это и есть рекурсия. В нашем примере это так сработало:
 
3 * (3-1) * ((3-1)-1) # так как 3-1-1 равно 1, рекурсия остановилась
 
Детали работы рекурсивной функции
 
Чтобы еще лучше понять, как это работает, разобьем на этапы процесс выполнения функции с параметром 3.
 
Для этого ниже представим каждый экземпляр с реальными числами. Это поможет «отследить», что происходит при вызове одной функции со значением 3 в качестве аргумента:
 
 
# Первый вызов 
factorial_recursive(3): 
if 3 == 1: 
return 3 
else: 
return 3*factorial_recursive(3-1) 
 
# Второй вызов 
factorial_recursive(2): 
if 2 == 1: 
return 2 
else: 
return 2*factorial_recursive(2-1) 
 
# Третий вызов 
factorial_recursive(1): 
if 1 == 1: 
return 1 
else: 
return 1*factorial_recursive(1-1) 
 
Рекурсивная функция не знает ответа для выражения 3*factorial_recursive(3–1) , поэтому она добавляет в стек еще один вызов.
 
Как работает рекурсия
 
/\ factorial_recursive(1) - последний вызов || factorial_recursive(2) - второй вызов || factorial_recursive(3) - первый вызов
 
Выше показывается, как генерируется стек. Это происходит благодаря процессу LIFO (last in, first out, «последним пришел — первым ушел»). Как вы помните, первые вызовы функции не знают ответа, поэтому они добавляются в стек.
 
Но как только в стек добавляется вызов factorial_recursive(1) , для которого ответ имеется, стек начинает «разворачиваться» в обратном порядке, выполняя все вычисления с реальными значениями. В процессе каждый из слоев выпадает в процессе.
 
     
  • factorial_recursive(1) завершается, отправляет 1 в
    •  
  • factorial_recursive(2) и выпадает из стека.
    •  
  • factorial_recursive(2) завершается, отправляет 2*1 в
    •  
  • factorial_recursive(3) и выпадает из стека. Наконец, инструкция else здесь завершается, возвращается 3 * 2 = 6, и из стека выпадает последний слой.
    •  
 
Рекурсия в Python имеет ограничение в 3000 слоев.
 
 
>>> import sys 
>>> sys.getrecursionlimit() 
3000 
 
Рекурсивно или итеративно?
 
Каковы же преимущества рекурсивных функций? Можно ли с помощью итеративных получить тот же результат? Когда лучше использовать одни, а когда — другие?
 
Важно учитывать временную и пространственную сложности. Рекурсивные функции занимают больше места в памяти по сравнению с итеративными из-за постоянного добавления новых слоев в стек в памяти. Однако их производительность куда выше.
 
 
Рекурсия может быть медленной, если реализована неправильно
 
 
Тем не менее рекурсия может быть медленной, если ее неправильно реализовать. Из-за этого вычисления будут происходить чаще, чем требуется.
 
Написание итеративных функций зачастую требуется большего количества кода. Например, дальше пример функции для вычисления факториала, но с итеративным подходом. Выглядит не так изящно, не правда ли?
 
 
def factorial_iterative(num): 
factorial = 1 
if num < 0:
print("Факториал не вычисляется для отрицательных чисел") 
else: 
for i in range (1, num + 1): 
factorial = factorial*i 
print(f"Факториал это ") 
 
Источник
 
Примеры программ с использованием рекурсии на языке Python
 
В этом разделе мы рассмотрим программы на языке Python, в которых используется рекурсия.
 
Рекурсия — это способ задания алгоритма вычисления функции с использованием вызова ею самой себя. Функция, которая вызывает сама себя, называется рекурсивной.
 
Рекурсивный метод решения задач применяется, когда задачу можно разбить на одинаковые подзадачи, которые в свою очередь также можно разбить. И так много раз подряд.
 
Здесь мы рассмотрим примеры программ для определения четности числа, нахождения чисел Фибоначчи и вычисления факториала числа. Также мы разберем программы для поиска наименьшего общего кратного (НОК) и наибольшего общего делителя (НОД) с использованием рекурсии, а еще — программу проверки числа на простоту. Другие программы в этом разделе содержат алгоритмы обращения строки, вычисления длинны списка, нахождения суммы данных чисел. Все это, разумеется, будет делаться с использованием рекурсии.
 
     
  • определение четности числа с использованием рекурсии
    •  
  • рекурсивный поиск количества вхождений заданной буквы в строке
    •  
  • вывод чисел Фибоначчи с использованием рекурсии
    •  
  • вычисление факториала числа с использованием рекурсии
    •  
  • вычисление с помощью рекурсии суммы элементов списка
    •  
  • перевод числа в двоичную систему счисления с использованием рекурсии
    •  
  • вычисление суммы цифр числа при помощи рекурсии
    •  
  • рекурсивный поиск наименьшего общего кратного (НОК)
    •  
  • рекурсивный поиск наибольшего общего делителя
    •  
  • проверка числа на простоту с использованием рекурсии
    •  
  • вычисление произведения двух чисел с использованием рекурсии
    •  
  • возведение числа в степень при помощи рекурсии
    •  
  • проверка, является ли строка палиндромом, с использованием рекурсии
    •  
  • вывод строки в обратном порядке с использованием рекурсии
    •  
  • преобразование списка, состоящего из списков, в обычный список (с использованием рекурсии)
    •  
  • вычисление суммы элементов списка, содержащего вложенные списки, с использованием рекурсии
    •  
  • нахождение длины списка при помощи рекурсии.
    •  
 
Источник
Оцените статью
© 2024 Программирование