ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. Рекурсивные функции (лат

 

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

Рекурсивный алгоритм – это алгоритм, решающий задачу путем решения одного или нескольких более простых вариантов той же задачи [2]. Функция называется рекурсивной, если в ее определении содержится вызов этой же функции [3]. Рекурсивная функция может вызывать саму се6я или непосредственно, или косвенно через другую функцию [4]. Рекурсии целесообразно применять в задачах, которые можно разбить на множество меньших подобных задач [5]. Рекурсия в программировании может быть определена как сведение задачи к такой же задаче, но манипулирующей более простыми данными.

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

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

Наличие в задаче рекуррентного соотношения позволяет использовать рекурсию. Например, арифметическая прогрессия – последовательность чисел, в которой разность между последующими и предыдущими членами остается неизменной и называется разностью прогрессии [1]. То есть каждый следующий член прогрессии равен предыдущему, увеличенному на разность прогрессии.

Различают прямую и косвенную рекурсию. Прямой (непосредственной) рекурсией является вызов функции внутри ее тела, косвенной – рекурсия, осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций [6]. Все функции, входящие в цепочку, тоже считаются рекурсивными.

В рекурсии простейшей формы рекурсивный вызов расположен в конце функции, непосредственно перед оператором возврата из функции (или возвращаемого значения). Такая рекурсия называется хвостовой или концевой и является простейшей формой рекурсии, поскольку действует подобно циклу [7]. Если в программе имеется хвостовая рекурсия, то ее лучше преобразовать к итерации.

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

Когда функция вызывает сама себя (когда имеем дело с рекурсивной функцией), новый набор локальных переменных и параметров размещается в памяти в стеке, а код функции выполняется с самого своего начала, причем используются именно эти новые переменные. При рекурсивном вызове функции новая копия ее кода не создается. Новыми являются только значения, которые использует данная функция. При каждом возвращении из рекурсивного вызова старые локальные переменные и параметры извлекаются из стека, и сразу за рекурсивным вызовом возобновляется работа функции с «внутренней» точки ее вызова [8].

Общая схема определения рекурсивной функции

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

· Существует также условие, которое будет удовлетворено и при котором функция выполняет свою задачу без рекурсивных вызовов. Оно называется базовым или условием останова [2; 4–6].

Рассмотрим некоторые определения, относящиеся к рекурсии. Максимальное число рекурсивных вызовов без возвратов, которые происходят во время выполнения программы, называется глубиной рекурсии. Число рекурсивных вызовов в каждый конкретный момент времени, – это текущий уровень рекурсии. В практических приложениях важно убедиться, что максимальная глубина рекурсий не только конечна, но и достаточно мала [11].

Существуют три разные формы рекурсивных программ:

1) форма с выполнением действий до рекурсивного вызова (на рекурсивном спуске).

2) фома с выполнением действий после рекурсивного вызова (на рекурсивном возврате);

3) форма с выполнением действий как до, так и после рекурсивного вызова (как на рекурсивном спуске, так и на рекурсивном возврате).

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

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

Главное при оформлении рекурсивной функции – это правильное задание условия выхода из рекурсивных вызовов. Если при зацикливании программы на операторе цикла компьютер может выполнять его, не реагируя на любые действия пользователя, то при зацикливании из-за неправильного оформления рекурсивной функции неизбежно происходит аварийный останов, когда будет исчерпан объем оперативной памяти, которая выделяется при каждом рекурсивном вызове. Следует всегда помнить, что даже при правильном оформлении рекурсивной функции необходимо учитывать объем вычислительной работы.Так, расчет факториала целого положительного числа – трудоемкая операция. В математической постановке задачи нет ничего сложного, но при программировании этого процесса для различных систем и компьютеров имеются свои ограничения, например трудности рекурсивного вычисления факториала.

Для некоторых задач рекурсивные функции вполне оправданы. В частности, динамические информационные структуры включают рекурсивность в само определение обрабатываемых данных. Именно для таких данных применение рекурсивных алгоритмов не имеет конкуренции со стороны итерационных методов [6].

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

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

int fact (int n) { if (n == 0) return 1; else return n * fact (n - 1); }

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

int fact (int n) { return fact_w (1,n); }

Вспомогательная функция fact_w() будет содержать хвостовую рекурсию. Ее программный код выглядет так:

int fact_w (int r, int n) { if (n == 0) return r; else return fact(r*n,n-1); }

В функции fact_w() хвостовая рекурсия присутствует в силу рекурсивного обращения только к самой функции в операторе return.

Обратимся к известному положению об исключении хвостовой рекурсии: если функция f (x) содержит в конце рекурсивный вызов в виде return f (y), то рекурсию можно исключить путем присваивания x = y, и перехода goto на начало функции [14]. Программный код исключения хвостовой рекурсии будет следующим:

int fact_w (int r, int n) { met: if (n == 0) return r; else { r = r*n; n = n-1; goto met; } }

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

int fact_w (int r, int n) { if (n!= 0) { r = r*n; n = n-1; } return r; }

В качестве окончательной оптимизации можно исключить и вспомогательную функцию fact_w(), выполнив подстановку тела функции в точку ее вызова (inlining). В итоге получим следующий программный код функции, вычисляющей факториал числа:

/* * Оптимизация функции * вычисления факториала числа */ int fact (int n) { int r = 1; if (n!= 0) { r = r*n; n = n-1; } return r; }

В приведенной функции нет ни рекурсивных вызовов, ни оператора goto.

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

Каждая функция в программе на языке С находится на одном уровне с остальными функциями, составляющими программный проект, может вызвать любую другую функцию или быть вызванной. Отсюда функция main() может вызывать сама себя в рамках некоторой рекурсии или быть вызвана из других функций, хотя подобное встречается достаточно редко [7]. Следует иметь в виду, что когда программа составляется из нескольких функций, ее выполнение начинается с первого оператора функции main().