20. Написание рекурсивных функций

Рекурсивной называется функция, внутри которой встречается вызов этой же функции, но с другими параметрами. Такая рекурсия называется простой.

Косвенной называется рекурсия, когда вызов функции осуществляется опосредованно: функция A вызывает функцию B, а функция B вызывает функцию A.

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

Общий формат записи рекурсивной функции:

def func(arg):

if граничные_условия:

return значение

else:

return выражение_с_рекурсивным_вызовом

Например, факториал числа

n!=1*2*...*(n-1)*n = (n-1)! * n,

0! = 1! = 1.

Т.е. n! выражается через (n-1)!

def fact(n):

if n == 0 or n == 1:

return 1

else:

return fact(n-1) * n

print('1! =', fact(1))

print('5! =', fact(5))

Рекурсивными могут функции, которые не возвращают значения.

Рассмотрим функцию для перевода десятичного числа в систему счисления (СС) с основанием n<10

def trans(a, n=2):

#если не указывать основание СС,

# то число переводится в 2-ичную СС

if a > 0:

trans(a//n, n) #переводим сначала целцю часть от деления a на n

print(a % n, end='')#выводим остатое от деления a на n

print()

trans(14)#перевод числа 14 в 2-ичную систему счисления

print()

trans(14, 3)#перевод числа 14 в 3-ичную систему счисления

print()

trans(14, 8)#перевод числа 14 в 8-ичную систему счисления

21. Анонимные функции (lambda-выражение)

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

func = lambda x, y: x+y

print(func(4, 10))

print(func('Ivan ', 'Ivanov '))

Вывод: 14, Ivan Ivanov

Анонимные функции чаще всего используют внутри других стандартных функций, например, в sorted, filter, map, reduce и других.

Например, имеется последовательность чисел, вывести только четные элементы

s = [5, 4, 8, 6, 2, 1, 7]

s = filter(lambda x: x % 2 == 0, s)

print(*s)

Вывод: 4 8 6 2

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

In [18]:

d = {'bol': 3, 'map':5, 'ring': 2, 'apple':3, 'number':3, 'doll': 5, 'look':3}

d = sorted(d.items(), key=lambda x: (-x[1], x[0]))

print(d)

[('doll', 5), ('map', 5), ('apple', 3), ('bol', 3), ('look', 3), ('number', 3), ('ring', 2)]

• Анонимная функция может иметь 0 или более параметров, но в теле функции есть только одно выражение (expression). Значение выражения является возвращенным значением функции. Но нельзя использовать оператор return сразу перед выражением.

• Список параметров разделен запятой, и не должен быть в круглых скобках ( ).

• В теле анонимной функции вы не можете иметь доступ к переменным снаружи, вы можете только иметь доступ к параметрам.

• Анонимная функция не может вызвать напрямую функцию print, так как lambda требует выражение.