Факториальный алгоритм отлично подходит для рекурсии

Что такое факториал?

В математике факториал неотрицательного целого числа 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)

Программа C

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

Ресурсы:

  1. Введение в алгоритмы, 3-е издание
  2. Википедия
  3. Математика - это весело
  4. дионизиз