Презентация по математике "Рекурсивная функция"

Слайд #1

Рекурсивная функция
Выполнила ученица 11Г класса
Марисова Екатерина

Индивидуальный проект по теме

Слайд #2

Введение
На уроках информатики и математики в школе мы нередко использовали функции. Особенно меня заинтересовала рекурсивная функция.

Актуальностью работы является то, что применение рекурсивных функций позволяет найти более простой способ решения задач, делает решение более понятным и занимает меньше времени, без потери эффективности.

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

Значимость проекта велика. Данную работу можно использовать на уроках математики и информатики в школе, при подготовке к ЕГЭ, для обучения решения задач с помощью рекурсивных функций

Слайд #3

Цель
исследовать методы решения задач с помощью рекурсивных функций

Задачи
Ознакомится с основными способами решения задач с помощью рекурсивной функции, тем самым изучить понятие рекурсивной функции

Объект исследования
рекурсивная функция

Предмет исследования
решение задач с помощью рекурсивной функции

Слайд #4

Гипотеза
Можно предположить, что рекурсивная функция является эффективной при решении задач.

Методы исследования
Работа с литературой, программирование рекурсивных функций на Python, исследование способов решения задач.

Новизна работы
рекурсивные функции позволяют уменьшить время решения задач и сделать решение понятным.

Практическая значимость
данную работу можно использовать на уроках математики и информатики в школе, при подготовке к ЕГЭ, для обучения решения задач с помощью рекурсивных функций.

Слайд #5

Глава I Из истории вопроса
Рекурсия - фундаментальное понятие в математике и компьютерных науках. В языках программирования рекурсивной функцией называется программа, которая обращается сама к себе.

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

Одним из примеров рекурсивной функции могут служить числа Фибоначчи — элементы числовой последовательности
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 …
в которой каждое последующее число равно сумме двух предыдущих чисел.

Слайд #6

Глава I Из истории вопроса
Применение рекурсивной функции разнообразно
В природе (капуста Романеско)
В архитектуре 
В искусстве
Герб России

Слайд #7

Глава II Рекурсивное задание функций
Основной задачей исследования рекурсивно заданных функций является получение f(n) в явной или как еще говорят «замкнутой» форме, т.е. в виде аналитически заданной функции. В связи с этим рассмотрим ряд примеров:

f(0) = 0
f(n) = f(n – 1) + 1
Это прямая рекурсия. То есть функция A вызывает функцию A с другими аргументами. Еще данную рекурсию можно назвать линейной, так как экземпляр функции вызывает себя только один раз.

Слайд #8

Другие прямые рекурсии
Данная рекурсия вычисляет факториал числа n




Эта рекурсивная функция определяет числа Фибоначчи: 1 1 2 3 5 8 13 ... Расчет чисел Фибоначчи также является каскадной рекурсией, потому что функция вызывает себя дважды: для n-1 и n-2.
f(0) = 1
f(n) = n*f(n – 1)
f(0) = 1
f(n) = f(n – 1) + f(n – 2)
f(1) = 1

Слайд #9

Косвенная рекурсия
Еще одним видом рекурсии является косвенная рекурсия, которая действует через «третью» функцию. Функция A вызывает функцию B, а та в свою очередь снова вызывает функцию A.

Пример


f(n) = g(n) = n, n <= 2
g(n) = f(n – 1) – g(n – 2), n > 2
f(n) = g(n) + f(n – 2), n > 2

Слайд #10

Виды рекурсий



Прямая
Косвенная
Каскадная
Линейная

Слайд #11

Решение рекурсивных задач с помощью дерева вариантов
Еще одним вариантом вычисления рекурсивных функций являются бинарные деревья.
f(5)
f(4)
f(3)
f(2)
f(3)
f(1)
f(2)
1
f(0)
f(1)

Слайд #12

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






Для решения данной задачи можно написать программу на Python


f(n) = 3, n = 1
f(21) - ?
f(n) = 2 * f(n – 1) – n + 1, n > 1
Ответ: 1048598

Слайд #13

Рекурсивный и итеративный процессы


Одну и ту же рекурсию можно использовать по-разному. Например, есть понятия рекурсивного и итеративного процесса.

В рекурсивном процессе все расчеты откладываются «на потом», как в примере с числами Фибоначчи. Конечный расчет делает тот экземпляр функции, который вызвали в последнюю очередь, а потом результаты по каскаду передаются предыдущим.

В итеративном процессе наоборот. Функция считает всё, что может посчитать, и только потом вызывает свой новый экземпляр и передает наработки ему.
Итеративный процесс
Рекурсивный процесс

Слайд #14

В чем заключаются преимущества и недостатки рекурсии?
+
Ясность

Наглядность

Краткость

Красота

-
Риск переполнения
(в программном решении!)
Можно избавить процесс от заполнения стека «ненужными» значениями предыдущих вызовов и обеспечить прямой возврат из функции при достижении условия. На языке Python можно использовать вспомогательные библиотеки. Например, functools, sys и тд.

Слайд #15

Заключение
При изучении теоретического материала мы выявили, что рекурсия — это поведение функции, при котором она вызывает сама себя. Обычно рекурсию применяют при расчетах, которые подразумевают использование результата одного шага для подсчитывания другого. С рекурсией мы часто встречаемся в повседневной жизни.

В ходе исследования рекурсивных функций, мы выявили, что она бывает разных видов: прямая – косвенная, каскадная – линейная.
Узнали, какие преимущества и недостатки есть у использования рекурсии:
Преимущества – ясность, наглядность, краткость, красота. 
Недостатки – риск переполнения (существует исключительно с программным решением задач на рекурсию)

Таким образом, гипотеза действительно подтвердилась. Рекурсивная функция действительно является эффективной при решении задач, она позволяет сделать решение наглядным.

Слайд #16

Спасибо за внимание!