Рекурсия.  

Рекурсия.

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

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

Рассмотрим построение рекурсивной функции на примере вычисления 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 (консольное приложение).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


0142705536901502.html
0142738911046298.html
    PR.RU™