Факториальный алгоритм отлично подходит для рекурсии
Что такое факториал?
В математике факториал неотрицательного целого числа n, обозначаемого n !, является произведением всех положительных целых чисел, меньших или равных n. Например
5! = 5 x 4 x 3 x 2 x 1 = 120. Это просто произведение целого числа и всех целых чисел под ним. - Wikepedia
Как написать факториальную функцию с помощью рекурсии?
Факториальную программу можно написать рекурсивно, потому что это функция, которая вызывает сама себя.
Псевдокод
1. func factorial (n)
2. if (n == 1)
3. return 1
4. return n * factorial (n -1)
factorial(int n) { //Base Case if(n == 1) return 1; return n *factorial(n-1); }
Вы можете увидеть, как преобразовать функцию в отношение повторения в этом видео, это не факториальная функция, а функция с таким же отношением повторения.
Напишите факториальную функцию в виде рекуррентного отношения
Эта функция, записанная как рекуррентное отношение, имеет следующий вид:
T (n) = 1 для n = 0
T (n) = 1 + T (n-1) для n ›0
Это время выполнения повторения в нотации Big O составляет: ** O (n) **, что является основной целью преобразования алгоритмов в отношения повторения.
Вы можете узнать, как решить эту проблему, из этого видео.
Давайте посмотрим на пример:
Предположим, у нас есть произвольное число n = 5, поэтому мы используем функцию factorial (5)
Получаем следующее Число итераций
1) факториал (5) = 5 * факториал (4)
2) факториал (4) = 4 * факториал (3)
3) факториал (3 ) = 3 * факториал (2)
4) факториал (2) = 2 * факториал (1)
5) факториал (1) = 1
Таким образом, факториальная функция вызывала себя 5 раз, что совпадает с номером входного размера 'n', где n = 5. Таким образом, повторение выполнялось 'n' раз, и, следовательно, O (n).
Спасибо, что прочитали эту статью. Надеюсь, она будет вам полезна! Продолжайте учиться, и если вы хотите больше видео с анализом алгоритмов, посетите и подпишитесь на мои каналы YouTube (randerson112358 и compsci112358)
Ознакомьтесь со следующими материалами для получения дополнительных материалов / видео по анализу алгоритмов и программированию:
Канал YouTube:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ
compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA
Веб-сайт:
http://everythingcomputerscience.com/
Видеоуроки по взаимосвязи повторяемости:
https://www.udemy.com/recurrence-relation-made-easy/
Видеоурок по анализу алгоритмов:
https://www.udemy.com/algorithm-analysis/
Twitter:
https://twitter.com/CsEverything