Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Рекурсия.






Рекурсия – это вывоз подпрограммой

(процедурой или функцией) самой себя.

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

PROGRAM DEMO1;

USES CRT;

VAR M: BYTE;

FUNCTION FAKT(N: BYTE): LONGINT;

BEGIN

IF N=1 THEN FAKT: =1

ELSE FAKT: =FAKT(N-1)*N;

END;

BEGIN

CLRSCR;

WRITE('N-'); READLN(M);

WRITELN('N! =', FAKT(M));

READKEY;

END.

В нашем примере происходит так: в операторе печати вызывается функция FAKT с параметрам N, которая в свою очередь вызывает функцию FAKT с параметрам N-1, и так далее, пока не вызывается FAKT(1). Тогда это процесс останавливается, затем происходить извлечение результата в обратном порядке.

Это хорошо видно на следующем примере программы:

Текст программы: Результат работы программы:
PROGRAM DEMO2; USES CRT; VAR CH: WORD; PROCEDURE WRITEA; BEGIN CH: =CH+1; WRITELN('­НАЧАЛО', CH); IF CH< 4 THEN WRITEA; WRITELN(' КОНЕЦ', CH); CH: =CH-1; END; BEGIN CLRSCR; CH: =0; WRITEA; READKEY; END.   НАЧАЛО 1 НАЧАЛО 2 НАЧАЛО 3 НАЧАЛО 4 КОНЕЦ 4 КОНЕЦ 3 КОНЕЦ 2 КОНЕЦ 1  

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

Стек – это специальная область памяти (конечное число ячеек), где сохраняется адреса возврата (адрес вызывающей программы, используется для передачи управления вызывающей программе). Стеки используются так же для передачи параметров в процедуры (для обычных параметров в стек заносятся их значения, для параметров-переменных – их адреса), размер стек ограничен. Стек можно представить в виде стопки книг. Если стопка достигла максимального размера, то при добавлении новой книги сверху – нижняя книга должна быть убрана.

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

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

Пример:

PROCEDURE B(J: BYTE); FORWARD; {тело процедуры заменено директивой FORWARD }

PROCUDURE A(I: BYTE);

BEGIN

B(I);

END;

PROCEDURE B;

BEGIN

A(J);

END;


 

Примеры программ с процедурами и функциями:

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

· Найти разность двух факториалов F=m! – k!, используя функцию.

Uses crt; Var F, m, k: integer; Function Fact(n: integer): integer; Var P, i: integer; Begin P; =1; For i: =2 to n do P; =P*i; Fact: =P; End; Begin Read (M, K); F: =Fact(m) – Fact(K); Writeln (‘F=’, F: 5); repeat until keypressed End.

· Написать программу «Бегущие огни» с использованием процедуры рисования окружности.

uses crt, graph; var gd, gm, x: integer; begin gd: =detect; initgraph(gd, gm, ''); x: =20; repeat repeat setcolor(4); circle(x, 200, 15); setfillstyle(1, 3); floodfill(x, 200, 4); delay(8000); setcolor(0); circle(x, 200, 15); setfillstyle(1, 3); floodfill(x, 200, 0); x: =x+40; until x> 600; repeat setcolor(4); circle(x, 200, 15); delay(8000); setcolor(0); circle(x, 200, 15); x: =x-40; until x< 20; repeat until keypressed; end.

 

Примеры программ с использованием рекурсий:

Вычислить Xn: PROGRAM DEMO3; USES CRT; VAR X1, X2: WORD; I, M: BYTE; S: LONGINT; FUNCTION XN(X, N: BYTE): LONGINT; BEGIN IF N=0 THEN XN: =1 ELSE XN: =XN(X, N-1)*X; END; BEGIN CLRSCR; WRITE('X, N-'); READLN(X1, M); WRITELN('XN-', XN(X1, M)); READKEY; END. Подсчитать сумму N чисел Фибоначчи (1, 1, 2, 3, 5, 8, 13,..): PROGRAM DEMO4; USES CRT; VAR X1, X2: WORD; I, M: BYTE; S: LONGINT; FUNCTION FIB(N: BYTE): LONGINT; BEGIN IF N=1 THEN FIB: =1; IF N=2 THEN FIB: =1; IF N> =3 THEN FIB: =FIB(N-1)+FIB(N-2); END; BEGIN CLRSCR; WRITE('N-'); READLN(M); S: =0; FOR I: =1 TO M DO S: =S+FIB(I); WRITELN('S-', S); READKEY; END.

Написать рекурсивную функцию вычисления суммы 1+2+3+4+5+…+N:

PROGRAM DEMO5;

USES CRT;

VAR M: WORD;

FUNNCTION SUM(N: WORD): LONGINT;

BEGIN

IF N=1 THEN SUM: =1 ELSE SUM: =SUM(N-1)+N;

END;

BEGIN

WRITE(‘N-‘); READLN(M);

WRITELN(‘СУММА -’, SUM(M));

READKEY; END.

 


ТЕМА №7: ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ PASCAL (КОНСОЛЬНОЕ ПРИЛОЖЕНИЕ DELPHI). МАССИВЫ, ОДНОМЕРНЫЕ И ДВУХМЕРНЫЕ. СОСТАВЛЕНИЕ ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ МАССИВОВ.

 

ПРОГРАММНО - ДИДАКТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ: ЭВМ типа IBM. Delphi (консольное приложение).

ЦЕЛИ И ЗАДАЧИ: Знакомство с понятием массив и способами их обработки. Познакомиться с базовыми алгоритмами работы с массивами. Выработка навыков составления программ с использованием массивов.

ТРЕБОВАНИЯ К ЗНАНИЯМ И УМЕНИЯМ:

Учащиеся должны знать:

- Что такое массив;

- Какие бывают массивы;

- Чем отличаются одномерные и двухмерные массивы;

- Как описываются массивы в программе;

- Как обратиться к заданному элементу массива;

- Алгоритм нахождения максимума или минимума среди элементов массива;

- Простейший алгоритм сортировки элементов одномерного массива.

Учащиеся должны уметь:

- Заполнять массивы с клавиатуры или случайными числами, произвольным или заданным образом;

- Распечатывать одномерные массивы в виде строки;

- Распечатывать двухмерные массивы в виде таблиц;

- Находить заданные элементы массива;

- Заменять заданные элементы массива или производить с ними арифметические операции;

- Менять местами элементы массива;

- Находить сумму, произведение или экстремальные элементы в массиве;

- Сортировать одномерные массивы;

- Составлять программы с использованием массивов.

 

ПЛАН-СОДЕРЖАНИЕ УРОКА

Основные понятия


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.009 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал