Тема довольно избитая, но мне все таки показалась интересной, и я решил об этом написать. Речь пойдет о линейных рекурсивном и итеративном вычислительных процессах.
Рассмотрим два подхода к процессу вычисления: рекурсивный и итеративный. В качестве примера возьмем задачу вычисления факториала. Для тех, кто забыл, что это такое, привожу определение из wikipedia: факториал — функция, определённая на множестве неотрицательных целых чисел, обозначается n!, произносится эн факториал. Факториал натурального числа n определяется как произведение всех натуральных чисел от 1 до n включительно:
n! = 1 * 2 * 3 * … * n
Факториал числа 6 будет равен:
6! = 1 * 2 * 3 * 4 * 5 * 6 = 720
Напишем функции, реализующие рекурсивный и итеративный процессы вычисления факториала. Воспользуемся для этого языком Python.
Линейный рекурсивный вычислительный процесс.
def fact_line_rec_proc(n): if n == 0 or n == 1: return 1 else: return n * fact_line_rec_proc(n - 1)
Если, в качестве аргумента такой функции передать число 6, то получим ответ 720. Проверьте сами! Проблема в том, что такой код не очень оптимален, т.к. интерпретатору приходится “помнить” все промежуточные состояния в процессе вычисления. Количество шагов, которое нужно сделать этому алгоритму, имеет порядок роста O(n), количество задействованной памяти – также O(n). Можно предложить более оптимальный алгоритм (см. код ниже).
Линейный итеративный вычислительный процесс.
def fact_iter_v1(n): if n == 0 or n == 1: return 1 else: prod = 1 for i in range(1, n + 1): prod *= i return prod
Количество шагов полученного алгоритма имеет тот же порядок роста, что и предыдущий – O(n), но по памяти он значительно выигрывает: порядок роста составляет O(1). А можно ли обойтись без присваиваний? Т.е. сделать его иммутабельным, но при этом итеративным? Можно! И выглядеть это будет так.
def fact_line_iter_proc(n): return fact_iter(1, 1, n) def fact_iter(prod, counter, n): if counter > n: return prod else: return fact_iter(counter * prod, counter + 1, n)
То, что мы получили, называют хвостовой рекурсией, и этот подход очень активно используется в функциональных языках программирования, где нет понятия переменной в классическом ее понимании (как в императивных или ООП языках программирования типа Python, C, Java, C#).
Приведем аналоги функций fact_line_rec_proc и fact_line_iter_proc на языке Haskell.
Функция с линейным рекурсивным вычислительным процессом.
fact_line_rec_proc :: Integer -> Integer fact_line_rec_proc 0 = 1 fact_line_rec_proc 1 = 1 fact_line_rec_proc n = n * fact_line_rec_proc (n - 1)
Функция с итеративным вычислительным процессом.
fact_line_iter_proc :: Integer -> Integer fact_line_iter_proc n = fact_iter 1 1 n fact_iter prod counter n | counter > n = prod | counter <= n = fact_iter (prod * counter) (counter + 1) n
Функцию fact_line_iter_proc можно назвать рекурсивной функцией с линейным вычислительным процессом!
