Рекурсивные функции. Пример

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

Задачу можно решать двумя способами. Первый - сохранять цифры по мере их формирования в массиве и печатать их оттуда в нужном порядке. При этом необходимо заранее предусмотреть достаточно большой массив. Однако, возможен и рекурсивный способ решения, - при каждом обращении к printd() она сначала обращается к себе, чтобы напечатать начальные цифры, а затем печатает замыкающую цифру.

Пример

printd (int n) /* десятичная печать n (рекурсивная) */

{

int i;

if (n < 0)

{ putchar ('-');

n = -n;

}

if ((i = n/10) != 0)

printd(i);

putchar(n % 10 + '0');

}

При рекурсивном обращении функции к самой себе при каждом вызове создается новое множество всех автоматических переменных, и оно совершен­но не зависит от предыдущего. Таким образом, при обращении printd(123) в первой активации функции n = 123. Во вторую printd передается 12, а после возврата из нее печатается 3. Аналогично вторая printd передает третьей 1 (та печатает ее), а затем сама печатает 2.

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

Вопросы для самоконтроля

• Тип функции по умолчанию?
• Может ли функция иметь пустое тело?
• Как читаются следующие спецификации функций: char f1(), int f2(int,…), double f3(void)?
• Для каких целей может использоваться указание класса памяти static?
• Как установить указатель на 1-й аргумент в списке неописанных аргументов функции с нефиксированным числом параметров?
• Как контролируется действительное число аргументов при вызове функции с нефиксированным числом параметров?
• Выделяется ли память в случае декларации переменной с указанием класса памяти extern?
• Предусмотрена ли автоматическая защита памяти для рекурсивных функций в случае переполнения стека вычислений?