57. Рекурсия в языке Си.
В языке Си функции могут вызывать сами себя, т.е. обладать свойством рекурсивности. Рекурсивная функция обязательно должна содержать в себе условие окончания рекурсивности, чтобы не вызвать зацикливания программы. При каждом рекурсивном вызове создается новое множество локальных переменных. Т.о. переменные, расположенные вне вызываемой функции, не изменяются.
Пример. Составить рекурсивную функцию, вычисляющую факториал числа n следующим образом: n!= 1 , если n<= 1 и n!= ( n -1 )! · n, если n > 1
long fact( int n)
else return (n * fact ( n -1 )); // функция fact вызывает саму себя
Таким образом, последовательно вызываются функции f(n), f(n-1),f(n-2)…f(1).
Достоинством рекурсий является компактная запись, а недостатком – расход времени и памяти на повторные вызовы функции и передачу ей копий параметров.
58. Указатель на функцию в языке Си.
Возможны только две операции с функциями: вызов и взятие адреса. Указатель, полученный с помощью последней операции, можно впоследствии использовать для вызова функции. Например:
Для вызова функции с помощью указателя (efct в нашем примере) надо вначале применить операцию косвенности к указателю — *efct. Поскольку приоритет операции вызова () выше, чем приоритет косвенности *, нельзя писать просто *efct(«error»). Это будет означать *(efct(«error»)), что является ошибкой. По той же причине скобки нужны и при описании указателя на функцию. Однако, писать просто efct(«error») можно, т.к. транслятор понимает, что efct является указателем на функцию, и создает команды, делающие вызов нужной функции.
Отметим, что формальные параметры в указателях на функцию описываются так же, как и в обычных функциях. При присваивании указателю на функцию требуется точное соответствие типа функции и типа присваиваемого значения.
59. Классы хранения переменных языка Си.
В языке C все переменные и функции должны быть объявлены до их использования. Объявление переменной устанавливает соответствие имени и атрибутов переменной, вызывает выделение памяти для хранения ее значения. Место размещения переменной в памяти программы задается с помощью класса памяти (класса хранения) переменной. В зависимости от места размещения переменной в памяти определяется время жизни и область видимости переменной. Класс памяти задается спецификатором класса памяти.
В языке C имеется 4 класса памяти:
— extern (внешние переменные);
— auto (автоматические переменные);
— register (регистровые переменные);
— static (статические переменные);
Время жизни – это интервал времени выполнения программы, в течение которого программный объект (переменная или функция) существует, что определяется фактом выделения памяти. Время жизни переменной может быть локальным или глобальным. Переменная с глобальным временем жизни имеет выделенную память и определенное значение на протяжении всего времени выполнения программы, начиная с момента объявления этой переменной. Переменная с локальным временем жизни имеет выделенную память и определенное значение только во время выполнения блока, в котором эта переменная объявлена. При каждом входе в блок локальной переменной выделяется новая память, которая освобождается при выходе из блока.
Область видимости – это часть текста программы, в которой может быть использован данный объект. Объект считается видимым в блоке или в исходном файле, если в этом блоке или файле известны имя и тип объекта. Объект может быть видимым в пределах блока, текущего файла или во всех файлах, образующих программу.
Время жизни и область видимости объекта зависят от того, в каком месте объявлен объект. Если объект объявлен на внутреннем уровне, т. е. внутри некоторого блока, то по умолчанию он имеет локальное время жизни и локальную область видимости, т. е. он существует, пока выполняется блок, и видим в этом блоке и во всех внутренних блоках (локальная переменная). Если объект объявлен на внешнем уровне, т. е. вне всех блоков, он имеет глобальное время жизни и глобальную видимость. Такой объект существует до завершения программы и видим от точки его объявления до конца данного исходного файла (глобальная переменная).
Изменить время жизни переменной и область ее видимости можно, если указать для нее класс памяти. Все переменные, которые использовались до сих пор, были известны только содержащим их функциям. В C имеются возможности сделать ряд переменных известными сразу нескольким функциям и быстро обработать переменные путем помещения их значений в регистры и т. д. Эти и другие возможности реализуются при помощи присваивания переменным класса памяти.
Служебное слово, определяющее класс памяти, ставится в описаниях переменных перед служебным словом, задающим тип переменных:
Как работает рекурсия в си
Отдельно остановимся на рекурсивных функциях. Рекурсивная функция представляет такую конструкцию, при которой функция вызывает саму себя.
Рекурсивная функция факториала
Возьмем, к примеру, вычисление факториала, которое использует формулу n! = 1 * 2 * … * n . То есть по сути для нахождения факториала числа мы перемножаем все числа до этого числа. Например, факториал числа 4 равен 24 = 1 * 2 * 3 * 4 , а факторил числа 5 равен 120 = 1 * 2 * 3 * 4 * 5 .
Определим метод для нахождения факториала:
При создании рекурсивной функции в ней обязательно должен быть некоторый базовый вариант , с которого начинается вычисление функции. В случае с факториалом это факториал числа 1, который равен 1. Факториалы всех остальных положительных чисел будет начинаться с вычисления факториала числа 1, который равен 1.
На уровне языка программирования для возвращения базового варианта применяется оператор return :
То есть, если вводимое число равно 1, то возвращается 1
Другая особенность рекурсивных функций: все рекурсивные вызовы должны обращаться к подфункциям, которые в конце концов сходятся к базовому варианту:
Так, при передаче в функцию числа, которое не равно 1, при дальнейших рекурсивных вызовах подфункций в них будет передаваться каждый раз число, меньшее на единицу. И в конце концов мы дойдем до ситуации, когда число будет равно 1, и будет использован базовый вариант. Это так называемый рекурсивный спуск.
Используем эту функцию:
Рассмотрим поэтапно, что будет в случае вызова factorial(4) .
Сначала идет проверка, равно ли число единице:
Но вначале n равно 4, поэтому это условие ложно, и соответственно выполняется код
То есть фактически мы имеем:
Далее выполняется выражение:
Опять же n не равно 1, поэтому выполняется код
То есть фактически:
Далее выполняется выражение:
Опять же n не равно 1, поэтому выполняется код
То есть фактически:
Далее выполняется выражение:
Теперь n равно 1, поэтому выполняется код
И возвращается 1.
В итоге выражение
В реальности выливается в
Рекурсивная функция Фибоначчи
Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фибоначчи. n-й член последовательности Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. То есть последовательность Фибоначчи будет выглядеть так 0 (0-й член), 1 (1-й член), 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . Для определения чисел этой последовательности определим следующий метод:
Здесь базовый вариант выглядит следующий образом:
То есть, если мы ищем нулевой или первый элемент последовательности, то возвращается это же число — 0 или 1. Иначе возвращается результат выражения fibonachi(n — 1) + fibonachi(n — 2);
Рекурсии и циклы
Это простейшие пример рекурсивных функций, которые призваны дать понимание работы рекурсии. В то же время для обоих функций вместо рекурсий можно использовать циклические конструкции. И, как правило, альтернативы на основе циклов работают быстрее и более эффективны, чем рекурсия. Например, вычисление чисел Фибоначчи с помощью циклов:
В то же время в некоторых ситуациях рекурсия предоставляет элегантное решение, например, при обходе различных древовидных представлений, к примеру, дерева каталогов и файлов.
Рекурсия
Рекурсия — состоит в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса. Это ситуация, когда объект является частью самого себя.
Процедура или функция может содержать вызов других процедур или функций. В том числе процедура может вызвать саму себя. Компьютер лишь последовательно выполняет команды и, если встречается вызов процедуры, просто начинает выполнять эту процедуру. Без разницы, какая процедура дала команду это делать.
Процедура func() вызывается с параметром 3. В ней содержится вызов процедуры func() с параметром 2. Предыдущий вызов еще не завершился, поэтому создается еще одна процедура и до окончания ее работы func(3) свою работу приостанавливает. Процесс вызова заканчивается, когда параметр равен 0. В этот момент одновременно выполняются 4 экземпляра процедуры.
Количество одновременно выполняемых процедур называют глубиной рекурсии .
Последняя вызванная процедура func(0) выведет число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала: func(1) и выводится число 1. И так далее пока не завершатся все процедуры. 
Важным и обязательным моментом в формировании рекурсивной процедуры является базис рекурсии. Базис рекурсии определяет условие выхода из рекурсии. Как правило, в качестве базиса записывается некий простейший случай, при котором ответ получается сразу, без использования рекурсии.
Существует такое понятие как шаг рекурсии или рекурсивный вызов . В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.
Сложная рекурсия
Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией . При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать описание функции B до ее использования.
Пример : вычислить значение выражения 
Результат выполнения 
Префиксная и постфиксная форма записи
Если процедура вызывает сама себя, то, по сути, это приводит к повторному выполнению содержащихся в ней инструкций, что аналогично работе цикла. При этом различают префиксную и постфиксную формы записи.
Как работает рекурсия в си
В Си допускается рекурсивное обращение к функциям, т.е. функция может прямо или косвенно обращаться сама к себе. Рассмотрим печать числа в виде строки символов. Как мы упоминали ранее, цифры генерируются в обратном порядке — младшие цифры получаются раньше старших, а печататься они должны в правильной последовательности.
Проблему можно решить двумя способами. Первый — запомнить цифры в некотором массиве в том порядке, как они получались, а затем напечатать их в обратном порядке; так это и было сделано в функции itoa , рассмотренной в параграфе 3.6. Второй способ — воспользоваться рекурсией, при которой printd сначала вызывает себя, чтобы напечатать все старшие цифры, а затем печатает последнюю младшую цифру. Эта программа, как и предыдущий ее вариант, при обработке самого большого по модулю отрицательного числа работает неправильно.
Когда функция рекурсивно обращается сама к себе, при каждом обращении она получает новый полный набор автоматических переменных, независимых от предыдущих наборов. Так, в обращении printd(123) при первом вызове аргумент n = 123, при втором — printd получает аргумент 12, при третьем вызове — значение 1. Функция printd на третьем уровне вызова печатает 1 и возвращается на второй уровень, после чего печатает цифру 2 и возвращается на первый уровень. Здесь она печатает 3 и заканчивает работу.
Другой хороший пример рекурсии — это быстрая сортировка, предложенная Ч.А.Р. Хоаром в 1962 г. Для заданного массива выбирается один элемент, который разбивает остальные элементы на два подмножества — те, что меньше, и те, что не меньше него. Та же процедура рекурсивно применяется и к двум полученным подмножествам. Если в подмножестве менее двух элементов, то сортировать нечего и рекурсия завершается.
Наша версия быстрой сортировки, разумеется, не самая быстрая среди всех возможных, но зато одна из самых простых. В качестве делящего элемента мы используем серединный элемент.
В нашей программе операция перестановки оформлена в виде отдельной функции swap , поскольку она встречается в qsort трижды.
В стандартной библиотеке есть функция qsort , позволяющая сортировать объекты любого типа.
Рекурсивная программа не обеспечивает ни экономии памяти, поскольку требуется где-то поддерживать стек значений, подлежащих обработке, ни быстродействия; но по сравнению со своим нерекурсивным эквивалентом она часто короче и намного легче для написания и понимания. Такого рода программы особенно удобны для обработки рекурсивно определяемых структур данных вроде деревьев; с хорошим примером на эту тему вы познакомитесь в параграфе 6.5.