Рекурсия
В языке "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.
Упражнение 4-7
-------------- Приспособьте идеи, использованные в PRINTD для рекурсив- ного написания ITOA; т.е. Преобразуйте целое в строку с по- мощью рекурсивной процедуры.
Упражнение 4-8
-------------- Напишите рекурсивный вариант функции REVERSE(S), которая располагает в обратном порядке строку S.
