Рекурсия и итерации
Чтобы понять рекурсию, надо понять рекурсию...
Итерация в программировании -
один шаг циклического процесса обработки данных.
Часто итерационные алгоритмы на текущем шаге (итерации) используют вычисленный на предыдущих шагах результат такой же операции или действия. Одним из примеров таких вычислений служат вычисления рекуррентных соотношений.
Простым примером величины, вычисляемой с помощью рекуррентных соотношений, является факториал:
\(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
Вычисление значения на каждом шаге (итерация) это
\(N=N \cdot i\) . При вычислении значения
\(N\), мы берем уже сохраненное значение
\(N\).
Факториал числа можно также описать с помощью
рекуррентной формулы:
\(\begin{equation*} n! = \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{cases} \end{equation*}\)
Можно заметить, что это описание является ни чем иным как рекурсивной функцией.
Здесь первая строка (
\(n <= 1\)) - это базовый случай (условие окончания рекурсии), а вторая строка - переход к следующему шагу.
| Рекурсивная функция вычисления факториала |
Итерационный алгоритм |
def Factorial(n):
if n > 1:
return n * Factorial(n - 1)
else:
return 1
|
x = 1
for i in range(1, n + 1):
x = x * i;
|
Следует понимать, что вызов функций влечет за собой некоторые дополнительные накладные расходы, поэтому не рекурсивный вариант вычисления факториала будет несколько более быстрым.
Вывод: там, где можно написать программу простым итерационным алгоритмом, без рекурсии, то надо писать без рекурсии. Но все таки существует большой класс задач где вычислительный процесс реализуется только рекурсией.
С другой стороны - рекурсивные алгоритмы чаще всего более понятны.
