Как сделать рекурсию в паскале

Обновлено: 03.07.2024

Для начала разберемся, что же такое рекурсивная функция. А рекурсивная функция – это не что иное, как функция, которая вызывает сама себя до тех пор, пока не выполнится условие. Грубо говоря, можно провести аналогию с циклом Repeat Until . Смысл тот же, но с отличием того, что занимает меньше времени на написание программного кода. В общем-то рекурсивная функция тот же цикл, только не явный, но в использовании намного удобнее. На эти два примера мы сейчас и будем опираться, а разницу вы увидите сами.

Создадим функцию factorial , в которую будут возвращаться значения с типом Longint , так как полученные значения могут быть огромными.

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

И если вам покажется объяснения очень трудным для понимания, то прокрутите в конец данной статьи. Там на простых примерах объясняется принцип работы рекурсивной функции.

Стандартные операторы, такие как readln , writeln я думаю понятны. Поэтому сразу перейдем разбирать написанную функцию factorial .

С виду обычная функция, кроме одного момента, а именно условие if . Здесь именно это условие помогает нам определить условие выхода из функции или продолжение на выполнение.

Разберем условие с конца, если x >1, получаем factorial := x * factorial ( x -1). Как же работает это выражение? Вы спросите как так, мы вводим, к примеру, число 5, а он поочередно умножает нам каждое число от 1 до 5?

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

Вызов функции

factorial:= 5 * factorial (5-1)

Пока что мы не можем вычислить factorial числа 5, так как мы вызвали функцию еще раз и необходимо вычислить теперь факториал 4

factorial:= 4 * factorial (4-1)

Пока что мы не можем вычислить factorial числа 4, так как мы вызвали функцию еще раз и необходимо вычислить теперь факториал 3

factorial:= 3 * factorial (3-1)

Пока что мы не можем вычислить factorial числа 3, так как мы вызвали функцию еще раз и необходимо вычислить теперь факториал 2

factorial:= 2 * factorial (2-1)

Пока что мы не можем вычислить factorial числа 2, так как мы вызвали функцию еще раз и необходимо вычислить теперь факториал 1

if x = 1 then factorial:= 1.

Теперь x = 1 и функция прекращает своё действие и возвращаем 1.

Теперь программа можем вычислить факториалы поочередно от 1 до 5, так как мы больше не вызываем нашу функцию.

Вызов функции

factorial:= 2 * factorial (1)

В factorial (1) нам вернулось число 1 и записываем значение в factorial = 2;

factorial:= 3 * factorial (2)

В factorial (2) нам вернулось число 2 и записываем значение в factorial = 6;

factorial:= 4 * factorial (3)

В factorial (3) нам вернулось число 6 и записываем значение в factorial = 24;

factorial:= 5 * factorial (4)

В factorial (4) нам вернулось число 24 и записываем значение в factorial = 120;

Я с Вами согласен, что немного трудно для понимания и написано очень много. Но это всё примеры работы этой функции и ничего более.

Я думаю, разница сразу бросается в глаза. Хотя принцип очень схож. Там мы вызываем функцию factorial до тех пор, пока x не станет равен 1, и здесь пока n не станет равен 1. Но на деле, понимание работы и использование рекурсивных функций намного упрощает написание кода и занимает меньше времени.

Приведу простенькие примеры из жизни для более глубокого понимания принципа рекурсии(Ведь рекурсия может быть и многосложной, к примеру для поиска выхода из лабиринта или в итоге - зацикленной):

Принцип матрешки . Вам поставили задачу посчитать количество матрешек в каждой из вложенных внутри. Вы же не можете сказать точное количество вложенных матрешек, пока не откроете каждую. Придется открыть каждую матрешку, а потом, уже, вкладывая их в друг друга считать, сколько в каждой из них находится матрешка поменьше. Из этого следует, что в 5-ой матрешке будет 4(но мы не узнаем, пока не откроем все матрешки до 4-ой), в 3-ей матрешке будет 2(но мы не узнаем, пока не откроем все матрешки до 3-ой) и так далее.

Грязное пятно . Бывает порой, что одежда пачкается маслом. Так вот, пятно от масла легко убирается бензином. Теперь проблема, надо оттереть сам бензин, а от бензина поможет раствор щёлочи. Но вот незадача, щелочь. Щелочь уберем эссенцией. Ага, теперь след от эссенции необходимо протереть маслом. А теперь вообще не проблема, как убрать пятно от масла мы уже знаем.

У попа была собака. Все докучные песни-сказки основаны на рекурсии. Только нет условия для выхода из неё. У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: "У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал:…..

В этом всём и заключается основной принцип функций-процедур-рекурсий. Не забываем, что решает всё практика и только практика. Без неё никакого понимания не придет. Можете, как и я, найти такие шуточные игры или песни-сказки и на их примере потренироваться в использовании рекурсивной функции или процедуры. В дальнейшем пригодится для решения очень многих задач, вставших перед вами.

Рекурсия. Примеры программ на языке Pascal с использованием рекурсивных процедур и функций.

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

Для работы рекурсивной подпрограммы используется стек.
Стек – особая область памяти, в которой хранятся локальные переменные и адреса возврата из подпрограммы. Когда выполняется возврат из рекурсивной подпрограммы, состояние стека изменяется в обратную сторону (“последний вошёл – первым вышел”).

Работу рекурсивной подпрограммы продемонстрируем на следующей задаче.

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

Прямой ход процедуры: 1 2 3 4 5 6 7 8 9 10

Обратный ход процедуры: 10 9 8 7 6 5 4 3 2 1

var n,k:integer;

procedure Print_N(n,k:integer);

if n=k then begin writeln;
write('Обратный ход процедуры: ',n,' '); exit;
end;

write('Прямой ход процедуры: ');

Пример:
Напечатать последовательность чисел в обратном порядке, используя рекурсивный вызов процедуры. Например: row (5) = 5 4 3 2 1

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

1 procedure row(n:integer);

3 if n =1 then begin

4 write (n, ' ');

7 end;

8 begin

9 row(5);

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

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

1 procedure reverse (n: integer);

2 begin

3 write (n mod 10);

4 if (n div 10) 0 then

5 reverse(n div 10)

6 end;

7 begin

8 writeln;

9 reverse(3078);

10 end.

Пример. Создать рекурсивную функцию для вычисления факториала числа A!

Подсказка:
1!=1

Выводим рекуррентную формулу a!=a·(a-1)!

var x: integer;

function fact (a: integer): integer;

write('Введи число:'); readln(x);

writeln(x,'! = ',fact(x));

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

№ 1. Написать программу с рекурсивной функцией sumTo(n), которая для заданного n вычисляет сумму натуральных чисел от 1 до n, например:

sumTo(1) = 1

sumTo(2) = 2 + 1 = 3

sumTo(3) = 3 + 2 + 1 = 6

№ 2. Написать программу с рекурсивной функцией, вычисляющей
X Y , где Y – целое число, включая 0.

№ 3. Найти НОД методом Евклида (модифицированного
алгоритма Евклида). Использовать рекурсивную функцию.

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

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

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

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

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

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

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

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

Иными словами, чтобы получить значение факториала от числа N, достаточно умножить на N значение факториала от предыдущего числа:

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

После запуска программы на экран выводится запрос "Введите число N > ", затем с клавиатуры считывается введенное значение и в выражении F:=RecFact(N) вызывается функция RecFact с параметром-значением N. В подпрограмме-функции проверяется условие N

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

Итак, при выполнении рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока не будет получено тривиальное решение поставленной задачи. В нашем примере решение при N=1 тривиально, т.е. ResFact=1. Затем осуществляется возврат на верхний уровень с последовательным вычислением значения функции ResFact.

Задание. Введите текст рассмотренной выше программы и запишите файл на диск под соответствующим именем, а затем откомпилируйте его. После того, как компиляция закончится успешно, задайте для просмотра в окне отладчика переменные N, F. Установите видимыми одновременно окна редактора с текстом программы и окно просмотра. Исполните программу в пошаговом режиме с заходом в функцию и пронаблюдайте за изменением значения переменной N при рекурсивных вызовах функции ResFact.

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

Определить две рекурсивных функции
В данном задании все операции над списками выполняются только с элементами верхнего уровня, хотя.

Определить две рекурсивных функции
Определить две рекурсивных функции. Распечатать результаты трассировки. Указать вид рекурсии.

Определить две рекурсивных функции
Пожалуйста, помогите определить две рекурсивных функции. Распечатать результаты трассировки.

Разработка рекурсивных алгоритмов для вычисления функции
Сразу к сути. Я должен сделать рекурсию функции y=x+3-e^-x. Что то y2 не выводит, ошибок нету! .

Написать две пользовательские функции, эквивалентные стандартной функции strlen
Написать программу, содержащую две пользовательские функции определения длины строки, эквивалентные.

Функции,как можно заменить две функции на одну?
4 Вариант: Два спортсмена одновременно начинают движение из одной точки с равномерным ускорением.

Один ПК, две сетевухи, две сетки, две папки для общего доступа
Здравствуйте! В одном здании имеем две разделенные физически локальные сети. Есть возможность.

Читайте также: