Программирование на языке высокого уровня. Марапулец Ю.В. - 76 стр.

      Для внутренних переменных, объявленных с классом памяти extern или static, но-
вые области памяти при каждом рекурсивном вызове не выделяются, выделенная им па-
мять сохраняется в течение всего времени выполнения программы. Сохраненные в стеке
значения могут использоваться после получения результата от последующего вызова
функции. Вызов рекурсивной функции производится до тех пор, пока не будет получено
тривиальное решение задачи, т. е. будет получен результат в виде конкретного значе-
ния без вызова рекурсивной функции. Правильно организованная рекурсивная функция
обязательно должна иметь этот вариант решения для завершения рекурсивных вызовов.
По завершении рекурсивных вызовов функции и после получения результатов ее вы-
полнения управление следующему за рекурсивной функцией оператору.
      Компилятор не ограничивает количество рекурсивных вызовов одной функции,
при этом для каждого вызова функции в памяти выделяется место для формальных па-
раметров и локальных переменных auto и register. Перечисленные переменные образу-
ют группу (фрейм стека). Стек «помнит историю» рекурсивных вызовов в виде последо-
вательности (цепочки) таких фреймов. Программа в каждый конкретный момент рабо-
тает с последним вызовом и с последним фреймом. При завершении рекурсии программа
возвращается к предыдущей версии рекурсивной функции и к предыдущему фрейму в
стеке. Некоторые операционные системы накладывают ограничения на количество вы-
зовов, так как это может вызвать переполнение стека.
      Принцип программирования рекурсивных функций имеет много общего с методом
математической индукции - рекурсивная функция представляет собой переход из n-го в
n+1-e состояние некоторого процесса. Если этот переход корректен, то есть соблюде-
ние некоторых условий на входе функции приводит к их соблюдению на выходе (в ре-
курсивном вызове), то эти условия будут соблюдаться во всей цепочке состояний. Таким
образом, самое важное в определении рекурсии - выделить те условия (инварианты), ко-
торые соблюдаются (сохраняются) во всех точках процесса, и обеспечить их справедли-
вость от входа в рекурсивную функцию до ее рекурсивного вызова. При этом не реко-
мендуется рассматривать следующий или предыдущий шаг рекурсии.
      С помощью рекурсии можно решать различные задачи. В некоторых случаях (вы-
числение факториала; определение сумм и произведений членов ряда, вычисляемых до
получения заданной точности вычислений; формирование и использование рекурсивно-
определяемых связанных структур данных, например очередей, списков, деревьев) ре-
курсивное построение алгоритма является наиболее естественным и экономичным путем
решения задачи. Рассмотрим примеры использования рекурсивных функций [3].
      1. Функция, которая выводит некоторую фразу несколько раз.
      Принцип работы функции PrintString() состоит в том, что при k > 0 она выводит
фразу из строки str и вызывает функцию PrintString() для значения фактического пара-
метра (k - 1). Так например, для k = 5, при втором вызове PrintString() фактический па-
раметр k = 4, при следующем k = 3 и т. д. до k = 0. При вызове функции с k = 0 вывод не
производится и последовательно осуществляется возврат обратно во все вызванные
функции PrintString() и выход в главную функцию.

void PrintString( char * str, int k )
{
       if ( k > 0 )          //проверка на тривиальность решения
       {
                printf ( "%s", str);         // вывод текста
                PrintString ( str, k - 1 ); // рекурсивный вызов функции
       }
}



                                              76