Программирование на языке С++. Рекурсия. Ханойские башни

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

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

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

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

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

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

4. Фракталы

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

5. Рекурсия в программировании

Алгоритмизация и программирование, Паскаль, 10 класс
5
Рекурсия в программировании
Рекурсивная процедура (функция) — это процедура
(функция), которая вызывает сама себя напрямую или
через другие процедуры и функции.
Факториал:
1, N 1
N!
N ( N 1)!, N 1
int fact(int n)
{
if (n <= 1)
return 1;
else
return n * fact(n-1);
}
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
6
Ханойские башни
1
2
3
• за один раз переносится один диск
• можно класть только меньший диск на больший
• третий стержень вспомогательный
перенести (n, 1, 2, 3)
перенести (n-1, 1, 3, 2)
1 -> 2
перенести (n-1, 3, 2, 1)
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
7
Ханойские башни
сколько
откуда
куда
void hanoi(int n, int k, int m, int p)
{
рекурсия
hanoi(n-1, k, p, m);
cout << k << ' -> ’ << m);
hanoi(n-1, p, m, k);
рекурсия
}
номер
вспомогательного
стержня
?
!
Чего не хватает?
Рекурсия никогда не остановится!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
8
Ханойские башни
void hanoi(int n, int k, int m, int p)
{
условие выхода из
if (n == 0) return;
рекурсии
hanoi(n-1, k, p, m);
cout << k << ' -> ’ << m);
hanoi(n-1, p, m, k);
}
int main()
{
hanoi(4, 1, 2, 3);
}
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru