Презентация "Рекурсия" 11 класс

Тема: Рекурсия Цель: дать учащимся представление о рекурсии и возможностях ее использования. ПЛАН 1. Проверка домашнего задания. 2. Изучение нового материала. 3. Итог урока. Домашнее задание. I. Проверка домашнего задания.

• Как описывается функция?
• Каковы отличия функции от процедуры?
• Чем отличаются друг от друга формальные и фактические параметры?
• Что такое область действия переменной?
• Чем отличаются друг от друга глобальные и локальные па­раметры?

П. Изучение нового материала. Подпрограммы в Turbo Pascal и могут обращаться к самим себе. Такое обращение называется рекурсией. Объект, который частично определяется через самого себя, называется - рекурсивным. Рекурсивные определения как мощный аналитический аппарат используются во многих областях науки, особенно в математике. Для того, чтобы не было бесконечного обращения подпрограммы к самой себе, требуется наличие некоторого условия (ус­ловного оператора) в тексте программы, по достижении которого дальнейшее обращение не происходит. Таким образом, рекурсив­ное программирование может включаться только в одну из ветвей условного оператора, присутствующего в подпрограмме. Некоторые задачи являются рекурсивными по своему опреде­лению, поэтому рекурсивные алгоритмы - это точные копии с соответствующего определения. Пример 1. Пример 1. Нахождение НОД (наибольшего общего делителя) двух натуральных чисел. Решение. Есть несколько способов нахождения этого значения. Одним из них является алгоритм Евклида. Рассмотрим еще один из вариантов его реализации. Пусть есть два целых числа а и Ь. Если а=Ь, то НОД(а,Ь)=а. Если а>Ь, то НОД(а,Ь)=НОД(а-Ь,Ь). Если а<Ь, то НОД(а,Ь)=НОД(а,Ь-а). Рассмотрим на примере. Найдем наибольший общий делитель чисел 22 и 16.

• Рассмотрим на примере. Найдем наибольший общий делитель чисел 22 и 16.

А	B	Примечание
22	16	так как а>в, то а = а-в
6	16	так как в>а, то в = в-а
6	10	в = в-а
6	4	так как а>в, то а =а-в
2	4	в=в-а
2	2	Так как а = в,то НОД=а

Таким образом, можно составить следующую функцию и программу: Таким образом, можно составить следующую функцию и программу: uses crt; var a,b:longint; function nod (a,b:longint):longint; begin if a=b then nod: =a else if a>b then nod:=nod(a - b, b) else nod:=nod(a, b- a) end; begin clrscr; writeln('a-b=') ;readln(a, b); a:=nod(a,b); writeln('nod= ‘,a); readkey; end. Пример 2. Пример 2. Перевод натурального числа из десятичной системы счисления в двоичную. Для решения этой задачи рассмотрим сначала, как перевести число из десятичной системы счисления в двоичную. Пусть есть число 39, которое и надо представить в двоичной системе. Для этого разделим его на 2, получим целую часть и остаток от деления. Целую часть снова делим на 2 и получаем целую часть и остаток. Так делаем до тех пор, пока целую часть можно делить на 2 (то есть пока она не станет равной 1). Теперь, начиная с этой единицы, выписываем в обратном порядке все остатки от деления, это и будет запись числа 39 в двоич­ной системе счисления: 3910=1001112. Теперь, начиная с этой единицы, выписываем в обратном порядке все остатки от деления, это и будет запись числа 39 в двоич­ной системе счисления: 3910=1001112. Таким образом можно переводить любое натуральное число из десятичной системы счисления в двоичную, а также и другие сис­темы (например, восьмеричную или шестеричную).   uses crt; var n:longint; procedure REC (n:longint;); begin if n>l then rec(n div 2); writefn (mod 2); end; begin clrscr; writeln('n - '); readln(n); rec(n); readln; end. Результат на экране: 100111. Результат на экране: 100111. Первая цифра (1) выводится на экран из последнего вызова, следующая цифра (0) - из предпоследнего и так далее, последняя (1) - из первого. Таким образом, вывод очередной цифры происходит перед тем, как выйти из данной функции. Домашнее задание:

• Повторить понятие процедур и функций.
• Выучить конспект.
• Написать программу нахождения факториала числа при помощи рекурсивной функции.