Рекурсия в Python (part 2)

В данном уроке мы продолжим знакомиться с рекурсией и разберем решение нескольких задач

Задача 1

Первая задача, которую мы рассмотрим, будет связана со строками. По условию на вход программе подается строка, а наша программа должна добавить открывающиеся и закрывающиеся скобки между символами по следующему примеру: "example" -> "(e(x(a(m)p)l)e)"

Решение задачи следующее:

def f(s):
    if len(s)==1 or len(s)==2:
        return s
    return s[0]+'('+f(s[1:-1])+')'+s[-1]

s=input()
print(f(s))

Подробности о том, как работает данная программа, смотрите в видео.

Задача 2. Возведение в степень

При помощи рекурсии необходимо возвести число x в целую стпень n

def power(x, n):
    if n == 0:
        return 1
    if n < 0:
        return 1 / power(x, -n)
    if n % 2 == 0:
        return power(x, n // 2) * power(x, n // 2)
    else:
        return power(x, n - 1) * x

x = int(input())
n = int(input())
print(power(x, n))

Подробности работы программы смотрите в видео.

Задача 3. Рекурсивный обход списка

Нужно обойти элементы многомерного списка с указанием уровня вложенности, на котором располагаются эти элементы.

a = [1, 2, [2, 3, 4, [3, 4, [2, 3], 5]]]
            
def rec(spicok, level=1):
    print(*spicok, 'level=', level)
    for i in spicok:
        if type(i) == list:
            rec(i, level + 1)
            
rec(a)