• 2
  • 3
  • 4
  • 6

pascal

Процедуры и функции в Pascal

Процедуры и функции в Pascal. Часть 2.

Итак, сегодня мы с вами на learnpascal.ru продолжаем изучатьфункции и процедуры — важнейшую часть структурного программирования. В этом уроке мы рассмотрим только процедуры и функции. И даже не будем практиковаться, оставим это для последующих уроков.

Структура программы.

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

  1. program <имя программы>;
  2. label <метки>;
  3. const
  4. <описание констант>;
  5. type
  6. <описание типов данны\>;
  7. var
  8. <описание переменных>;
  9. <процедуры и функции>;
  10. begin
  11. <основное тело программы>;
  12. end.

Структура процедуры и функции

Структура процедуры.

До этого момента времени мы использовали из раздела описаний только описание переменных и типов. На этом занятии мы начнем изучать процедуры. Структура процедуры повторяет структуру программы. Отличия выделены «полужирным» шрифтом.

  1. procedure <имя процедуры> (<параметры>);
  2. label
  3. <метки>;
  4. const
  5. <описание констант>;
  6. type
  7. <описание типов данных>;
  8. var
  9. <описание переменных>;
  10. <процедуры и функции>;
  11. begin
  12. <основное тело процедуры>;
  13. end;

Напишу простую программу с процедурой, складывающей два числа.

  1. var
  2. a, b, c: integer;
  3. procedure sum(x, y: integer; var z: integer);
  4. begin
  5. z := x + y;
  6. end;
  7. begin
  8. write('Введите два числа: ');
  9. readln(a, b);
  10. sum(a, b, c); {процедура вызывается своим именем, которое вы написали после зарезервированного слова procedure в описании}
  11. writeln(c);
  12. end.

Итак, что вы видите? Точнее, что вам не понятно в данной программе? Я думаю, что вы не можете понять, почему перед z стоит var, а перед x, y — нет. Но всему свое время.

Процедуры и функцииhttp://learnpascal.ru/wp-content/uploads/2014/06/процедура-300x120.jpeg 300w, http://learnpascal.ru/wp-content/uploads/2014/06/процедура-510x204.jpeg 510w" sizes="(max-width: 1000px) 100vw, 1000px">

Обратимся к примеру, приведенному на рисунке выше. Слева приведен фрагмент текста основной программы, справа — процедура. Как только в теле программы объявляется имя процедуры с параметрами, выполнение «главного» тела прекращается, и управление вычислительными процессами передается процедуре. После выполнения процедуры осуществляется возврат на оператор основной программы, следующий за вызовом процедуры.

Немножко теории:
В любой программе все переменные делятся на два типа: локальные и глобальные. В нашей программы переменные а, b, с — глобальные, а х, у, z — локальные. Глобальные переменные — это переменные из раздела описаний основной части программы, а локальные — из раздела описаний процедур и функций. Локальные переменные существуют только в течение времени работы процедуры, определяются (создаются) при её вызове и исчезают после завершении работы процедуры.

В программе определены переменные a, b, c. В процедуре x, y, z — её параметры, и они являются переменными процедуры. Причем между х, у  и z существует большая разница.

Поясню ее очередным рисунком.

Параметрыhttp://learnpascal.ru/wp-content/uploads/2014/06/параметры-300x120.jpeg 300w, http://learnpascal.ru/wp-content/uploads/2014/06/параметры-510x204.jpeg 510w" sizes="(max-width: 1000px) 100vw, 1000px">

Параметры.

При описании процедуры указывается список формальных параметров. Каждый параметр является локальным по отношению к описываемой процедуре, к нему можно обращаться только в пределах данной процедуры (в нашем примере х, у, z — формальные параметры). Фактические параметры — это параметры, которые передаются процедуре при обращении к ней (а, b, с — фактические параметры). Число и тип формальных и фактических параметров должны совпадать с точностью до их следования.

Параметры-значения.

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

Параметры-переменные.

Другими словами, передача параметров по ссылке. Это те формальные параметры, перед которыми стоит идентификатор var. Передается адрес фактического параметра (обязательно переменной), после этого формальный
параметр становится его синонимом. Любые операции с формальным параметром выполняются непосредственно над фактическим параметром.

Структура функции

Функция выглядит почти так же, как и процедура. Почти единственное отличие в том, что заголовок функции начинается с ключевого слова Function и кончается типом возвращаемого данной функцией значения.

  1. function <имя функции> (<список формальных операторов>): <тип возвращаемого значения>;

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

Пример:

  1. var
  2. a, b, c: integer;
  3. function sum(x, y: integer): integer;
  4. begin
  5. sum := x + y;
  6. end;
  7. begin
  8. readln(a, b);
  9. writeln(sum(a, b));
  10. end.

Или так:

  1. var
  2. a, b, c: integer;
  3. function sum(x, y: integer): integer;
  4. begin
  5. result := x + y;
  6. end;
  7. begin
  8. readln(a, b);
  9. writeln(sum(a, b));
  10. end.
НЕБОЛЬШОЕ ПОСЛЕСЛОВИЕ:

Каждая процедура должна иметь одну точку входа и одну точку выхода (то есть использование goto, break, exit нежелательно), использование глобальных переменных в процедуре следует свести к минимуму, взаимодействие с процедурой должно осуществляться (по возможности) только через параметры.
Постепенно вы должны отказаться от технологии неструктурированного программирования. Сегодня мы с вами осваиваем структурную технологию разработки программ, при этом на каждом этапе текущая задача разбивается на ряд подзадач, определяя тем самым некоторое количество отдельных подпрограмм. Концепция процедур и функций — один из механизмов второго витка развития технологий программирования, а именно, структурного проектирования.

Циклы Pascal

Циклы. Тексты программ

 
 

Вывод последовательностей 1 2 3 4 5 и 5 4 3 2 1

var i: integer;
begin
// С помощью for
  for i := 1 to 5 do
    write(i,' ');
  writeln;
 
  for i := 5 downto 1 do
    write(i,' ');
  writeln;
  writeln;
 
// С помощью while
  i := 1;
  while i<=5 do
  begin
    write(i,' ');
    i := i + 1;
  end;
  writeln;
 
  i := 5;
  while i>=1 do
  begin
    write(i,' ');
    i := i - 1;
  end;
  writeln;
  writeln;
 
// С помощью repeat
  i := 1;
  repeat
    write(i,' ');
    i := i + 1;
  until i>5;
  writeln;
 
  i := 5;
  repeat
    write(i,' ');
    i := i - 1;
  until i<1;
  writeln;
end.

Вывод последовательности 1 3 5 7 9

var i,x: integer;
begin
// С помощью for и промежуточной переменной
  x := 1;
  for i := 1 to 5 do
  begin
    write(x,' ');
    x := x + 2;
  end;
  writeln;
 
// С помощью for без промежуточной переменной
  for i := 1 to 5 do
    write(2*i-1,' ');
  writeln;
 
// С помощью while
  x := 1;
  while x<10 do
  begin
    write(x,' ');
    x := x + 2;
  end;
  writeln;
 
// С помощью repeat
  x := 1;
  repeat
    write(x,' ');
    x := x + 2;
  until x>=10;
end.

Сумма и произведение введенных чисел

Код на Pascal

var 
  i: integer;
  s,p: real;
  x: real;
begin
  writeln('Введите 10 чисел: ');
  s := 0;
  p := 1;
  for i := 1 to 10 do
  begin
    read(x);
    s := s + x;
    p := p * x;
  end;
  writeln('Сумма введенных чисел = ',s);
  writeln('Произведение введенных чисел = ',p);
end.

Код на PascalABC.NET

var 
  s,p: real;
begin
  writeln('Введите 10 чисел: ');
  s := 0;
  p := 1;
  for var i := 1 to 10 do
  begin
    var x: integer;
    read(x);
    s += x;
    p *= x;
  end;
  writeln('Сумма введенных чисел = ',s);
  writeln('Произведение введенных чисел = ',p);
end.

Вычисление n!

Код на Pascal

var 
  n,fact: integer;
  i: integer;
begin
  write('Введите n (n<=13): ');
  readln(n);
  fact := 1;
  for i := 2 to n do
    fact := fact * i;
  writeln(n,'! = ',fact);
end.

Код на PascalABC.NET

var n: integer;
begin
  write('Введите n (n<=13): ');
  readln(n);
  var fact := 1;
  for var i := 2 to n do
    fact *= i;
  writeln(n,'! = ',fact);
end.

Вычисление An

Код на Pascal

var 
  n,i: integer;
  a,p: real;
begin
  write('Введите a,n: ');
  readln(a,n);
  p := 1;
  for i := 1 to n do
    p := p * a;
  writeln(a,' в степени ',n,' = ',p);
end.

Код на PascalABC.NET

var 
  n: integer;
  a: real;
begin
  write('Введите a,n: ');
  readln(a,n);
  var p := 1.0;
  for var i := 1 to n do
    p *= a;
  writelnFormat('{0} в степени {1} = {2}',a,n,p);
end.

Вывод цифр числа

var x: integer;
 
begin
  write('Введите x: ');
  readln(x);
  write('Цифры числа x в обратном порядке: ');
  while x<>0 do
  begin
    write(x mod 10,' ');
    x := x div 10;
  end;
end.

Вывод букв английского алфавита

var c: char;
 
begin
  for c := 'a' to 'z' do
    write(c,' ');
  writeln;  
  c := 'A';
  while c<='Z' do
  begin
    write(c,' ');
    c := succ(c);
  end;
end.

Числа Фибоначчи

Код на Pascal

const n = 25;
 
var 
  a,b,c: integer;
  i: integer;  
 
begin
  a := 1;
  b := 1;
  write(a,' ',b,' ');
  for i := 3 to n do
  begin
    c := a + b;
    write(c,' ');
    a := b;
    b := c;
  end;
end.

Код на PascalABC.NET

const n = 25;
 
begin
  var a := 1;
  var b := 1;
  write(a,' ',b,' ');
  for var i := 3 to n do
  begin
    var c := a + b;
    write(c,' ');
    a := b;
    b := c;
  end;
end.

Минимум из введенных

Код на Pascal

const n = 10;
 
var  
  min: integer;
  x: integer;
  i: integer;
 
begin
  writeln('Введите ',n,' значений: ');
  read(x);  
  min := x;  
  for i := 2 to n do
  begin
    read(x);
    if x<min then
      min := x;
  end;
  writeln('Минимальное значение = ',min);
end.

Код на PascalABC.NET

const n = 10;
 
var min: integer;
 
begin
  writelnFormat('Введите {0} значений: ',n);
  min := integer.MaxValue;  
  for var i := 1 to n do
  begin
    var x: integer;
    read(x);
    if x<min then
      min := x;
  end;
  writeln('Минимальное значение = ',min);
end.

Алгоритм Евклида поиска НОД

var a,b,c: integer;
 
begin
  writeln('Введите a,b: ');
  read(a,b);  
  while b<>0 do
  begin
    c := a mod b;
    a := b;
    b := c;
  end;
  writeln('Наибольший Общий Делитель = ',a);
end.

Вывод таблицы умножения

Код на PascalABC.NET

const n = 9;
 
begin
  for var i:=1 to n do
  begin
    for var j:=1 to n do
      write(i*j:4);
    writeln;  
  end;
end.

Определение простоты числа

var 
  N: integer;
  IsSimple: boolean;
 
begin
  writeln('Введите число: ');
  readln(N);
 
  IsSimple := True;
  for var i:=2 to round(sqrt(N)) do // если число составное, то один из его сомножителей <= sqrt(N) 
    if N mod i = 0 then
    begin
      IsSimple := False;
      break;
    end;
 
  if IsSimple then
    writeln('Число ',N,' простое')
  else writeln('Число ',N,' составное');  
end.

Рекурсия Pascal-Паскаль

Подпрограммы в Паскале могут обращаться сами к себе. Такое обращение называется рекурсией.

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

Пример.

Рассмотрим математическую головоломку из книги Ж. Арсака «Программирование игр и головоломок».

Построим последовательность чисел следующим образом: возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если i=1, то последовательность останавливается.

Математически конечность последовательности независимо от начального i не доказана, но на практике последовательность останавливается всегда.

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

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

Program Arsac;
Var first: word;
Procedure posledov (i: word); 
Begin 
   Writeln (i); 
   If i=1 then exit
   If odd(i) then posledov(3*i+1else posledov(i div 2); 
End
Begin 
   Write (' введите первое значение '); readln (first); 
   Posledov (first); 
   Readln ; 
End.

Программист разрабатывает программу, сводя исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме. Например, для вычисления F( N) может понадобиться вычислить F( N-1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.

Алгоритм, который является своей собственной частью, называется рекурсивным. Часто в основе такого алгоритма лежит рекурсивное определение.

Пример рекурсивного алгоритма

N! = ( N-1)!* N, если N=0, то N!= 1

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

Пример рекурсивного алгоритма

2n2 n-1*2, если n=0, то 2 n= 1

Процедура является рекурсивной, если она обращается сама к себе прямо или косвенно (через другие процедуры).

схема рекурсии

Заметим, что при косвенном обращении все процедуры в цепочке – рекурсивные.

Все сказанное о процедурах целиком относится и к функциям.

Пример рекурсивной функции вычисления факториала

Function factorial(N: integer) : longint; 
Begin 
   If N= 0 then 
   Factorial := 1 
   Else Factorial := factorial(N-1) * N 
End;

Рекурсия изнутри

Это может показаться удивительным, но самовызов процедуры ничем не отличается от вызова другой процедуры. Что происходит, если одна процедура вызывает другую? В общих чертах следующее:

  • в памяти размещаются параметры, передаваемые процедуре (но не параметры-переменные!);
  • в другом месте памяти сохраняются значения внутренних переменных вызывающей процедуры;
  • запоминается адрес возврата в вызывающую процедуру;
  • управление передается вызванной процедуре.

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

Пусть рекурсивная процедура Power( X, N, Y) возводит число X в степень N и возвращает результат Y .

Пример рекурсивной процедуры, возводящей число в степень

Procedure Power (X: real; N: integer; var Y: real); 
Begin 
   If N=0 then 
      Y:= 1 
   Else Begin Power(X, N-1,Y); 
      Y:= Y*X; 
   End ; 
End ;

Проследим за состоянием памяти в процессе выполнения вызова данной процедуры Power(5,3, Y). Стрелка «->» означает вход в процедуру, стрелка «<-» означает выход из нее.

состояние памяти при рекурсии

Число копий переменных, одновременно находящихся в памяти, называется глубиной рекурсии. Как видно из примера, сначала она растет, а затем сокращается.

Подведем итог.

  • рекурсивной называется такая процедура или функция, которая вызывает сама себя;
  • для завершения процесса рекурсии в алгоритме рекурсивной функции (процедуры) обязательно должно быть условие, обеспечивающее непосредственное завершение функции (процедуры).

Напишем программу вычисления функции, заданной следующим образом:

F(1)=1; F(2n)=F(n); F(2n+1)=F(n)+F(n+1)

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

Таким образом, работа алгоритма будет состоять из некоторого количества шагов, на каждом из которых будут выполняться два действия:

  • Определение четности или нечетности аргумента. От этого зависит выбор формулы вычислений;
  • Выполнение вычислений. Фактически это будет сводиться к определению нового аргумента функции.

Пример рекурсивной программы вычисления функции

Program primer; 
Uses crt; 
Var 
   N, a: integer; 
Function f(n:integer):integer; 
Begin 
   If n =1 then 
      f :=1 {условие завершения рекурсии} 
   Else 
   Begin 
      If odd ( n ){проверка на нечетность числа} 
      then begin 
         n:= n div 2
         f:=f(n)+f(n+1)
      end 
      else begin 
         n:= n div 2
         f:=f(n) 
      end
   end ; 
end ; 
begin {начало основной программы} 
   clrscr; 
   write(' Введите число – '); 
   readln(n); 
   a:=f(n); 
   write(' результат – ', a); 
end.

Рекурсивная программа построения снежинки

Написать программу, строящую на экране изображение:

Пример рекурсивной программы построения окружностей

Изображение строится по следующему правилу: строится окружность с заданным радиусом r. Затем на диаметрально противоположных точках окружности ( x- r и x+ r)строится вновь окружность меньшего радиуса ( r=3 r/5). Для каждой меньшей окружности на диаметрально противоположных точках вновь строится окружность меньшего радиуса, и т.д., пока радиус не уменьшится до 10.

Пример рекурсивной программы построения окружностей

program recurs; 
uses graph; 
var x,y,r,d,m:integer; 
procedure ris(x,y,r:integer); 
var i:integer; 
begin 
   if r<10 then exit
   circle(x,y,r); 
   for i:=1 to 1000 do{ просто цикл задержки } 
   ris(x+r,y,r*3 div 5); 
   ris(x-r,y,r*3 div 5); 
end ; 
begin {начало основной программы} 
   d:=detect; 
   initgraph(d,m,'e:\bp\bgi'); 
   x:=320
   y:=240
   r:=120
   ris(x,y,r); 
   readln ; 
end.

Пример рекурсивной программы построения снежинки

Как видно из рисунка, здесь опять повторяются одни и те же фрагменты. Построение выполняется так: на окружности заданного радиуса r берется 6 равноотстоящих точек (начиная от угла в 0 0, с шагом ?/3), из каждой точки к центру окружности проводятся радиусы. Затем каждая из этих точек выступает центром новой, меньшей окружности с радиусом r=2 r/5. На каждой меньшей окружности вновь берется 6 равноотстоящих точек, из которых строятся радиусы к центру, и т.д., пока радиус не станет меньше или равен 1.

Пример рекурсивной программы построения снежинки

program sneg;
uses graph, crt; 
var 
   x,y,r,d,m:integer; 
procedure ris(x,y,r:integer); 
var 
   x1,y1,t:integer; 
begin 
   if r<=1 then begin putpixel(x,y,15);exit end
   for t:=0 to 6 do 
   begin 
      x1:=x+trunc(r*cos(t*pi/3)); 
      y1:=y+trunc(r*sin(t*pi/3)); 
      line(x,y,x1,y1); 
      ris(x1,y1,r*2 div 5); 
      delay(500); 
   end
end
begin 
   d:=detect; 
   initgraph(d,m,'e:\bp\bgi'); 
   x:=320
   y:=240
   r:=80
   ris(x,y,r); 
   readln; 
end.

Пример «Кривой Дракона».

Рассмотрим пример решения еще одной классической задачи: «Кривая Дракона».

Изображение кривой Дракона выглядит так:

Пример рекурсивной программы «Кривая Дракона»

Очень красиво, не правда ли. Разберемся, как же эта кривая получается.

Возьмем длинную полоску бумаги и сложим ее пополам, а затем развернем на 90. Если смотреть на полоску сбоку, то получится ломаная линия из двух перпендикулярных участков: см. рис. а. Теперь сложим полоску пополам дважды и также дважды развернем на 90 так, как это показано на рис. б. Получим ломаную линию уже из четырех отрезков, причем угол между смежными отрезками составляет 90. Наконец, если сложение и разворачивание полоски осуществить три раза, то в результате получится фигура, представленная на рис. в. Продолжая этот процесс, можно получить кривую, аналогичную той, которая представлена на рис. 1. Эту причудливую кривую называют кривой дракона. Способ построения подсказывает, что она не имеет самопересечений.

Пример рекурсивной программы «Кривая Дракона»

Кривая дракона впервые была описана в популярной литературе в журнале Scientific American в 1967 году. Заметка о ней появилась в колонке “Математические игры”, которую вел Мартин Гарднер. Первоначально использовалось полное название кривой – «дракон Хартера — Хейтуэя», которое ей дал основатель компьютерной фрактальной геометрии Бенуа Мандельброт, именем которого названо знаменитое множество. В дальнейшем стали говорить просто о кривой дракона. Выше мы описали один из алгоритмов построения кривой. На наш взгляд, он несколько запутан (хотя и достаточно прост в реализации). Приведем описание алгоритма построение кривой, близкое к тому, которое использовалось Мартином Гарднером.

Пример рекурсивной программы «Кривая Дракона»

Рассмотрим горизонтальный отрезок как кривую дракона нулевого порядка. Разделим отрезок пополам и построим на нем прямой угол, как показано на рис. а).

Пример рекурсивной программы «Кривая Дракона»

Получим кривую дракона первого порядка. На сторонах прямого угла снова построим прямые углы (рис. б).

При этом вершина первого угла всегда находится справа, если смотреть из точки A (начала кривой) вдоль первого отрезка кривой, а направления, в которых строятся вершины остальных углов, чередуются. На рис. в) и г) показаны кривые дракона третьего и четвертого порядков соответственно.

Пример рекурсивной программы «Кривая Дракона»

Пример рекурсивной программы «Кривая Дракона»

program dragon;
uses graph; 
var k,d,m:integer;
procedure ris(x1,y1,x2,y2,k:integer); 
var xn,yn:integer; 
begin 
   if k>0 then 
   begin 
      xn:=(x1+x2) div 2 +(y2-y1) div 2
      yn:=(y1+y2) div 2 -(x2-x1) div 2
      ris(x1,y1,xn,yn,k-1); 
      ris(x2,y2,xn,yn,k-1); 
   end 
   else begin line(x1,y1,x2,y2); end
end
begin 
   readln ( k );{задаем порядок кривой} 
   d:=detect; 
   initgraph(d,m,'e:\bp\bgi'); 
   ris(200,300,500,300,k); 
   readln; 
end.

Рекурсия Pascal-Паскаль

Подпрограммы в Паскале могут обращаться сами к себе. Такое обращение называется рекурсией.

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

Пример.

Рассмотрим математическую головоломку из книги Ж. Арсака «Программирование игр и головоломок».

Построим последовательность чисел следующим образом: возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если i=1, то последовательность останавливается.

Математически конечность последовательности независимо от начального i не доказана, но на практике последовательность останавливается всегда.

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

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

Program Arsac;
Var first: word;
Procedure posledov (i: word); 
Begin 
   Writeln (i); 
   If i=1 then exit
   If odd(i) then posledov(3*i+1else posledov(i div 2); 
End
Begin 
   Write (' введите первое значение '); readln (first); 
   Posledov (first); 
   Readln ; 
End.

Программист разрабатывает программу, сводя исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме. Например, для вычисления F( N) может понадобиться вычислить F( N-1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.

Алгоритм, который является своей собственной частью, называется рекурсивным. Часто в основе такого алгоритма лежит рекурсивное определение.

Пример рекурсивного алгоритма

N! = ( N-1)!* N, если N=0, то N!= 1

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

Пример рекурсивного алгоритма

2n2 n-1*2, если n=0, то 2 n= 1

Процедура является рекурсивной, если она обращается сама к себе прямо или косвенно (через другие процедуры).

схема рекурсии

Заметим, что при косвенном обращении все процедуры в цепочке – рекурсивные.

Все сказанное о процедурах целиком относится и к функциям.

Пример рекурсивной функции вычисления факториала

Function factorial(N: integer) : longint; 
Begin 
   If N= 0 then 
   Factorial := 1 
   Else Factorial := factorial(N-1) * N 
End;

Рекурсия изнутри

Это может показаться удивительным, но самовызов процедуры ничем не отличается от вызова другой процедуры. Что происходит, если одна процедура вызывает другую? В общих чертах следующее:

  • в памяти размещаются параметры, передаваемые процедуре (но не параметры-переменные!);
  • в другом месте памяти сохраняются значения внутренних переменных вызывающей процедуры;
  • запоминается адрес возврата в вызывающую процедуру;
  • управление передается вызванной процедуре.

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

Пусть рекурсивная процедура Power( X, N, Y) возводит число X в степень N и возвращает результат Y .

Пример рекурсивной процедуры, возводящей число в степень

Procedure Power (X: real; N: integer; var Y: real); 
Begin 
   If N=0 then 
      Y:= 1 
   Else Begin Power(X, N-1,Y); 
      Y:= Y*X; 
   End ; 
End ;

Проследим за состоянием памяти в процессе выполнения вызова данной процедуры Power(5,3, Y). Стрелка «->» означает вход в процедуру, стрелка «<-» означает выход из нее.

состояние памяти при рекурсии

Число копий переменных, одновременно находящихся в памяти, называется глубиной рекурсии. Как видно из примера, сначала она растет, а затем сокращается.

Подведем итог.

  • рекурсивной называется такая процедура или функция, которая вызывает сама себя;
  • для завершения процесса рекурсии в алгоритме рекурсивной функции (процедуры) обязательно должно быть условие, обеспечивающее непосредственное завершение функции (процедуры).

Напишем программу вычисления функции, заданной следующим образом:

F(1)=1; F(2n)=F(n); F(2n+1)=F(n)+F(n+1)

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

Таким образом, работа алгоритма будет состоять из некоторого количества шагов, на каждом из которых будут выполняться два действия:

  • Определение четности или нечетности аргумента. От этого зависит выбор формулы вычислений;
  • Выполнение вычислений. Фактически это будет сводиться к определению нового аргумента функции.

Пример рекурсивной программы вычисления функции

Program primer; 
Uses crt; 
Var 
   N, a: integer; 
Function f(n:integer):integer; 
Begin 
   If n =1 then 
      f :=1 {условие завершения рекурсии} 
   Else 
   Begin 
      If odd ( n ){проверка на нечетность числа} 
      then begin 
         n:= n div 2
         f:=f(n)+f(n+1)
      end 
      else begin 
         n:= n div 2
         f:=f(n) 
      end
   end ; 
end ; 
begin {начало основной программы} 
   clrscr; 
   write(' Введите число – '); 
   readln(n); 
   a:=f(n); 
   write(' результат – ', a); 
end.

Рекурсивная программа построения снежинки

Написать программу, строящую на экране изображение:

Пример рекурсивной программы построения окружностей

Изображение строится по следующему правилу: строится окружность с заданным радиусом r. Затем на диаметрально противоположных точках окружности ( x- r и x+ r)строится вновь окружность меньшего радиуса ( r=3 r/5). Для каждой меньшей окружности на диаметрально противоположных точках вновь строится окружность меньшего радиуса, и т.д., пока радиус не уменьшится до 10.

Пример рекурсивной программы построения окружностей

program recurs; 
uses graph; 
var x,y,r,d,m:integer; 
procedure ris(x,y,r:integer); 
var i:integer; 
begin 
   if r<10 then exit
   circle(x,y,r); 
   for i:=1 to 1000 do{ просто цикл задержки } 
   ris(x+r,y,r*3 div 5); 
   ris(x-r,y,r*3 div 5); 
end ; 
begin {начало основной программы} 
   d:=detect; 
   initgraph(d,m,'e:\bp\bgi'); 
   x:=320
   y:=240
   r:=120
   ris(x,y,r); 
   readln ; 
end.

Пример рекурсивной программы построения снежинки

Как видно из рисунка, здесь опять повторяются одни и те же фрагменты. Построение выполняется так: на окружности заданного радиуса r берется 6 равноотстоящих точек (начиная от угла в 0 0, с шагом ?/3), из каждой точки к центру окружности проводятся радиусы. Затем каждая из этих точек выступает центром новой, меньшей окружности с радиусом r=2 r/5. На каждой меньшей окружности вновь берется 6 равноотстоящих точек, из которых строятся радиусы к центру, и т.д., пока радиус не станет меньше или равен 1.

Пример рекурсивной программы построения снежинки

program sneg;
uses graph, crt; 
var 
   x,y,r,d,m:integer; 
procedure ris(x,y,r:integer); 
var 
   x1,y1,t:integer; 
begin 
   if r<=1 then begin putpixel(x,y,15);exit end
   for t:=0 to 6 do 
   begin 
      x1:=x+trunc(r*cos(t*pi/3)); 
      y1:=y+trunc(r*sin(t*pi/3)); 
      line(x,y,x1,y1); 
      ris(x1,y1,r*2 div 5); 
      delay(500); 
   end
end
begin 
   d:=detect; 
   initgraph(d,m,'e:\bp\bgi'); 
   x:=320
   y:=240
   r:=80
   ris(x,y,r); 
   readln; 
end.

Пример «Кривой Дракона».

Рассмотрим пример решения еще одной классической задачи: «Кривая Дракона».

Изображение кривой Дракона выглядит так:

Пример рекурсивной программы «Кривая Дракона»

Очень красиво, не правда ли. Разберемся, как же эта кривая получается.

Возьмем длинную полоску бумаги и сложим ее пополам, а затем развернем на 90. Если смотреть на полоску сбоку, то получится ломаная линия из двух перпендикулярных участков: см. рис. а. Теперь сложим полоску пополам дважды и также дважды развернем на 90 так, как это показано на рис. б. Получим ломаную линию уже из четырех отрезков, причем угол между смежными отрезками составляет 90. Наконец, если сложение и разворачивание полоски осуществить три раза, то в результате получится фигура, представленная на рис. в. Продолжая этот процесс, можно получить кривую, аналогичную той, которая представлена на рис. 1. Эту причудливую кривую называют кривой дракона. Способ построения подсказывает, что она не имеет самопересечений.

Пример рекурсивной программы «Кривая Дракона»

Кривая дракона впервые была описана в популярной литературе в журнале Scientific American в 1967 году. Заметка о ней появилась в колонке “Математические игры”, которую вел Мартин Гарднер. Первоначально использовалось полное название кривой – «дракон Хартера — Хейтуэя», которое ей дал основатель компьютерной фрактальной геометрии Бенуа Мандельброт, именем которого названо знаменитое множество. В дальнейшем стали говорить просто о кривой дракона. Выше мы описали один из алгоритмов построения кривой. На наш взгляд, он несколько запутан (хотя и достаточно прост в реализации). Приведем описание алгоритма построение кривой, близкое к тому, которое использовалось Мартином Гарднером.

Пример рекурсивной программы «Кривая Дракона»

Рассмотрим горизонтальный отрезок как кривую дракона нулевого порядка. Разделим отрезок пополам и построим на нем прямой угол, как показано на рис. а).

Пример рекурсивной программы «Кривая Дракона»

Получим кривую дракона первого порядка. На сторонах прямого угла снова построим прямые углы (рис. б).

При этом вершина первого угла всегда находится справа, если смотреть из точки A (начала кривой) вдоль первого отрезка кривой, а направления, в которых строятся вершины остальных углов, чередуются. На рис. в) и г) показаны кривые дракона третьего и четвертого порядков соответственно.

Пример рекурсивной программы «Кривая Дракона»

Пример рекурсивной программы «Кривая Дракона»

program dragon;
uses graph; 
var k,d,m:integer;
procedure ris(x1,y1,x2,y2,k:integer); 
var xn,yn:integer; 
begin 
   if k>0 then 
   begin 
      xn:=(x1+x2) div 2 +(y2-y1) div 2
      yn:=(y1+y2) div 2 -(x2-x1) div 2
      ris(x1,y1,xn,yn,k-1); 
      ris(x2,y2,xn,yn,k-1); 
   end 
   else begin line(x1,y1,x2,y2); end
end
begin 
   readln ( k );{задаем порядок кривой} 
   d:=detect; 
   initgraph(d,m,'e:\bp\bgi'); 
   ris(200,300,500,300,k); 
   readln; 
end.

MVSocialButtons

Share this post

Отправить в FacebookОтправить в Google BookmarksОтправить в OdnoklassnikiОтправить в Vkcom

Авторизация

Новые пользователи

  • RubenAbsex
  • ArtemAGFa
  • GennadiyHah
  • JorgeGrore
  • Bobbyphiva

Статистика сайта

ОС
Linux v
PHP
5.6.31
MySQLi
5.5.56-cll-lve
Время
08:13
Кэширование
Отключено
GZip
Отключено
Посетители
20569
Материалы
282
Количество просмотров материалов
249412
cassidy clay free pornmalay young girls sucking cockbeeg gallery hdchina young sexyoung inzestpornfree download sunny leon porn hd vedeos moviesxxx.biz Bangladeshi scandalfree daughter gangbangöld granny fikautumn riley porn video free download Bangladeshi scandalfree daughter gangbangöld granny fikautumn riley porn video free download mobile porn sexyoung inzestpornfree download sunny leon porn hd vedeos