Конструктор уроків
Цілі:
навчальна: рекурсивні функції
розвивальна: розвивати логічне мислення; формувати вміння діяти за інструкцією, планувати свою діяльність, аналізувати i робити висновки;
виховна: виховувати інформаційну культуру учнів, уважність, акуратність, дисциплінованість.
2
3
4
5
Проблеми використання рекурсивних функцій
Задача. Обчислити n-ий елемент послідовності Фібоначчі
Математичний запис | програмний код |
| def F(n): ____if n==0 or n==1: ___________return 1; _______else: ________return f(n-1) + f(n-2) |
Під час обчислення значення F(6) будуть викликані функції обчислення F(4) та F(5). У свою чергу, для обчислення F(4) будуть викликані F(2) та F(3), а для Fib(5) – пара F(3) та F(4). Можна намалювати «дерево рекурсивних викликів»:
Як видно з малюнка, що, наприклад, F(3) обчислюється три рази.
Якщо розглянути обчислення при великих N, то повторних обчислень буде дуже багато. Це і є основний недолік рекурсії - повторні обчислення тих самих значень. Крім того, з рекурсивними функціями пов'язана одна серйозна проблема: дерево рекурсивних викликів може виявитися нескінченним і комп'ютер «зависне».
Способи вирішення проблеми "повторних обчислень" та "нескінченності дерева викликів":
перетворити рекурсивну функцію на циклічний алгоритм;
застосувати метод динамічного програмування (масиви + циклічний алгоритм)
застосувати рекурсію із запам'ятовуванням (рекурсивна функція+масив)
6
Рекурсія із запам'ятовуванням
Рекурсивна функція | Рекурсивна функція з запам'ятовуванням |
|
|
mem - це список (з n+1 елемента), який зберігає проміжні результати; остаточний результат знаходиться в комірці масиву mem[n] |
Hекурсія із запам'ятовуванням складється з "обгортки" та "рекурсивної функції+масив":
Послідовність Фібоначчі | Сума цифр числа |
|
|
|
|
7
Головна програма для рекурсії з запам'ятовуванням
8
Задача "Фібоначчі"
Ознайомитись з умовою задачі на сайті EOlymp
Написати програму використовуючи "чисту" рекурсивну функцію, виконати тестування та надіслати результати тестування.
Написати програму використовуючи рекурсію із запам'ятовуванням, виконати тестування та надіслати результати тестування.
.png)
9
Пояснити, чому, на Вашу думку, результати тестування відрізняються для наведених вище двох підходів до розв'язання задачі?
10
Рефлексія від 10 учнів
Сподобався:
Так: 9
Ні: 1
Зрозумілий:
Так: 9
Ні: 1
Потрібні роз'яснення:
Ні: 9
Так: 1
