C език в примери
Факториелът на число n е произведението на първите n естествени числа:
н! = 1 ⋅ 2 ⋅ … ⋅ n = ∏ i = 1 n i . ^i.>
По-долу ще разгледаме примери за програми, съдържащи факторна функция, която изчислява факториела на дадено число.
Съдържание
Прилагане на рекурсивната формула[редактиране]
Дефиницията на факторната функция по-горе се основава на следнатарекурентнаформула:
н! = n ⋅ ( n − 1 ) ! , 0 ! = 1.
За да изчислите факториела n ! тази функция се самоизвиква с аргумент n − 1.
Тернарен оператор (?:) в израз (n 2)? 1 : n * факторен ( n - 1 ) за върнатата стойност ( return ) „прекъсва“ рекурсията, когато аргументът на функцията стане по-малък от 2. В противен случай факторната функция постоянно ще се извиква сама и по време на изпълнение на програмата ще получим съобщение за грешка „препълване на стека“ или „превишена дълбочина на рекурсия“. За да се избегне това, е необходимо за някои стойности на аргумента функцията да не се извиква сама, а да изчислява стойността си "независимо".
Идеята на рекурсията е да намали проблема до същия проблем, но за по-прости случаи (например за по-малка стойност на аргумента n). Процесът на намаляване на проблема до предишния трябва да приключи някой ден, така че рекурсивните функции за най-простите входни данни трябва да „знаят“ на какво са равни и да не правят рекурсивни извиквания.
Използване на рекурсия на опашката[редактиране]
Възможността за рекурсия е ограничена от дълбочинатана стека за връщане.В някои случаи обаче внедряването на език за програмиране може само по себе си да намали рекурсията до итерация.
В примера по-долу ще използваме опашна рекурсия, чието редуциране до итерация, въпреки чене се изисква от стандарта, но все пак се прилага, например от C компилатора, включен в общия GCC комплект. За да направим това, трябва да дефинираме помощна функция factorial_1, която изчислява стойността p n !, където p, n са аргументите на функцията.
Моля, обърнете внимание, че в този пример не включваме дефиницията на основната функция, нитопрепроцесорните директиви#include за включване назаглавките, които използваме - те трябва да бъдат заимствани от предишния пример.
Ясно итеративен вариант[редактиране]
И накрая, във версията по-долу ще елиминираме напълно рекурсията от дефиницията на факторната функция, изрично я редуцирайки до итерация.
За разлика от първата опция (но подобна на опцията за рекурсия на опашката), в този пример се нуждаехме от допълнителна локална променлива. В случай на рекурсия без опашка, ролята на такава променлива всъщност се играе от нарастващиястек за връщане.Имайте предвид обаче, че това не е толкова важно в тази конкретна задача.
Вариант "произволен" [редактиране]
Стандартът изисква поддръжка за внедряване за 8, 16, 32 и 64 битови цифрови типове. [1] Лесно се вижда обаче, че вече е на 21! = 51,090,942,171,709,440,000 - което надвишава ограниченията за 64-битово число - както със знак (9,223,372,036,854,775,807), така и без знак (18,446,744,073,709,551,615).
Ако по някаква причина е необходимо да се изчислят точните факторни стойности за числа от 21 и по-високи, трябва да използвате библиотеки от операции с числа с произволна битова дължина - като например GNU MP. [2]