20 практических заданий с рекурсией в Python. Python практика.

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

https://t.me/python_job_interview – в нашем канале еще больше полезных практических задач.

# 10 Простых заданий + 10 сложных заданий

Простые задания

1) Факториал

Напишите рекурсивную функцию factorial(n), которая будет принимать положительное целое число n и возвращать факториал от этого числа (1 x 2 x 3 x … x n).

factorial(1)   # 1
factorial(2)   # 2
factorial(3)   # 6
factorial(4)   # 24
factorial(5)   # 120
factorial(6)   # 720
factorial(7)   # 5040
factorial(8)   # 40320

2) Суммирование

Напишите рекурсивную функцию summation(n), которая будет принимать положительное целое число n и возвращать сумму чисел от 1 до n.

summation(1)  # 1
summation(2)  # 3
summation(3)  # 6
summation(4)  # 10
summation(5)  # 15
summation(6)  # 21
summation(7)  # 28
summation(8)  # 36

3) Сумма нечётных чисел

Напишите рекурсивную функцию sum_odd(lis), которая будет принимать список из целых чисел и возвращать сумму только нечётных чисел из списка.

sum_odd([1,2,3,4])    # 4
sum_odd([1,2,3,4,5])  # 9
sum_odd([1,2,4,6,8])  # 1
sum_odd([])           # 0
sum_odd([2,4,6,8])    # 0

 

4) Сумма нечётных чисел и вычитание чётных чисел

Напишите рекурсивную функцию sum_sub(list), которая будет принимать список целых чисел. Эта функция будет суммировать все нечётные числа и вычитать все чётные числа. В конце она будет возвращать получившееся значение.

sum_sub([1,2,3,4])   # -2 
sum_sub([1,2,3,4,5]) # 3
sum_sub([1,3,5])     # 9
sum_sub([2,4,6])     # -12
sum_sub([99,10,10])  # 79

5) Слова-палиндромы

Слова-палиндромы — это строки, которые одинаково читаются с обеих сторон. Например: «aba», «abba», «abcba», «aaa», «ababa» и так далее.

Напишите функцию is_palindrome(string), которая будет принимать строку и возвращать «True», если строка является палиндромом, и «False» во всех других случаях.

is_palindrome('aba')     # True
is_palindrome('abba')    # True
is_palindrome('abcba')   # True

is_palindrome('abc')     # False
is_palindrome('abbb')    # False
is_palindrome('abab')    # False

6) Палиндромы, игнорирующие пробелы

Напишите функцию is_pal(string), которая будет принимать строку и возвращать «True», если строка — палиндром (при этом игнорируя все пробелы), и «False» во всех других случаях.

is_pal('aba')      # True
is_pal('ab   a')   # True
is_pal(' a z  a')  # True

is_pal('ab a b')   # False
is_pal('a a  ba')  # False
is_pal('a z a a')  # False

7) Удаление гласных букв

Напишите функцию remove_vowels(string), которая будет принимать строку и возвращать только согласные буквы. 

remove_vowels('apple')     # ppl
remove_vowels('orange')    # rng
remove_vowels('pear')      # pr
remove_vowels('pineapple') # pnppl
remove_vowels('durian')    # drn
remove_vowels('banana')    # bnn

8) Удвоенные буквы

Напишите функцию double(string), которая будет принимать строки и возвращать другую версию строки, в которой все буквы будут удваиваться.

double('apple')   # aappppllee
double('orange')  # oorraannggee
double('pear')    # ppeeaarr
double('abc')     # aabbcc
double('zz')      # zzzz

9) Треугольник Паскаля

Треугольник Паскаля выглядит так: 

Напишите функцию pascal(n), которая будет принимать положительные целые числа n и возвращать n-ую строку треугольника Паскаля.

10) Число Фибоначчи

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

Числа Фибоначчи — это серия чисел, которая начинается с 0 и 1. Каждое последующее число будет являться суммой двух предыдущих чисел.

fib(1)   # 0
fib(2)   # 1
fib(3)   # 1
fib(4)   # 2
fib(5)   # 3
fib(6)   # 5
fib(7)   # 8
fib(8)   # 13
fib(9)   # 21
fib(10)  # 34

Менее выполнимые задания

11) Генерация перестановок

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

permutations([1,2,3], 2)

# [(1,2), (1,3), (2,3), (2,1), (3,1), (3,2)] 

permutations([1,2,3,4], 2)

# [(1,2), (1,3), (1,4), (2,1), (2,3), (2,4),
# (3,1), (3,2), (3,4), (4,1), (4,2), (4,3)]

Вы не должны пользоваться встроенными функциями, потому что это жульничество.

12) Генерация комбинаций

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

Combinations([1,2,3], 2)

# [(1,2), (1,3), (2,3)] 

permutations([1,2,3,4], 2)

# [(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)]

13) Поиск в глубину с использованием рекурсии

У вас есть словарь, который представляет из себя сеть друзей.

g = {
1: [2,3], # 1 is friends with 2 and 3
2: [1], # 2 is friends with 1
3: [1,4], # 3 is friends with 1 and 4
4: [3], # etc
5: [6],
6: [5,7],
7: [6]
} 

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

friends(1) # [1,2,3,4]
friends(2) # [1,2,3,4]
friends(3) # [1,2,3,4]
friends(4) # [1,2,3,4]

friends(5) # [5,6,7]
friends(6) # [5,6,7]
friends(7) # [5,6,7] 

14) Проверка наличия выхода в лабиринте

Вам дам список строк, который представляет из себя лабиринт. 

maze = [
  'S----',
  '##---',
  '---##',
  '----X'
]

s означает стартовую позицию (откуда игрок начинает);

x означает финиш (цель прохождения лабиринта);

– означает свободный путь, по которому может осуществлять движение игрок;

# означает стену, через которую игрок не может пройти.

Некоторые правила:

Игрок может двигаться только на 1 шаг за один раз;

Игрок может двигаться только в 4 направлениях: вверх, вниз, влево, вправо.

Лабиринт проходим, если игрок может пройти до x из s. Напишите рекурсивную функцию, которая будет принимать лабиринт и возвращать «True», если он проходим, и «False» в любом другом случае.

15) Прохождение лабиринта

Используя точно такой же лабиринт, как и в задании 14, напишите рекурсивную функцию, которая будет возвращать решение лабиринта, позволяющее игроку добраться до финиша.

maze = [
  'S----',
  '##---',
  '---##',
  '----X'
]

solve(maze) # ['right', 'right', 'down', 'down', 'down', 'right', 'right']

Это не обязательно должно быть короткое решение — любое возможное решение. Если лабиринт невозможно пройти, просто верните [].

16) Поиск VideoID

Вам дан неупорядоченный словарь, содержащий в себе несколько вложенных структур данных. Некоторые из них (независимо от вложенности) содержать ключ VideoID.

data = {
    "type": "video",
    "videoID": "vid001",
    "links": [
        {"type":"video", "videoID":"vid002", "links":[]},
        {   "type":"video", 
            "videoID":"vid003",
            "links": [
            {"type": "video", "videoID":"vid004"},
            {"type": "video", "videoID":"vid005"},
            ]
        },
        {"type":"video", "videoID":"vid006"},
        {   "type":"video",
            "videoID":"vid007",
            "links": [
            {"type":"video", "videoID":"vid008", "links": [
                {   "type":"video", 
                    "videoID":"vid009",
                    "links": [{"type":"video", "videoID":"vid010"}]
                }
            ]}
        ]},
    ]
}

Напишите рекурсивную функцию, целью которой будет извлечение всех значений с ключом «VideoID».

output = [
  {'videoID': 'vid001'}, {'videoID': 'vid002'}, 
  {'videoID': 'vid003'}, {'videoID': 'vid004'}, 
  {'videoID': 'vid005'}, {'videoID': 'vid006'}, 
  {'videoID': 'vid007'}, {'videoID': 'vid008'}, 
  {'videoID': 'vid009'}, {'videoID': 'vid010'}
]

17) Конвертирование множеств в списки во вложенной структуре данных

Вам дана неупорядоченная структура данных, которая содержит в себе списки, множества и словари. 

d = {'a': [
{1,2,3},
[1,2,3],
{1:1, 2:2, 3:3}
],
'b': [
[1,2,3],
{
1: {1,2,3,4},
2: {1,2,3,4},
3: {1,2,3,4}
}
]} 

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

output = {'a': [
      [1,2,3],
      [1,2,3],
      {1:1, 2:2, 3:3}
    ], 
    'b': [
      [1,2,3],
      {
        1: [1,2,3,4],
        2: [1,2,3,4],
        3: [1,2,3,4]
      }
    ]}

18) Наименьшее количество монет

Напишите рекурсивную функцию, которая будет принимать 1) значение 2) список монет и возвращать наименьшее количество монет, которые в сумме составляют значение.

coins(10, [2, 5])  # {5:2}

# 2 $5 coins make up $10
# 5 $2 coins also make up $10

# we chose 2 coins over 5 coins because fewer coins.
coins(8, [2, 5])  # {2:4}

# 4 $2 coins make up $8. This is the only solution
coins(11, [1,2,3]) # {3:3, 2:1}

# 3 $3 coins + 1 $2 coin make up $11
coins(11, [2,4]) # {}

# no solution

19) Рекурсия os.walk без использования функции os.walk.

Вам дана вложенная папка с вещами.

baseFolder
|- folderA
  |- folderAA
    |- 1.txt
  |- folderAB
  |- folderAC
  |- 2.txt
|- folderB
  |- folderBA
    |- 3.txt
    |- folderBAA
      |- 4.txt
      |- 5.txt
    |- folderBAB
    |- folderBAC
      |- 6.txt
  |- folderBB
|- folderC
  |- 7.txt
  |- folderCA
  |- folderCB

Без использования встроенной функции os.walk, напишите рекурсивную функцию, которая будет принимать путь к главной папке и подсчитывать количество подпапок + общее количество файлов.

output = {'numFolders':13, 'numFiles': 7} 

20) Ханойская башня

Цель этой игры — переместить все кольца из А в С.

Некоторые правила:

1. Вы можете двигать только одно кольцо за раз;

2. Большое кольцо не может находиться выше маленького.

Напишите рекурсивную функцию hanoi(n), которая будет принимать целочисленное число n, являющееся количеством колец, и выводить шаги для перемещения всех колец пирамиды от А до С.

hanoi(1)

# A to C
hanoi(2)

# A to B
# A to C
# B to C
hanoi(3)

# A to C
# A to B
# C to B
# A to C
# B to A
# B to C
# A to C

Заключение!

Надеюсь, что это было непросто!

Несколько финальных слов

Если эта статья оказалась полезной для вас, вы могли бы оказать мне поддержку (поставить лайк, поделиться ею с друзьями, )!