Программирование на языке Python

1. Программирование на языке Python

1
Программирование
на языке Python
§ 61. Рекурсия
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

2. Что такое рекурсия?

Алгоритмизация и программирование, язык Python, 10 класс
2
Что такое рекурсия?
У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
…
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

3. Что такое рекурсия?

Алгоритмизация и программирование, язык Python, 10 класс
3
Что такое рекурсия?
Рекурсия — это способ определения множества
объектов через само это множество на основе
заданных простых базовых случаев.
Рекурсивная функция — это функция, которая
вызывает сама себя напрямую или через другие
функции.
Числа Фибоначчи:
• F1 F2 1
• Fn Fn 1 Fn 2 при n 2
1, 1, 2, 3, 5, 8, 13, 21, 34, …
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

4. Фракталы

Алгоритмизация и программирование, язык Python, 10 класс
4
Фракталы
Фракталы – геометрические фигуры, обладающие
самоподобием.
Треугольник Серпинского:
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

5. Вывод двоичного кода числа

Алгоритмизация и программирование, язык Python, 10 класс
5
Вывод двоичного кода числа
условие выхода из
рекурсии
def printBin ( n ):
if n == 0: return
printBin ( n // 2 )
print ( n % 2, end = "" )
напечатать все
цифры, кроме
последней
вывести
последнюю цифру
printBin(
01))
printBin(
printBin(
24))
printBin(
printBin(
))
printBin(919
? Как без рекурсии?
10011
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

6. Алгоритм Евклида

Алгоритмизация и программирование, язык Python, 10 класс
6
Алгоритм Евклида
Алгоритм Евклида. Чтобы найти НОД двух натуральных
чисел, нужно вычитать из большего числа меньшее до
тех пор, пока меньшее не станет равно нулю. Тогда
второе число и есть НОД исходных чисел.
def NOD ( a, b ):
if a == 0 or b == 0:
условие окончания
рекурсии
return a + b;
if a > b:
return NOD( a - b, b )
else:
return NOD( a, b – a )
рекурсивные вызовы
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

7. Как работает рекурсия?

Алгоритмизация и программирование, язык Python, 10 класс
7
Как работает рекурсия?
Факториал:
1, N 1
N !
N ( N 1)!, N 1
def Fact(N):
print ( "->", N )
if N <= 1: F = 1
else:
F = N * Fact ( N – 1 )
print ( "<-", N )
return F
-> N = 3
-> N = 2
-> N = 1
<- N = 1
<- N = 2
<- N = 3
? Как сохранить состояние функции перед
рекурсивным вызовом?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

8. Стек

Алгоритмизация и программирование, язык Python, 10 класс
8
Стек
Стек – область памяти, в которой хранятся локальные
переменные и адреса возврата.
SP
значение
параметра
адрес
возврата
SP
Fact(3)
3
A
локальная
переменная
F
SP
Fact(2)
3
A
F
2
AF
F
SP
Fact(1)
3
A
К.Ю. Поляков, Е.А. Ерёмин, 2014
F
2
AF
F
1
AF
F
http://kpolyakov.spb.ru

9. Кеширование значений

Алгоритмизация и программирование, язык Python, 10 класс
9
Кеширование значений
Модуль functools, декоратор @functools.lru_cache.
подробнее
LRU (least recently used) — это алгоритм, при котором
вытесняются значения, которые дольше всего не
запрашивались.
@functools.lru_cache(maxsize=128, typed=False)
import functools
@functools.lru_cache(maxsize=None)
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

10. Рекурсия – «за» и «против»

Алгоритмизация и программирование, язык Python, 10 класс
10
Рекурсия – «за» и «против»
• с каждым новым вызовом расходуется память в стеке
(возможно переполнение стека)
• затраты на выполнение служебных операций при
рекурсивном вызове
программа становится более короткой и понятной
возможно переполнение стека
замедление работы
! Любой рекурсивный алгоритм можно заменить
нерекурсивным!
def Fact ( n ):
f=1
for i in range(2,n+1):
итерационный
f *= i
алгоритм
return f
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru