- •Рекурсия
- •Определения
- •Рекурсия
- •Итерация и рекурсия
- •СПОСОБЫ ПРЕДСТАВЛЕНИЯ ДРЕВОВИДНЫХ СТРУКТУР
- •Рекурсия типов данных:
- •Рекурсия функций
- •Рекурсивные определения, примеры:
- •Рекурсивные определения, примеры:
- •Достоинство
- •Рекурсия в программировании
- •Рекурсивные функции
- •Рекурсия
- •Общий вид рекурсии:
- •Свойства рекурсивных
- •Задача о вычислении Факториала
- •Однако мы можем выразить факториал рекурсивно, через другие факториалы:
- •Факториал числа
- •Факториал числа: итеративное определение
- •Рекурсивное решение
- •Рекурсивное решение: факториал числа 5
- •Пример 2. Определим функцию K(n), которая возвращает количество цифр в заданном натуральном числе
- •Свойства рекурсивного решения
- •Ошибка в использовании рекурсии
- •Четыре вопроса о рекурсивном решении:
- •Числа Фибоначчи
- •Цена рекурсии
- •Ханойские башни:
- •Ханойские башни:
- •для того чтобы перенести самый большой диск, нужно сначала перенести все диски кроме
- •Функция на с
- •Рекурсивный алгоритм Евклида (НОД)
Рекурсия
Один из самых мощных методов решения задач
Определения
Рекурсивным называется объект, частично содержащий себя, или определенный с помощью самого себя.
Рекурсия
Итерация и рекурсия
Введение понятия «функция» необходимо и
достаточно для разработки рекурсивных
алгоритмов.
Примеры рекурсивного определения:
1.Матрёшка – это кукла, внутри которой находится матрёшка.
2.Если внутри куклы может находится больше одной матрешки, то такой объект структурно эквивалентен
Древовидныедереву. структуры могут быть представлены различными способами –
•в виде диаграмм
a |
|
или |
a |
c |
d |
b |
c |
|
|||
e |
|
b |
e |
||
d |
|
|
|
||
|
|
|
|
СПОСОБЫ ПРЕДСТАВЛЕНИЯ ДРЕВОВИДНЫХ СТРУКТУР
A
B
D
I
E
J
K
L
C
F
O
G
M
N
H
P
MN J G
ID BLEK OF C PH
(A(B(D(I),E(J,K,L)),C(F,(O),G(M,N),H(P))))
5
Рекурсия типов данных:
Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов. Пример описания списка :
struct element_of_list
{
element_of_list *next;
/* ссылка на следующий элемент того же типа*/ int data; // некие данные //
};
Рекурсия функций
Рекурсия функции— это вызов функции из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Рекурсивные определения, примеры:
Натуральные числа:
0 – натуральное число
Если N – натуральное число, то число N+1 также натуральное
Рекурсивные определения, примеры:
Факториал числа:
0!=1
N!=(N-1)!*N, для любого N>0;
Достоинство
Рекурсивное определение
позволяет определить бесконечное множество объектов с помощью конечного высказывания