Рекурсивный и итерационный методы решения задач. Виды рекурсий.

Рекурсия.

Описание объектов или вычисления в терминах самого себя. Обращение подпрограммы к самой себе.

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

2. Вызов с другим значением параметра. Чтобы не произошло зацикливание рекурсивных вызовов, необходимо, чтобы внутренний вызов производился с модифицированным значением параметра. При этом желательно, чтобы модификация стремилось к состоянию прерывания рекурсии.

Виды рекурсий.

1. Линейная рекурсия – выполнение тела подпрограммы приводит не более чем к одному рекурсивному вызову. Существует линейная цепочка вызовов. Вычисление факториала.

2. Повторная рекурсия – разновидность линейной рекурсии, когда рекурсивный вызов внутри подпрограммы является последним оператором. Отсутствуют какие-либо предварительные, или отложенные вычисления. В этом случае все действия подпрограммы выполнены и управление передается в другой вызов, а внутреннее состояние можно забыть. В этом случае нет необходимости сохранять все предыдущие промежуточные значения и результатом вычислений является последний вызов.

3. Каскадная рекурсия – возникает, если при выполнении тела подпрограммы, рекурсивные вызовы могут возникнуть более одного раза. Древовидная схема вызовов.

4. Взаимная рекурсия – циклическая последовательность взаимных вызовов нескольких подпрограмм, когда одна подпрограмма производит обращение к другой, а та в свою очередь снова может обратиться к первой. Всегда может быть сведена к линейной.

5. Удаленная рекурсия – если в теле функции при рекурсивных вызовах в выражении являющихся фактическими параметрами, снова встречаются рекурсивный вызов этой функции.

Недостатки рекурсивного подхода:

Время выполнения не всегда меньше, чем другими способами. Опасные зацикливания. Всегда нужно предусматривать условия выхода. Сложность понимания. Передача множества параметров.