О рекурсии и итерации

Автор: | 18.03.2018

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

Рассмотрим два подхода к процессу вычисления: рекурсивный и итеративный. В качестве примера возьмем задачу вычисления факториала. Для тех, кто забыл, что это такое, привожу определение из 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 можно назвать рекурсивной функцией с линейным вычислительным процессом!

Поделиться
Share on VK
VK
Tweet about this on Twitter
Twitter
Share on Facebook
Facebook
Share on Google+
Google+

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *