Что такое рекурсия в паскале

Что такое рекурсия в паскале

Понятие, которое частично определяется, через само себя, называется рекурсивным.

Любое рекурсивное определение состоит из двух частей. Одна определяет понятие через него же. Другая – через иные понятия. Рекурсивный алгоритм – это алгоритм, который при вычислении обращается сам к себе. Например: вычисление функции f(n) может потребовать вычислениеf(n-1) и еще каких-то операций. Т.е. часть алгоритма вычисления функции, есть вычисление это же функции с другими аргументами. Рекурсивные алгоритмы записываются с помощью рекурсивных процедур. Процедура называется рекурсивной, если она обращается сама к себе, прямо или косвенно.

Пример: Рекурсивное вычисление факториала.

If n=1 then factorial:=1

Else factorial:= factorial(n-1)*n;

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

Пример: Возведение действительного числа в целую степень.

Procedure power(x:real;n:integer;var y:real);

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

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

Вопрос 39: Представление чисел с плавающей точкой и операции с ними.

С помощью чисел с плавающей точкой представляются действительные числа.

Если в теле функции встречается вызов самой этой функции, то мы имеем дело с так называемой рекурсией. В языке программирования 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. Первая процедура завершается и передает управление в основную ветку программы.
Читайте также:  Инвертор 12 220 из бесперебойника своими руками

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

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

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

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

Справочник

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

Ссылка на основную публикацию
Adblock detector