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

     Рассмотрим пример использования функций. Первоначально создается массив A со
значениями, указанными на рис.5. Первый элемент массива равен значению главного
корня дерева, остальные расположены в случайном порядке. Первоначально создается
корень, далее расставляются остальные значения согласно правилу: все ключи левого
поддерева меньше ключа текущего узла, а все ключи правого поддерева - больше. Далее
ключи дерева выводятся на экран. В заголовочном файле function.h приведен исходный
код всех вышеперечисленных функций. В результате выполнения программы на экран
будут выведены значения:
Main Root 10
Left Root    6
Left Tree    1 8
Right Root 25
Right Tree 20 21 30

int main()
{
       int A[] = {10, 25, 20, 6, 21, 8, 1, 30};
       X *root = FirstElement(A[0]);
       for (int i = 1; i<8; i++)
                SearchAndInsertElement(root, A[i]);
       PrintTree(root);
       return 0;
}

     § 2.10. Рекурсия

      Функция называется рекурсивной, если во время ее обработки возникает ее по-
вторный вызов, либо непосредственно, либо косвенно, путем цепочки вызовов других
функций. Таким образом рекурсия - это такой способ организации процесса вычисле-
ний, при котором функция в ходе выполнения ее операторов обращается сама к себе,
прямо или косвенно. Рекурсия бывает линейной, когда определение объекта включает в
себя единственный аналогичный объект, или ветвящейся, когда таких включаемых объ-
ектов много.
      Рекурсивная форма организации алгоритма обычно дает более компактный текст
программы, чем другие способы решения этой же задачи, но требует дополнительных
затрат оперативной памяти для размещения данных и времени для организации рекур-
сивных вызовов функции. Таким образом, благодаря рекурсии уменьшается исходный
код программы, но при этом нет выигрыша ни в использовании памяти, ни в быстродей-
ствии. Рассмотрим трудоемкость рекурсивных алгоритмов - зависимость времени их вы-
полнения от размерности входных данных. В рекурсивных функциях размерность вход-
ных данных определяет глубину рекурсии. Если имеется ветвящаяся рекурсия - цикл
из m повторений, то при глубине рекурсии N общее количество рекурсивных вызовов будет
порядка mN, поскольку с каждым шагом рекурсии оно увеличивается в m раз. Таким обра-
зом трудоемкость рекурсивных алгоритмов значительно превышает трудоемкость рассмот-
ренных ранее алгоритмов сортировки и поиска.
      При выполнении правильно организованной рекурсивной функции осуществляется
ее многократный последовательный вызов. При этом система:
      1) сохраняет в стеке значения всех локальных переменных функции и ее парамет-
ры для всех предыдущих вызовов;
      2) выделяет место в оперативной памяти для локальных переменных очередного
вызова функции.

                                             75