Рекурсия

В языке "C" функции могут использоваться рекурсивно; это

означает, что функция может прямо или косвенно обращаться к

себе самой. Традиционным примером является печать числа в

виде строки символов. как мы уже ранее отмечали, цифры гене-

рируются не в том порядке: цифры младших разрядов появляются

раньше цифр из старших разрядов, но печататься они должны в

обратном порядке.

Эту проблему можно решить двумя способами. Первый спо-

соб, которым мы воспользовались в главе 3 в функции ITOA,

заключается в запоминании цифр в некотором массиве по мере

их поступления и последующем их печатании в обратном поряд-

ке. Первый вариант функции PRINTD следует этой схеме.

PRINTD(N) /* PRINT N IN DECIMAL */

INT N;

{

CHAR S[10];

INT I;

IF (N < 0) {

PUTCHAR('-');

N = -N;

}

I = 0;

DO {

S[I++] = N % 10 + '0'; /* GET NEXT CHAR */

} WHILE ((N /= 10) > 0); /* DISCARD IT */

WHILE (--I >= 0)

PUTCHAR(S[I]);

}

Альтернативой этому способу является рекурсивное реше-

ние, когда при каждом вызове функция PRINTD сначала снова

обращается к себе, чтобы скопировать лидирующие цифры, а за-

тем печатает последнюю цифру.

PRINTD(N) /* PRINT N IN DECIMAL (RECURSIVE)*/

INT N;

(

INT I;

IF (N < 0) {

PUTCHAR('-');

N = -N;

}

IF ((I = N/10)!= 0)

PRINTD(I);

PUTCHAR(N % 10 + '0');

)

Когда функция вызывает себя рекурсивно, при каждом обра-

щении образуется новый набор всех автоматических переменных,

совершенно не зависящий от предыдущего набора. Таким обра-

зом, в PRINTD(123) первая функция PRINTD имеет N = 123. Она

передает 12 второй PRINTD, а когда та возвращает управление

ей, печатает 3. Точно так же вторая PRINTD передает 1

третьей (которая эту единицу печатает), а затем печатает 2.

Рекурсия обычно не дает никакой экономиии памяти, пос-

кольку приходится где-то создавать стек для обрабатываемых

значений. Не приводит она и к созданию более быстрых прог-

рамм. Но рекурсивные программы более компактны, и они зачас-

тую становятся более легкими для понимания и написания. Ре-

курсия особенно удобна при работе с рекурсивно определяемыми

структурами данных, например, с деревьями; хороший пример

будет приведен в главе 6.