Рекурсия в программировании паскаль

Программирование. Рекурсия Pascal-Паскаль

• Скачено бесплатно: 7728
• Куплено: 414

• Pascal-Паскаль->Программирование. Рекурсия Pascal-Паскаль

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

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

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

Пример.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программирование

Исходники Pascal (127)

Справочник

Справочник по паскалю: директивы, функции, процедуры, операторы и модули по алфавиту

лабораторные работы и задачи по программированию и информатике, егэ по информатике

Рекурсия

Если в теле функции встречается вызов самой этой функции, то это и есть рекурсия.

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

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

Рассмотрим простой пример использования рекурсивной процедуры:

procedure row(n:integer); begin if n >=1 then begin write (n, ‘ ‘); row(n-1) end; end; begin row(10); end.

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

Например: при переданном функции числе 3078 , должно в итоге вернуть 8703
Использовать операции div и mod.

procedure reverse (n: integer); begin write (n mod 10); if (n div 10) <> 0 then reverse(n div 10) end; begin writeln; reverse(3078); end.

Подсказка:
2!=2*1=2
3!=3*2*1=6
Выводим формулу a!=a*((a-1)!)

var x: integer; function fact (a: integer): integer; begin if (a sumTo(n) , которая для данного n вычисляет сумму чисел от 1 до n , например:
sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
.

var x,y: integer; function stepen (a,b: integer):integer; var . begin . end; begin writeln(‘число?’); readln(x); writeln(‘степень?’); readln(y); writeln(stepen(x,y)); end.

Для чисел 3430 и 1365:

остаток от деления 3430 на 1365	3430 mod 1365 = 700
остаток не равен нулю, повторим то же действие, подставив вместо первого числа второе, а вместо второго – остаток	1365 mod 700 = 665
остаток также не нуль, поэтому еще одно деление	700 mod 665 = 35
остаток также не нуль, поэтому еще одно деление	665 mod 35 = 0
остаток нуль	НОД равен 35

procedure fib (i,n: integer); begin writeln (i+n,’ ‘); if . then fib(. ) end; begin fib(0,1); end.

Потренируйтесь в решении задач по теме, щелкнув по пиктограмме:

Урок "Решение задач по теме "Рекурсивные алгоритмы выполнения функций и процедур" (язык программирования Паскаль).

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

1 этап урока : объяснение нового материала :

Слово рекурсия от лат. recursio означает круговорот. Синонимами этого слова являются возвращение, повторение. Классическим примером рекурсивного алгоритма является алгоритм решения задачи "Ханойские башни". Есть три стержня, на одном из которых находятся кольца разного диаметра. Необходимо переложить их с первого стержня на свободный, используя еще один.

Рассмотрим случай с пятью кольцами.

Учащимся предлагается самостоятельно составить алгоритм к этой задаче и устно описать его.

Далее учитель загружает файл Hanoy.exe и демонстрирует учащимся работу алгоритма.

Переместить пятое кольцо самого большого диаметра невозможно до тех пор, пока мы не перенесем четыре верхних. Т.е задача приводит нас к решению подобной задачи, но уже с меньшим количеством колец — четырьмя. Переместив пятое кольцо нам нужно будет положить на него четвертое, освободить которое мы можем только убрав верхние три. Т.е следующая задача, которую мы будем решать эта задача перекладывания трех колец. Продолжая наши рассуждения мы дойдем до того момента, когда нам нужно будет переложить всего лишь одно кольцо. Рекурсивный алгоритм обязательно должен иметь условие остановки. Если остановки не произойдет, он будет работать бесконечно. В нашем случае это произойдет когда количество колец для перекладывания станет равно 0.

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

Рекурсивная (процедура) функция вызывает сама себя напрямую или через другие процедуры и функции . Количество таких вызовов называется глубиной рекурсии .

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

базовые случаи здесь: 0!=1, 1!=1

рекурентная формула: N != N *( N -1)! при N >=2

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

function factorial(N: integer) : longint;
begin
if N = 0 then factorial := 1
else
factorial := factorial(N-1) * N
end;

Что же происходит, если одна функция вызывает другую?

в памяти размещаются параметры, передаваемые функции

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

запоминается адрес возврата в вызывающую функцию;

управление передается вызванной функции.

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

Действия, выполняемые функцией до входа на следующий уровень рекурсии, выполняются на прямом ходу рекурсии, а действия, выполняемые по возврату с более глубокого уровня к текущему, – выполняются на обратном ходу рекурсии.

2 этап : практическая работа за компьютером

Продемонстрируем ход рекурсии. Учащимся предлагается ввести программу в компьютер и пошагово проследить как она работает.

var glubina: i nteger := 0;
function factorial(N: integer) : longint;
begin
<при входе в функцию увеличиваем переменную, которая считает глубину рекурсии>
glubina := glubina + 1;
w riteln(‘Прямой ход рекурсии. Глубина = ‘, glubina);
result := 1;
if N > 0 then result := factorial(N-1) * N;
Writeln(‘ Обратный ход рекурсии . Глубина = ‘, glubina);
< при выходе из функции — уменьшаем эту переменную >
glubina := glubina — 1;
end;
begin
factorial(3);
end.

При запуске этой программы, будет выведено:

Прямой ход рекурсии. Глубина = 1
Прямой ход рекурсии. Глубина = 2
Прямой ход рекурсии. Глубина = 3
Прямой ход рекурсии. Глубина = 4
Обратный ход рекурсии. Глубина = 4
Обратный ход рекурсии. Глубина = 3
Обратный ход рекурсии. Глубина = 2
Обратный ход рекурсии. Глубина = 1

3 этап : закрепление нового материала при решении задач.

Рассмотрим задачи ЕГЭ , в которых присутствуют рекурсивные алгоритмы выполнения процедур. В процессе выполнения таких задач будут осуществляться рекурсивные вызовы процедуры. Необходимо правильно проследить порядок вызовов. Это возможно сделать разными способами, один из которых нарисовать дерево вызовов. Дерево может получится достаточно громоздким, поэтому более простым способом решения является анализ алгоритма, его связи с вопросом задачи. Внутри алгоритма могут находится следующие операторы:

Writeln(*); в этом случае возможен вопрос: сколько * выведется на экран после выполнения алгоритма.

Writeln(n); в этом случае может быть задан вопрос :какова сумма всех n, выводимых на экран или потребуется записать последовательность из выводимых n.

Рассмотрим следующую задачу:

Найдите сумму чисел, которые будут выведены при вызове F(2).

сумму чисел, полученных при вызове F ( n ) обозначим через S ( n ).

аккуратно и последовательно выполним вычисления:

s(2)=2+s(4)+S(6), т . е необходимо найти S(4) и s(6).

Рассмотрим еще один рекурсивный алгоритм:

if n > 0 then begin

Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?

обозначим через Z(n) количество звездочек, которые выводит программа при вызове F(n)

из программы видим, что

Z(n) = 1 при всех n

Z(n) = 1 +Z(n-2) + Z(n div 2) + Z(n div 2) при n > 0

n div 2– это частное от деления n на 2

попробуем начать с нуля:

Z(1) = 1 + Z(-1) + Z(0) + Z(0) = 1 + 1 +2* 1 =4

Z(2) = 1 + Z(0) + Z(1) + Z(1) = 1 + 1 + 2*4 = 10

Z(3) = 1 + Z(1) + Z(1)+ Z(1) = 1 +3* 4 = 13

Z(4) = 1 + Z(2) + Z(2) + Z(2) = 1 + 3*10 = 31

Z(5) = 1 + Z(3) + Z(2) + Z(2) = 1 + 13 +2*10 = 34

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

Определите, что выведет на экран программа при вызове F(9).

if n > 0 then begin

при вызове F(9) условие n>0 выполняется, распечатывается 9, затем вызывается F(n-4) = F(5), затем вызывается F(n div 2) = F(4); т.е. можно записать, что F(9)= 9 F(5) F(4)

аналогично рассматриваем F(5) и F(4)

теперь неизвестны F(2), F(1)

F(1)= 1 F(-3) F(0)=1, т.к при n

F(4)= 4 F(0) F(2) =4 2 1

F(5)= 5 F(1) F(2)=5 1 2 1

F(9)= 9 F(5) F(4)=9 5 1 2 1 4 2 1

Учащиеся могут проверить данную задачу на компьютере, выполнив следующую программу:

procedure F(n: integer);

if n > 0 then begin

Последовательность будет аналогичной.

выполнить следующие задания из открытого банка заданий ЕГЭ

Начало формы Алгоритм вычисления значения функции F ( n ), где n – натуральное число, задан следующими соотношениями:

Чему равно значение функции F (4)?

В ответе запишите только натуральное число.

Начало формы Алгоритм вычисления значения функции F ( n ), где n – натуральное число, задан следующими соотношениями:

Чему равно значение функции F (7)?

В ответе запишите только натуральное число.

Начало формы Алгоритм вычисления значения функции F ( n ), где n – натуральное число, задан следующими соотношениями:

Чему равно значение функции F (9)?

В ответе запишите только натуральное число.