1. Основные понятия алгоритмизации и программирования

6. Итерация и рекурсия

6.1. Понятие итеративного процесса

Итеративный процесс можно определить как процесс вычислений, основанный на повторении последовательности операций, при котором на каждом шаге повторения используется результат предыдущего шага. Примерами итеративных алгоритмов могут служить алгоритмы вычисления факториала натурального числа, последовательности чисел Фибоначчи, вычисление суммы членов последовательности с заданным числом слагаемых и т.д. Итеративные процессы программируются обычно с помощью циклических конструкций.
Пример. Вычисление факториала числа n.
int factor (int n)
{
int f = 1;
for (int i = 2; i <= n; i++) f *= i;
return k;
}

6.2. Понятие рекурсии

В то же время повторение последовательности действий можно осуществить и другим методом, основанным на принципе возможности явного включения в конструкции языка программирования конструкции того же вида. В частности, в языке программирования C# всякая функция может вызывать сама себя. Такой вызов называется рекурсией. Функция, вызывающая саму себя, называется рекурсивной.
Вообще алгоритм решения задачи называется рекурсивным, если он выражается в терминах решения более простой версии той же задачи и, кроме того, в нем предусмотрено решение самого простого варианта задачи.
При рекурсивном вызове функций в C#используется стековая организация хранения локальных параметров.
Стек является простейшей динамической структурой организации данных. Добавление элементов в стек и выборка из него выполняются из одного конца, называемого вершиной стека. Говорят, что стек реализует принцип обслуживания LIFO (last in — first out, последним пришел - первым ушел (обслужен)).
Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах.
Различия между итерацией и рекурсией:

1. 
   итерации необходим цикл и вспомогательные величины, в то время как рекурсия обходится без вспомогательных величин и обычно проще для понимания, короче и нагляднее итерации;
   
2. 
   итерация требует меньше места в оперативной памяти и меньших затрат машинного времени, чем рекурсия, которой необходимы затраты на управление стеком;
   
3. 
   при реализации рекурсии велика вероятность переполнения стека.
   

Поэтому при выборе способа описания функции следует вначале решить, чему отдать предпочтение – эффективности программы или ее компактности. Однако следует избегать рекурсий там, где есть очевидное итерационное решение. Вместе с тем существует много хороших примеров применения рекурсии (построение графических образов разнообразных узоров, работа с двоичными деревьями).
При рекурсивном описании функции последняя всегда должна содержать, по крайней мере, одну альтернативную нерекурсивную ветвь алгоритма с условием окончания вычислений, заканчивающуюся оператором возврата результата.
Различают две формы рекурсивных подпрограмм:
- прямая рекурсия;
- косвенная рекурсия.
В первом случае функция содержит вызов этой же функции.