Задачи на рекурсию в паскале

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

В приведенном примере процедура rever выводит цифры, переданного ей в качестве фактического параметра числа, в обратном порядке. Т.е. если мы передаем число 35, то процедура выведет на экран число 53. Рассмотрим, как она это делает:

1. Мы передаем число 3096.
2. Процедура rever выводит на экран остаток от деления на 10. Это число 6.
3. Переход на новую строку не происходит, т.к. используется write.
4. Проверяется условие того, что 3096 при деление нацело на 10 больше нуля.
5. Вызывается rever с фактическим параметром, равным 309.
6. Вторая запущенная процедура выводит на экран цифру 9 и запускает третью процедуру с параметром 30.
7. Третья процедура выводит 0 и вызывает четвертый rever с 3 в качестве параметра.
8. Четвертая процедура выводит 3 на экран и ничего больше не вызывает, т.к. условие (3 div 10) <> 0 ложно.
9. Четвертая процедура завершается и передает управление третьей.
10. Третья процедура завершается и передает управление второй.
11. Вторая процедура завершается и передает управление первой.
12. Первая процедура завершается и передает управление в основную ветку программы.

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

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

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

Рекурсия

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

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

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

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

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:

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

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

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

• Скачено бесплатно: 6962
• Куплено: 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)

Справочник

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