Относится ли алгоритм вычисления факториала к парадигме "Разделяй и властвуй"?
При изучении парадигмы "Разделяй и властвуй" попадается пример с вычислением числа Фибоначчи с эффективной двойной рекурсией. И тут все понятно, что задача на первом шаге разбивается на 2 подзадачи с двойной рекурсией, присутствует базовый случай и, действительно, - это парадигма "Разделяй и властвуй".
Тут возникает вопрос:
Относится ли задача с простым рекурсивным вычислением факториала числа к той же парадигме "Разделяй и властвуй"?
def recur_factorial(n):
if n == 1:
return n
else:
return n*recur_factorial(n-1)
Я думаю, что не относится, так как тут не вижу разделение задачи на несколько более мелких подзадач, хотя вижу явное присутствие базового случая и рекурсии. Хотелось бы удостовериться в своих рассуждениях.
Ответы (1 шт):
Нет, рекурсивное вычисление факториала - просто сведение задачи к размерности, меньшей на единицу. Здесь нет выделения двух (или нескольких) подзадач, решения каждой по отдельности, затем объединения результатов (хороший пример - сортировка слиянием).
Пример с числами Фибоначчи тоже не слишком удачный, поскольку подзадачи не являются независимыми, и в результате происходит многократное вычисление одних и тех же величин (что ведет к экспоненциальной сложности вычисления, хотя даже без применения математических хитростей можно посчитать числа Фибоначчи линейно)