Рекурсивные функции. Лекция №9

1.

Лекция № 9
Рекурсивные
Функции

2.

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

3.

Рекурсия в быту
Камера снимает экран монитора, в котором
камера снимает экран монитора, в котором …

4.

Определение рекурсии
Рекурсия — процесс повторения элементов
самоподобным образом.

5.

Рекурсивная функция
Функция, которая вызывает сама себя.
! Проверка допустимого числа повторений !

6.

Рекурсивная функция
Печать целых чисел в обратном порядке

7.

Печать чисел (разбор)
10 ≠ 0

8.

Печать чисел (разбор)
10 ≠ 0
9≠0

9.

Печать чисел (разбор)
10 ≠ 0
9≠0
8≠0

10.

Печать чисел (разбор)
10 ≠ 0
9≠0
8≠0
…2≠0

11.

Печать чисел (разбор)
10 ≠ 0
9≠0
8≠0
…2≠0
1≠0

12.

Печать чисел (разбор)
10 ≠ 0
9≠0
8≠0
…2≠0
1≠0
0=0
stop !

13.

Печать чисел (разбор)
10 ≠ 0
9≠0
8≠0
…2≠0
1≠0
0=0
stop !

14.

Печать чисел (разбор)
10 ≠ 0
9≠0
8≠0
…2≠0
1≠0

15.

Печать чисел (разбор)
10 ≠ 0
9≠0
8≠0
…2≠0

16.

Печать чисел (разбор)
10 ≠ 0
9≠0
8≠0

17.

Печать чисел (разбор)
10 ≠ 0
9≠0

18.

Вызовы в стеке
1-я копия (10)

19.

Вызовы в стеке
2-я копия (9)
1-я копия (10)

20.

Вызовы в стеке
3-я копия (8)
2-я копия (9)
1-я копия (10)

21.

Вызовы в стеке
4-я копия (7)
3-я копия (8)
2-я копия (9)
1-я копия (10)

22.

Вызовы в стеке
5-я копия (6)
4-я копия (7)
3-я копия (8)
2-я копия (9)
1-я копия (10)

23.

Вызовы в стеке
6-я копия (5)
5-я копия (6)
4-я копия (7)
3-я копия (8)
2-я копия (9)
1-я копия (10)

24.

Вызовы в стеке
7-я копия (4)
6-я копия (5)
5-я копия (6)
4-я копия (7)
3-я копия (8)
2-я копия (9)
1-я копия (10)

25.

Вызовы в стеке
8-я копия (3)
7-я копия (4)
6-я копия (5)
5-я копия (6)
4-я копия (7)
3-я копия (8)
2-я копия (9)
1-я копия (10)

26.

Вызовы в стеке
9-я копия (2)
8-я копия (3)
7-я копия (4)
6-я копия (5)
5-я копия (6)
4-я копия (7)
3-я копия (8)
2-я копия (9)
1-я копия (10)

27.

Вызовы в стеке
10-я копия (1)
9-я копия (2)
8-я копия (3)
7-я копия (4)
6-я копия (5)
5-я копия (6)
4-я копия (7)
3-я копия (8)
2-я копия (9)
1-я копия (10)

28.

Вызовы в стеке
11-я копия (0)
10-я копия (1)
9-я копия (2)
8-я копия (3)
7-я копия (4)
6-я копия (5)
5-я копия (6)
4-я копия (7)
3-я копия (8)
2-я копия (9)
1-я копия (10)

29.

Рекурсивная функция
Вычисление факториала

30.

Вычисление факториала (разбор)
k=5

31.

Вычисление факториала (разбор)
k=5
k=4
5*

32.

Вычисление факториала (разбор)
k=5
k=4
k=3
5* 4*

33.

Вычисление факториала (разбор)
k=5
k=4
k=3
k=2
5* 4* 3*

34.

Вычисление факториала (разбор)
k=5
k=4
k=3
k=2
k=1
5* 4* 3* 2*
1

35.

Вычисление факториала (разбор)
k=5
k=4
k=3
k=2
5* 4* 3* 2

36.

Вычисление факториала (разбор)
k=5
k=4
k=3
5* 4* 6

37.

Вычисление факториала (разбор)
k=5
5 * 24

38.

Вычисление факториала (разбор)
k=5
120

39.

Треугольник Серпинского
(x2,y2)
(xc1,yc1)
(x1,y1)
(xc2,yc2)
(xc3,yc3)
(x3,y3)

40.

Треугольник Серпинского
Координаты середин сторон треугольника
x1 x 2
y1 y 2
xc1
, yc1
2
2
x 2 x3
y 2 y3
xc2
, yc 2
2
2
x1 x3
y1 y3
xc3
, yc3
2
2

41.

Треугольник Серпинского
Словесный алгоритм :-)
Я – отец треугольник . Нарисую себя.
Рассчитаю середины своих сторон .
Скажу каждому своему сыну
(маленькому треугольнику) –
сделай то, что я сделал.

42.

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

43.

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

44.

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