Рекурсия в программировании

С помощью конечной рекурсивной программы можно описать бесконечное вычисление, причем программа не будет содержать явных повторений

Рекурсивные функции

Если некоторая подпрограмма (функция) содержит явную ссылку на саму себя, то ее называют

прямо-рекурсивной

Если подпрограмма P ссылается на другую подпрограмму Q, которая содержит ссылку на P, то такую подпрограмму называют

косвенно-рекурсивной

Рекурсия

Рекурсия сводит решение задачи к решению более мелких идентичных

задач

Сложные задачи могут иметь простые рекурсивные решения

Не всегда рекурсивный метод решения лучше итеративного (основанного на использовании циклов)

Общий вид рекурсии:

Если (простейший случай) тогда Решить напрямую

Иначе

Делать рекурсивный вызов до появления простейшего случая

Свойства рекурсивных

алгоритмов:

Правильный рекурсивный алгоритм не должен создавать бесконечную последовательность вызовов самого себя.

Для этого он обязательно должен содержать нерекурсивный выход, т.е. при некоторых исходных данных вычисления в алгоритме должны производиться без вызовов его самого - тривиальный случай.

Определение сложного случая в терминах более простого.

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

Задача о вычислении Факториала

Вычисление факториала – пример задачи, в которой мы можем использовать рекурсию. Факториал n -это произведение всех натуральных чисел до n включительно. К примеру:

5! = 5 * 4 * 3 * 2 * 1 = 120 4! = 4 * 3 * 2 * 1 = 24 3! = 3 * 2 * 1 = 6 2! = 2 * 1 = 2 1! = 1 0! = 1

Однако мы можем выразить факториал рекурсивно, через другие факториалы:

5! = 5 * 4! 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1 * 0! 0! = 1

Факториал числа

Рекурсивное определение:

long Fact(int n)

{if(n==0) return 1;

else return (Fact(n-1)*n);

}

Факториал числа: итеративное определение

long Factorial (int n)

{int i; long f;

if (n==0) return 1; else

for(i=1;i<=n;i++)

{f=f*i;} return f;

}

Рекурсивное решение

При вызове подпрограммы всякий раз создаются новые экземпляры локальных переменных

При этом не возникает никаких конфликтов при использовании имен