243282
столько раз учителя, ученики и родители
посетили сайт «Инфоурок»
за прошедшие 24 часа
+Добавить материал
и получить бесплатное
свидетельство о публикации
в СМИ №ФС77-60625 от 20.01.2015
Дистанционные курсы профессиональной переподготовки и повышения квалификации для педагогов

Дистанционные курсы для педагогов - курсы профессиональной переподготовки от 6.900 руб.;
- курсы повышения квалификации от 1.500 руб.
Престижные документы для аттестации

ВЫБРАТЬ КУРС СО СКИДКОЙ 50%

ВНИМАНИЕ: Скидка действует ТОЛЬКО сейчас!

(Лицензия на осуществление образовательной деятельности № 5201 выдана ООО "Инфоурок")

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

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

библиотека
материалов
Реку́рсия — в определении, описании, изображении какого-либо объекта или проц...
В математике рекурсия 	имеет отношение к методу определения функций и числовы...
В математике рекурсия Бесконечная рекурсивная функция. Примером может служить...
Ханойская башня
Ханойская башня //n – количество дисков //a, b, c – номера штырьков. Переклад...
В программировании рекурсия — 	вызов функции (процедуры) из неё же самой, неп...
Структурно рекурсивная функция на верхнем уровне всегда представляет собой к...
Пример рекурсивной процедуры: procedure Rec(a: integer); begin   if a>0 then...
Если в основной программе поставить вызов, например, вида Rec(3). Ниже предст...
Процедура Rec вызывается с параметром a = 3. В ней содержится вызов процедуры...
В качестве самостоятельного упражнения подумайте, что получится при вызове Re...
Перевод числа в двоичную систему. while x>0 do begin   c:=x mod 2;   x:=x div...

Описание презентации по отдельным слайдам:

1 слайд Реку́рсия — в определении, описании, изображении какого-либо объекта или проц
Описание слайда:

Реку́рсия — в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике.

2 слайд В математике рекурсия 	имеет отношение к методу определения функций и числовы
Описание слайда:

В математике рекурсия имеет отношение к методу определения функций и числовых рядов: рекурсивно заданная функция определяет своё значение через обращение к себе самой с другими аргументами. Конечная рекурсивная функция. Здесь каждое следующее рекурсивное обращение делается с аргументом, меньшим на единицу. Поскольку n, по определению, целое неотрицательное число, через n рекурсивных обращений вычисление функции гарантированно придёт к частному случаю , на котором рекурсия прекратится. 

3 слайд В математике рекурсия Бесконечная рекурсивная функция. Примером может служить
Описание слайда:

В математике рекурсия Бесконечная рекурсивная функция. Примером может служить один из вариантов разложения числа Эйлера: Подобным образом могут задаваться бесконечные ряды, бесконечные  непрерывные дроби и так далее.

4 слайд
Описание слайда:

5 слайд Ханойская башня
Описание слайда:

Ханойская башня

6 слайд Ханойская башня //n – количество дисков //a, b, c – номера штырьков. Переклад
Описание слайда:

Ханойская башня //n – количество дисков //a, b, c – номера штырьков. Перекладывание производится со штырька a, //на штырек b при вспомогательном штырьке c. procedure Hanoi(n, a, b, c: integer); begin   if n > 1 then   begin     Hanoi(n-1, a, c, b);     writeln(a, ' -> ', b);     Hanoi(n-1, c, b, a);   end else     writeln(a, ' -> ', b);   end;

7 слайд В программировании рекурсия — 	вызов функции (процедуры) из неё же самой, неп
Описание слайда:

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция А вызывает функцию В, а функция А — функцию В . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Рекурсивная программа позволяет описать повторяющееся или даже потенциально бесконечное вычисление, причём без явных повторений частей программы и использования циклов.

8 слайд Структурно рекурсивная функция на верхнем уровне всегда представляет собой к
Описание слайда:

Структурно рекурсивная функция на верхнем уровне всегда представляет собой команду ветвления (выбор одной из двух или более альтернатив в зависимости от условия (условий), которое в данном случае уместно назвать «условием прекращения рекурсии»), имеющей две или более альтернативные ветви, из которых хотя бы одна является рекурсивной и хотя бы одна — терминальной. Рекурсивная ветвь выполняется, когда условие прекращения рекурсии ложно, и содержит хотя бы один рекурсивный вызов — прямой или опосредованный вызов функцией самой себя. 

9 слайд Пример рекурсивной процедуры: procedure Rec(a: integer); begin   if a>0 then
Описание слайда:

Пример рекурсивной процедуры: procedure Rec(a: integer); begin   if a>0 then     Rec(a-1);   writeln(a); end;

10 слайд Если в основной программе поставить вызов, например, вида Rec(3). Ниже предст
Описание слайда:

Если в основной программе поставить вызов, например, вида Rec(3). Ниже представлена блок-схема, показывающая последовательность выполнения операторов.

11 слайд Процедура Rec вызывается с параметром a = 3. В ней содержится вызов процедуры
Описание слайда:

Процедура Rec вызывается с параметром a = 3. В ней содержится вызов процедуры Rec с параметром a = 2. Предыдущий вызов еще не завершился, поэтому можете представить себе, что создается еще одна процедура и до окончания ее работы первая свою работу не заканчивает. Процесс вызова заканчивается, когда параметр a = 0. В этот момент одновременно выполняются 4 экземпляра процедуры. Количество одновременно выполняемых процедур называют глубиной рекурсии. Четвертая вызванная процедура (Rec(0)) напечатает число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала (Rec(1)) и печатается число 1. И так далее пока не завершатся все процедуры. Результатом исходного вызова будет печать четырех чисел: 0, 1, 2, 3.

12 слайд В качестве самостоятельного упражнения подумайте, что получится при вызове Re
Описание слайда:

В качестве самостоятельного упражнения подумайте, что получится при вызове Rec(4). Также подумайте, что получится при вызове описанной ниже процедуры Rec2(4), где операторы поменялись местами. procedure Rec2(a: integer); begin   writeln(a);   if a>0 then     Rec2(a-1); end; Обратите внимание, что в приведенных примерах рекурсивный вызов стоит внутри условного оператора. Это необходимое условие для того, чтобы рекурсия когда-нибудь закончилась. Также обратите внимание, что сама себя процедура вызывает с другим параметром, не таким, с каким была вызвана она сама. Если в процедуре не используются глобальные переменные, то это также необходимо, чтобы рекурсия не продолжалась до бесконечности.

13 слайд Перевод числа в двоичную систему. while x>0 do begin   c:=x mod 2;   x:=x div
Описание слайда:

Перевод числа в двоичную систему. while x>0 do begin   c:=x mod 2;   x:=x div 2;   write(c); end; procedure BinaryRepresentation(x: integer); var   c, x: integer; begin   {Первый блок. Выполняется в порядке вызова процедур}   c := x mod 2;   x := x div 2;   {Рекурсивный вызов}   if x>0 then     BinaryRepresentation(x);   {Второй блок. Выполняется в обратном порядке}   write(c); end;

Краткое описание документа:

Тема:  рекурсивные алгоритмы.

Что нужно знать:

·    рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа

·    чтобы определить рекурсию, нужно задать

o   условие остановки рекурсии (базовый случай или несколько базовых случаев)

o   рекуррентную формулу

·    любую рекурсивную процедуру можно запрограммировать с помощью цикла

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

    существуют языки программирования, в которых рекурсия используется как один из основных приемов обработки данных (Lisp, Haskell)

Общая информация

Номер материала: 480694

Вам будут интересны эти курсы:

Курс повышения квалификации «Табличный процессор MS Excel в профессиональной деятельности учителя математики»
Курс повышения квалификации «Методика преподавания информатики в начальных классах»
Курс повышения квалификации «Основы создания интерактивного урока: от презентации до видеоурока»
Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»
Курс повышения квалификации «Организация работы по формированию медиаграмотности и повышению уровня информационных компетенций всех участников образовательного процесса»
Курс профессиональной переподготовки «Информатика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Облачные технологии в образовании»
Курс «3D Studio MAX»
Курс профессиональной переподготовки «Информационные технологии в профессиональной деятельности: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Использование компьютерных технологий в процессе обучения в условиях реализации ФГОС»
Курс повышения квалификации «Специфика преподавания информатики в начальных классах с учетом ФГОС НОО»
Курс повышения квалификации «Применение MS Word, Excel в финансовых расчетах»
Курс профессиональной переподготовки «Теория и методика обучения информатике в начальной школе»
Курс повышения квалификации «Современные языки программирования интегрированной оболочки Microsoft Visual Studio C# NET., C++. NET, VB.NET. с использованием структурного и объектно-ориентированного методов разработки корпоративных систем»
Курс повышение квалификации «Применение интерактивных образовательных платформ на примере платформы Moodle»
Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.