No Image

Что такое рекурсивная процедура

СОДЕРЖАНИЕ
2 просмотров
22 января 2020

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

Рекурсия


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

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

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

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

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.

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

Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике.

Содержание

В математике [ править | править код ]

В математике рекурсия имеет отношение к методу определения функций и числовых рядов: рекурсивно заданная функция определяет своё значение через обращение к себе самой с другими аргументами. При этом возможно два варианта:

  • Конечная рекурсивная функция. Она задаётся таким образом, чтобы для любого конечного аргумента за конечное число рекурсивных обращений привести к одному из отдельно определённых частных случаев, вычисляемых без рекурсии. Классический пример: рекурсивно-определённый факториал целого неотрицательного числа: 0\1,&n=0end>>"> n ! = < n ⋅ ( n − 1 ) ! , n >0 1 , n = 0 <displaystyle n!=<eginncdot (n-1)!,&n>0\1,&n=0end>>0\1,&n=0end"/> . Здесь каждое следующее рекурсивное обращение делается с аргументом, меньшим на единицу. Поскольку n, по определению, целое неотрицательное число, через n рекурсивных обращений вычисление функции гарантированно придёт к частному случаю 0 ! = 1 <displaystyle 0!=1>, на котором рекурсия прекратится. Таким образом, несмотря на рекурсивность определения, вычисление функции для любого аргумента из области определения окажется конечным.
  • Бесконечная рекурсивная функция. Она задаётся в виде обращения к самой себе во всех случаях (по крайней мере, для некоторых из аргументов). Подобным образом могут задаваться бесконечные ряды, бесконечные непрерывные дроби и так далее. Практическое вычисление точного значения здесь, естественно, невозможно, поскольку потребует бесконечного времени. Требуемый результат находится аналитическими методами. Тем не менее, если речь идёт не о получении абсолютно точного значения, а о вычислении заданного приближения искомого значения, то тут в некоторых случаях возможно прямое использование рекурсивного определения: вычисления по нему ведутся до тех пор, пока необходимая точность не будет достигнута. Примером может служить разложение в непрерывную дробьчисла e:

e = 2 + 2 2 + 3 3 + 4 4 + … = 2 + f ( n ) <displaystyle e=2+<cfrac <2><2+<cfrac <3><3+<cfrac <4><4+ldots >>>>>>;=2+f(n)>, где f ( n ) = n n + f ( n + 1 ) <displaystyle f(n)=<cfrac >>Прямой расчёт по приведённой формуле вызовет бесконечную рекурсию, но можно доказать, что значение f(n) при возрастании n стремится к единице (поэтому, несмотря на бесконечность ряда, значение числа Эйлера конечно). Для приближённого вычисления значения e достаточно искусственно ограничить глубину рекурсии некоторым наперёд заданным числом и по достижении его использовать вместо f ( n ) <displaystyle f(n)>единицу.

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

Читайте также:  Установка игр на ноутбук

С рекурсией тесно связана математическая индукция: она является естественным способом доказательства свойств функций на натуральных числах, рекурсивно заданных через свои меньшие значения.

В математике отдельно рассматривается класс так называемых «примитивно рекурсивных» функций. Определение примитивно рекурсивной функции также рекурсивно, оно задаёт набор примитивных функций и набор правил; функция является примитивно рекурсивной, если она может быть представлена как комбинация примитивно рекурсивных функций, образованная по этим правилам.

Примеры рекурсии в математике:

  • Метод Гаусса — Жордана для решения систем линейных алгебраических уравнений является рекурсивным.
  • Уже упоминавшийся факториал целого неотрицательного числа.
  • Числа Фибоначчи определяются с помощью рекуррентного соотношения: Первое и второе числа Фибоначчи равны 1 Для 2>"> n > 2 <displaystyle n>2>2"/> , n <displaystyle n>-e число Фибоначчи равно сумме ( n − 1 ) <displaystyle (n-1)>-го и ( n − 2 ) <displaystyle (n-2)>-го чисел Фибоначчи
  • Практически все геометрические фракталы задаются в форме бесконечной рекурсии (например, треугольник Серпинского).
  • Стандартный пример вычислимой рекурсивной функции, не являющейся примитивно рекурсивной — функция Аккермана: для неотрицательных целых чисел m <displaystyle m>и n <displaystyle n>следующим образом:

0,;n=0;\A(m-1,;A(m,;n-1)),&m>0,;n>0.end>>"> A ( m , n ) = < n + 1 , m = 0 ; A ( m − 1 , 1 ) , m >0 , n = 0 ; A ( m − 1 , A ( m , n − 1 ) ) , m > 0 , n > 0. <displaystyle A(m,;n)=<eginn+1,&m=0;\A(m-1,;1),&m>0,;n=0;\A(m-1,;A(m,;n-1)),&m>0,;n>0.end>>0,;n=0;\A(m-1,;A(m,;n-1)),&m>0,;n>0.end"/>

В программировании [ править | править код ]

Функции [ править | править код ]

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A <displaystyle A> вызывает функцию B <displaystyle B> , а функция B <displaystyle B> — функцию A <displaystyle A> . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Рекурсивная программа позволяет описать повторяющееся или даже потенциально бесконечное вычисление, причём без явных повторений частей программы и использования циклов.

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

Помимо функций, выполняющих один рекурсивный вызов в каждой рекурсивной ветви, бывают случаи «параллельной рекурсии», когда на одной рекурсивной ветви делается два или более рекурсивных вызова. Параллельная рекурсия типична при обработке сложных структур данных, таких как деревья. Простейший пример параллельно-рекурсивной функции — вычисление ряда Фибоначчи, где для получения значения n-го члена необходимо вычислить (n-1)-й и (n-2)-й.

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

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

Читайте также:  Что означает кэш процессора

Имеется специальный тип рекурсии, называемый «хвостовой рекурсией» (структура рекурсивного алгоритма такова, что рекурсивный вызов является последней выполняемой операцией в функции, а его результат непосредственно возвращается в качестве результата функции). Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.

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

Доказательство корректности программ [ править | править код ]

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

  1. Корректность рекурсивного обращения. Доказывается, что результат, вычисляемый в любой рекурсивной ветви функции, будет верным при условии, что параметры функции заданы корректно и соответствующие рекурсивные вызовы вернут верный результат.
  2. Корректность всех терминальных ветвей. Доказывается, что все терминальные ветви возвращают верные значения. Как правило, это доказательство тривиально, так как терминальные ветви обычно никаких вычислений не содержат.
  3. Достижимость терминальной ветви для любого корректного набора параметров после конечного числа рекурсивных вызовов. Доказывается, что изменение параметров вызова функции, которое производится при рекурсивном обращении, через конечное число рекурсивных вызовов приведёт к одному из наборов параметров, для которых существует терминальная ветвь.

Из суммы первого и второго утверждений следует, что в случае достижения терминальной ветви (а это значит — во всех случаях, когда вычисление функции окажется конечным) функция вернёт правильный результат. Третье положение доказывает, что конечным будет любое вычисление. Следовательно, любой вызов функции с корректными параметрами вернёт правильный результат (с очевидной «технической» оговоркой — если глубина рекурсии не окажется настолько большой, что вызовет переполнение памяти).

Данные [ править | править код ]

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

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

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

В физике [ править | править код ]

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

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

Читайте также:  Усилитель для наушников самодельный

В лингвистике [ править | править код ]

В лингвистике рекурсией называют способность языка порождать вложенные предложения и конструкции. Базовое предложение «кошка съела мышь» может быть за счёт рекурсии расширено как «Ваня догадался, что кошка съела мышь», далее как «Катя знает, что Ваня догадался, что кошка съела мышь» и так далее. Рекурсия считается одной из лингвистических универсалий, то есть свойственна любому естественному языку. Однако в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии — пираха, которое отмечает лингвист Дэниел Эверетт [1] .

В культуре [ править | править код ]

  • Большая часть шуток о рекурсии касается бесконечной рекурсии, в которой нет условия выхода, например, известно высказывание: «чтобы понять рекурсию, нужно сначала понять рекурсию» .
  • Весьма популярна шутка о рекурсии, напоминающая словарную статью:
  • Тема рекурсии присутствует во многих рассказах и очерках аргентинского писателя Хорхе Луиса Борхеса.
  • Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:
  • рассказ из «Кибериады» о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей);
  • рассказ про Ийона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого», в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки»:

Нашёл следующие краткие сведения:
«СЕПУЛЬКИ — важный элемент цивилизации ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКАРИИ».
Я последовал этому совету и прочёл:
«СЕПУЛЬКАРИИ — устройства для сепуления (см.)».
Я поискал «Сепуление»; там значилось:
«СЕПУЛЕНИЕ — занятие ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКИ».

Сравнительный анализ возможностей процедуры и функции. Возможности преобразования процедуры в функцию и наоборот

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

Синтаксис заголовка процедуры: PROCEDURE [( )];

Функция предназначена для вычисления какого-либо одного значения и используется в выражениях аналогично стандартным функциям.

Синтаксис заголовка функции: FUNCTION [( )]: ;

Размещение:

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

Отличие описания функции от процедуры:

· результатом обращения к функции может быть одно единственное значение;

· идентификатор результата не указывается в списке формальных параметров;

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

· после списка формальных параметров задается тип результата;

· после обращения к функции управление передается на выполнение следующей операции данного выражения (в соответствии с приоритетом).

Преобразование процедуры в функцию:

Только если на выходе процедуры 1 результат

PROCEDURE P1 (A,B,C : Integer; VAR Sum : Integer)

Преобразование функции в процедуру:

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

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

Рассмотрим пример. Вычислить значение F=M! Рекурсивное

определение значение факториала можно записать следующим образом:

при М> 1 F= M!= M*(M-1)!, т.е. М! определяется через (М-1)!

Комментировать
2 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
Adblock detector