Рекурсия

1.

Рекурсия

2.

Последовательное конструирование алгоритма
Подзадача 1
Подзадача 2.1
Задача
Подзадача 2
Подзадача 2.2
Подзадача 3

3.

Последовательное конструирование алгоритма
Подзадача 1
Вспомогательный
алгоритм 1
Подзадача 2.1
Вспомогательный
алгоритм 2.1
Задача
Подзадача 2.2
Вспомогательный
алгоритм 2.2
Подзадача 3
Вспомогательный
алгоритм 3
Алгоритм
решения задачи

4.

При программировании
вспомогательные алгоритмы
оформляются в виде
подпрограмм.
Функции –
это подпрограммы, которые могут
вызываться в различных местах
программы и обрабатывать различные
данные одним и тем же способом.

5.

Вопросы к изучению
1
2
3
Определение
рекурсии.
Рекурсивные
алгоритмы.
Программирование
рекурсивных
алгоритмов.

6.

Рекурсия —
это способ определения множества
объектов через это же множество на
основе заданных базовых случаев.
Числа Фибоначчи —
это числовой ряд, в котором
первые два числа равны единице,
а все последующие являются
суммой двух предыдущих.
Базовые
случаи
Индуктивная
часть

7.

Рекурсия в культуре
«Чтобы понять, что такое
рекурсия, нужно сначала
понять, что такое рекурсия».
Народная шутка
GNU:
GNU’s Not Unix

8.

Рекурсия в культуре

9.

Рекурсия в культуре

10.

Кривые Коха
Дерево-фрактал
Треугольники Серпинского

11.

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

12.

Принцип работы функции
factorial (3) = 6
def factorial (n):
if n == 1:
return 1
else:
return factorial (n - 1) * n
factorial (2) = 2
def factorial (n):
if n == 1:
return 1
else:
return factorial (n - 1) * n
factorial (1) = 1
def factorial (n):
if n == 1:
return 1
else:
return factorial (n - 1) * n

13.

Задача
Используя рекурсию, найти цифровой корень заданного натурального числа N.
Обозначим:
f (n) – цифровой корень n;
g (n) – сумму цифр n.

14.

Стек —
особая область памяти для хранения
значений локальных параметров и
адресов возврата функций.

15.

Стек —
особая область памяти для хранения
значений локальных параметров и
адресов возврата функций.
…
…
Указатель стека
…
…
ЛП АВ ЛП АВ
1. factorial (4)
2. factorial (3)

16.

Стек —
особая область памяти для хранения
значений локальных параметров и
адресов возврата функций.
…
…
Указатель стека
…
…
ЛП АВ ЛП АВ ЛП АВ
При вызове функции
происходит расход не только
оперативной, но и стековой
памяти компьютера.
1. factorial (4)
2. factorial (3)
3. factorial (2)
4. factorial (1)

17.

Правило:
если задачу можно достаточно
просто решить без использования
рекурсии — лучше так и поступить.

18.

Рекурсия
Рекурсия —
Рекурсивные алгоритмы —
это способ определения множества
объектов через это же множество на
основе заданных базовых случаев.
это вспомогательные алгоритмы,
которые напрямую или через
другие вспомогательные алгоритмы
вызывают сами себя.
Правило:
если задачу можно достаточно
просто решить без использования
рекурсии — лучше так и поступить.