Рекурсия
В языке "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.
