Питон рекурсивные функции задачи

Структуры и алгоритмы данных Python: рекурсия — упражнения, практика, решение

Структуры данных и алгоритмы: рекурсия [11 упражнений с решением]

[ Внизу страницы доступен редактор для написания и выполнения сценариев. ]

1. Напишите программу на Python для расчета суммы списка чисел. Перейти к редактору
Нажмите меня, чтобы увидеть образец решения

2. Напишите программу на Python для преобразования Integer в строку в любой базе. Перейти к редактору
Нажмите меня, чтобы увидеть образец решения

3. Напишите на Python программу списка рекурсивных сумм. Перейти к редактору
Данные испытаний: [1, 2, [3,4], [5,6]]
Ожидаемый результат: 21
Нажмите меня, чтобы увидеть образец решения

4. Напишите программу на Python, чтобы получить факториал неотрицательного целого числа. Перейти к редактору
Нажмите меня, чтобы увидеть образец решения

5. Напишите программу на Python для решения последовательности Фибоначчи с помощью рекурсии. Перейти к редактору
Нажмите меня, чтобы увидеть образец решения

6. Напишите программу на Python, чтобы получить сумму неотрицательного целого числа. Перейти к редактору
Тестовые данные :
sumDigits (345) -> 12
sumDigits (45) -> 9
Нажмите меня, чтобы увидеть образец решения

7. Напишите программу на Python для вычисления суммы натуральных чисел n + (n-2) + (n-4) . (до тех пор, пока nx = <0). Перейти к редактору
Тестовые данные :
sum_series (6) -> 12
sum_series (10) -> 30
Нажмите меня, чтобы увидеть образец решения

8. Напишите программу на Python для расчета гармонической суммы n-1. Перейти к редактору
Примечание : гармоническая сумма является суммой обратных значений натуральных чисел.
Пример :

Нажмите меня, чтобы увидеть образец решения

9. Напишите программу на Python для расчета геометрической суммы n-1. Перейти к редактору
Примечание . В математике геометрический ряд — это ряд с постоянным соотношением между последовательными членами.
Пример :

10. Напишите программу на Python для вычисления значения «a» в степени «b». Перейти к редактору
Тестовые данные :
(мощность (3,4) -> 81
Нажмите меня, чтобы увидеть образец решения

11. Напишите программу на Python, чтобы найти наибольший общий делитель (gcd) из двух целых чисел. Перейти к редактору
Нажмите меня, чтобы увидеть образец решения

Редактор кода Python:

Еще не все !

Не отправляйте решение вышеупомянутых упражнений здесь, если вы хотите внести вклад, перейдите на соответствующую страницу упражнения.

Источник

Примеры программ с использованием рекурсии на языке Python

В этом разделе мы рассмотрим программы на языке Python, в которых используется рекурсия.

Рекурсия — это способ задания алгоритма вычисления функции с использованием вызова ею самой себя. Функция, которая вызывает сама себя, называется рекурсивной.

Рекурсивный метод решения задач применяется, когда задачу можно разбить на одинаковые подзадачи, которые в свою очередь также можно разбить. И так много раз подряд.

Здесь мы рассмотрим примеры программ для определения четности числа, нахождения чисел Фибоначчи и вычисления факториала числа. Также мы разберем программы для поиска наименьшего общего кратного (НОК) и наибольшего общего делителя (НОД) с использованием рекурсии, а еще — программу проверки числа на простоту. Другие программы в этом разделе содержат алгоритмы обращения строки, вычисления длинны списка, нахождения суммы данных чисел. Все это, разумеется, будет делаться с использованием рекурсии.

• определение четности числа с использованием рекурсии
• рекурсивный поиск количества вхождений заданной буквы в строке
• вывод чисел Фибоначчи с использованием рекурсии
• вычисление факториала числа с использованием рекурсии
• вычисление с помощью рекурсии суммы элементов списка
• перевод числа в двоичную систему счисления с использованием рекурсии
• вычисление суммы цифр числа при помощи рекурсии
• рекурсивный поиск наименьшего общего кратного (НОК)
• рекурсивный поиск наибольшего общего делителя
• проверка числа на простоту с использованием рекурсии
• вычисление произведения двух чисел с использованием рекурсии
• возведение числа в степень при помощи рекурсии
• проверка, является ли строка палиндромом, с использованием рекурсии
• вывод строки в обратном порядке с использованием рекурсии
• преобразование списка, состоящего из списков, в обычный список (с использованием рекурсии)
• вычисление суммы элементов списка, содержащего вложенные списки, с использованием рекурсии
• нахождение длины списка при помощи рекурсии.

Источник

Решение модуля 7.8 Инди-курс программирования на Python

Модуль 7.8 (Рекурсия в Python. Рекурсивная функция Часть 1). Рекурсия – определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.

Что произойдет, если в рекурсивной функции не будет условия выхода?

RecursionError: maximum recursion

RecursionError: maximum recursion

Рекурсивная функция при большом числе повторов неоптимальна из-за высокой нагрузки. Отсутствие выхода из рекурсивной функции чаще всего является ошибкой программиста.

Определите функцию print_from , которая принимает одно натуральное число n и распечатывает на экране убывающую последовательность целых чисел от n до 1 включительно. Каждое число необходимо выводить на отдельной строке.

Ваша задача только написать определение функции print_from

def print_from(n: int) -> None: print(n) # выводим первое число if n > 1: # если число больше 1, вызываем саму функцию, но число уменьшаем на 1 print_from(n - 1)

def print_from(n: int) -> None:
print(n) #выводим первое число
if n > 1: #если число больше 1, вызываем саму функцию, но число уменьшаем на 1
print_from(n — 1)

def print_to(n: int) -> None: if n > 0: # если заданное число больше нуля print_to(n - 1) # вызываем функцию но переданную print(n) # выводим числа от 1 до заданного числа

Дано натуральное число N и последовательность из N элементов. Требуется вывести эту последовательность в обратном порядке.

def rev(n): # объявляем функцию if n > 0: # условие выхода из рекурсии. Пока n > 0 буем выполнять все что ниже в ветке if rev(n-1) # рекурсивный вызов функцию rev(n-1). Когда мы в коде натыкаемся на эту строчку ev(n-1) выполнение программы прерывается и в стек сохраняется исходный аргумент , а сам рекурсивный вызов функции происходи при (n-1) и так по кругу пока не достигнем нуля (n = 0). В этот момент рекурсивный вызов прерывается (так как сработало условие if) и исполнение кода наконец-то переходит к строке print. print(sp[-n], end=" ") # выводим данную последовательность N = int(input()) # получаем натуральное число N sp = list(map(int, input().split())) #и получаем последовательность из N элементов. Сразу создаем список rev(N) # Вызываем функцию

Описать рекурсивную функцию double_fact , которая принимает на вход целое число и вычисляет значение двойного факториала по формуле:

double_fact(7) => 105 double_fact(4) => 8 double_fact(1) => 1 double_fact(10) => 3840

Ваша задача только написать определение функции double_fact

def double_fact(n): # объявляем функцию if n == 1: # условие выхода из рекурсии при n =1 return 1 # возвращаем 1 if n == 2: # еще одно условие выхода из рекурсии при n =2 return 2 # возвращаем 2 f = n * double_fact(n - 2) # рекурсивный вызов функцию double_fact(n - 2) return f # возвращение результата вычисления

Последовательностью Фибоначчи называется последовательность чисел a₀, a₁, …, a_n, …, где число, стоящее на n-ой позиции можно вычислить по формуле:

Требуется найти N-е число Фибоначчи.

def fib(n): if n==0: # если порядковый номер(введенный) равен 0, то возвращаем ноль return 0 if n==1: # если порядковый номер(введенный) равен 1, выводим 1 return 1 return fib(n-1) + fib(n-2) # иначе вызываем сумму функций с числом уменьшенным на 1 и числом уменьшенным на 2 print(fib(int(input ()))) # вызываем функцию

Описать рекурсивную функцию tribonacci , которая принимает на вход целое число n — порядковый номер чисел Трибоначчи. Функция по параметру n должна вычислить и вернуть значение, стоящее на n-м месте в ряде чисел Трибоначчи

Вот примере вызовов:

tribonacci(0) => 0 tribonacci(2) => 1 tribonacci(4) => 2 tribonacci(6) => 7 tribonacci(7) => > 13

Ваша задача только написать определение функции tribonacci

def tribonacci(n): # объявляем функцию, принимающую порядковый номер нужного числа из ряда Трибоначчи if n==0: # если задали 0 - возвращаем 0, т.к. первое(с индексом 0) число в ряду - 0 return 0 if n==1: # если задали 1 - возвращаем 0, т.к. второе(с индексом 1) число в ряду - 0 return 0 if n==2: # если задали 2 - возвращаем 1, т.к. третье(с индексом 2) число в ряду - 1 return 1 return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3) # иначе если задали число больше 2, возвращаем сумму функций с уменьшенным числом на 1, на 2, на 3

Описать рекурсивную функцию get_combin , которая принимает на вход два целых числа и находит C(N,K) — число сочетаний из N элементов по K — с помощью рекуррентного соотношения:

При этом гарантируется, что входные значения n и k будут удовлетворять следующим условиям:

• n > 0
• 0 ≤ k ≤ n

Вот примеры вызовов:

get_combin(5, 5) => 1 get_combin(5, 2) => 10 get_combin(3, 1) => 3 get_combin(7, 0) => 1

Ваша задача только написать определение функции get_combin

def get_combin(n: int, k:int) -> int: # объявляем функцию которая принимает 2 числа if k == 0 or n == 0: # если какое то из заданных чисел равно 0 - возвращаем 1 return 1 if k == n: # если 2 числа равны - возвращаем 1 return 1 return get_combin(n-1, k) + get_combin(n-1, k-1) # иначе возвращаем сумму результатов выполнения функций с уменьшенным первым числом на 1, и с функцией, у которого уменьшены оба числа на 1

Описать рекурсивную функцию ackermann , которая принимает на вход два целых числа m и n находит значение, определенное следующим образом:

Найденное значение функция ackermann должна вернуть в качестве результата

ackermann(3, 2) => 29 ackermann(3, 0) => 5 ackermann(1, 0) => 2 ackermann(3, 5) => 253

Ваша задача только написать определение функции ackermann

В тестовых примерах сперва поступает на вход значение аргумента m, затем аргумента n.

def ackermann(m: int, n: int) -> int: # объявляем функцию которая принимает 2 числа if m == 0: # если первое число равно 0, то возвращаем второе число увеличенное на 1 return n + 1 if m > 0 and n == 0: # если первое число положительное и второе число равно 0, вызываем функцию с уменьшенным на 1 первым числом return ackermann(m - 1, 1) return ackermann(m - 1, ackermann(m, n - 1)) # иначе вызываем функцию с уменьшенным на 1 первое число и в качестве второго числа вызываем функцию с уменьшенным вторым числом на 1

Напишите функцию list_sum_recursive , которая принимает на вход список из целых чисел и возвращает сумму элементов переданного списка. Не забывайте, что реализовать это нужно при помощи рекурсии.

Ваша задача только написать определение функции list_sum_recursive

def list_sum_recursive(a: list) -> int: # объявляем функцию, которая принимает список чисел if len(a) == 0: # если длина переданного списка равно 0, то и сумма будет равна нулю return 0 if len(a) == 1: # если длина переданного списка равна 1, то и сумма будет равна этому одному числу return a[0] return a[0] + list_sum_recursive(a[1:]) # иначе сумма первого числа и функции в которую передаётся список уже без первого числа (которая вызывает ещё 1 функцию, и так складываются все числа)

Представьте, что у нас есть список целых чисел неограниченной вложенности. То есть наш список может состоять из списков, внутри которых также могут быть списки. Ваша задача превратить все это в линейный список при помощи функции flatten

flatten([1, [2, 3, [4]], 5]) => [1, 2, 3, 4, 5] flatten([1, [2, 3], [[2], 5], 6]) => [1, 2, 3, 2, 5, 6] flatten([[[[9]]], [1, 2], [[8]]]) => [9, 1, 2, 8]

Ваша задача только написать определение функции flatten

def flatten(sp: list) -> list: # объявляем функцию, которая принимает вложенный список new = [] # создаем пустой список, для создавания линейного списка for i in sp: # проходимся по введенному списку if type(i) is int: # если тип элемента число, то добавляем в новый список это число new.append(i) else: # иначе если это ещё 1 список, то для него вызываем функцию, которая добавить числа из него в новый список new += flatten(i) return new # возвращаем полученный список

Источник