Рекурсия в Python

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

Рекурсия

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

У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал:

У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал:

…

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

Натуральные числа :

индуктивное определение

• 1 – натуральное число
• если – натуральное число, то – натуральное число

Рекурсия — это способ определения множества объектов через само это множество на основе заданных простых базовых случаев.

Числа Фибоначчи :

при

1, 1, 2, 3, 5, 8, 13, 21, 34, …

3

Фракталы

Фракталы – геометрические фигуры, обладающие самоподобием.

Треугольник Серпинского:

3 перенести (n- 1 , 2 , 3 )" width="640"

3

Ханойские башни

3

2

1

• за один раз переносится один диск
• класть только меньший диск на больший
• третий стержень вспомогательный

перенести (n, 1 , 3 )

перенести (n- 1 , 1 , 2 )

1 - 3

перенести (n- 1 , 2 , 3 )

" , m ) Hanoi ( n- 1 , p, m ) рекурсия рекурсия ? Что плохо? ! Рекурсия никогда не остановится!" width="640"

5

Ханойские башни – процедура

куда

откуда

сколько

номер вспомогательного стержня (1+2+3=6!)

def Hanoi ( n, k, m ):

p = 6 - k - m

Hanoi ( n- 1 , k, p )

print ( k, "-" , m )

Hanoi ( n- 1 , p, m )

рекурсия

рекурсия

?

Что плохо?

!

Рекурсия никогда не остановится!

" , m ) Hanoi ( n- 1 , p, m ) условие выхода из рекурсии if n == 0 : return # основная программа Hanoi ( 4 , 1 , 3 )" width="640"

6

Ханойские башни – процедура

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

def Hanoi ( n, k, m ):

p = 6 - k - m

Hanoi ( n- 1 , k, p )

print ( k, "-" , m )

Hanoi ( n- 1 , p, m )

условие выхода из рекурсии

if n == 0 : return

# основная программа

Hanoi ( 4 , 1 , 3 )

6

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

условие выхода из рекурсии

def printBin ( n ):

if n == 0 : return

printBin ( n // 2 )

print ( n % 2 , end = "" )

напечатать все цифры, кроме последней

вывести последнюю цифру

printBin ( 0 )

printBin ( 1 )

printBin ( 2 )

?

printBin ( 4 )

Как без рекурсии?

printBin ( 9 )

printBin ( 19 )

10011

= 10 : sum += sumDig ( n // 10 ) return sum последняя цифра рекурсивный вызов ? Где условие окончания рекурсии? sumDig ( 1234 ) 4 + sumDig ( 123 ) 4 + 3 + sumDig ( 12 ) 4 + 3 + 2 + sumDig ( 1 ) 4 + 3 + 2 + 1" width="640"

8

Вычисление суммы цифр числа

def sumDig ( n ):

sum = n % 10

if n = 10 :

sum += sumDig ( n // 10 )

return sum

последняя цифра

рекурсивный вызов

?

Где условие окончания рекурсии?

sumDig ( 1234 )

4 + sumDig ( 123 )

4 + 3 + sumDig ( 12 )

4 + 3 + 2 + sumDig ( 1 )

4 + 3 + 2 + 1

b: return NOD( a - b, b ) else : return NOD( a, b – a ) условие окончания рекурсии return a + b; рекурсивные вызовы" width="640"

9

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

Алгоритм Евклида . Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел.

def NOD ( a, b ):

if a == 0 or b == 0 :

if a b:

return NOD( a - b, b )

else :

return NOD( a, b – a )

условие окончания рекурсии

return a + b;

рекурсивные вызовы

9

Задачи

«A»: Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел, используя модифицированный алгоритм Евклида.

Пример :

Введите два натуральных числа:

7006652 112307574

НОД(7006652,112307574)=1234.

«B»: Напишите рекурсивную функцию, которая раскладывает число на простые сомножители.

Пример :

Введите натуральное число:

378

378 = 2*3*3*3*7

9

Задачи

«C»: Дано натуральное число N. Требуется получить и вывести на экран количество всех возможных различных способов представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа 3). Решите задачу с помощью рекурсивной процедуры.

Пример :

Введите натуральное число:

4

Количество разложений: 4.

N = 3 - N = 2 - N = 1 = 1 = 2 = 3 def Fact(N): print ( "-" , N ) if N 1 : F = 1 else : F = N * Fact ( N – 1 ) print ( " , N ) return F ? Как сохранить состояние функции перед рекурсивным вызовом?" width="640"

9

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

Факториал:

- N = 3

- N = 2

- N = 1

= 1

= 2

= 3

def Fact(N):

print ( "-" , N )

if N 1 : F = 1

else :

F = N * Fact ( N – 1 )

print ( " , N )

return F

?

Как сохранить состояние функции перед рекурсивным вызовом?

13

Стек

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

SP

адрес возврата

значение параметра

локальная переменная

SP

Fact(3)

3

A

F

SP

Fact(2)

3

A

F

2

A F

F

SP

Fact(1)

3

A

F

2

A F

F

1

A F

F

14

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

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

• программа становится более короткой и понятной

• возможно переполнение стека
• замедление работы

!

Любой рекурсивный алгоритм можно заменить нерекурсивным!

def Fact ( n ):

f = 1

for i in range ( 2 ,n+ 1 ):

f *= i

return f

итерационный алгоритм