Мова Сі в прикладах
Факторіалом числа n називають добуток перших n натуральних чисел:
n! = 1 ⋅ 2 ⋅ … ⋅ n = ∏ i = 1 n i . ^i.>
Нижче ми розглянемо приклади програм, що містять обчислюючу факторіал заданого числа функцію factorial .
Зміст
Реалізація рекурентної формули [ред.]
Визначення функції factorial вище ґрунтується на наступнійрекурентнійформулі:
n! = n ⋅ ( n − 1 ) ! , 0! = 1.
Для обчислення факторіалу n! ця функція викликає себе з аргументом n − 1.
Тернарний оператор (?:) у виразі (n 2)? 1 : n * factorial ( n - 1 ) для повертаного значення ( return ) «обриває» рекурсію, коли аргумент функції стає меншим 2. В іншому випадку, функція factorial постійно б викликала саму себе, і під час виконання програми ми отримали б повідомлення про помилка «переповнення стека» або «перевищена глибина рекурсії». Для того, щоб цього не було, необхідно, щоб при деяких значеннях аргументу, функція не викликала саму себе, а обчислювала своє значення «самостійно».
Ідея рекурсії полягає у зведенні завдання до цієї задачі, але для більш простих випадків (наприклад, для меншого значення аргументу n ). Процес зведення завдання до попередньої повинен колись закінчуватися, тому рекурсивні функції для найпростіших вхідних даних повинні знати, чому вони рівні і не робити рекурсивних викликів.
Використання хвостової рекурсії [ред.]
Можливість рекурсії обмежена граничною глибиноюстека повернення.У деяких випадках, проте, реалізація мови програмування може самостійно звести рекурсію до ітерації.
У прикладі нижче ми скористаємося хвостовою рекурсією, зведення якої до ітерації хоча іне потрібно стандартом, але все ж реалізується, наприклад, компілятором C, що входить до поширеного комплекту GCC. Для цього нам потрібно буде визначити допоміжну функцію factorial_1 , що обчислює значення p n !, де p , n - аргументи функції.
Зверніть увагу, що в цьому прикладі ми не наводимо ні визначення функції main , нідиректив препроцесора#include підключення використовуваних намизаголовків- їх слід запозичувати з попереднього прикладу.
Очевидно ітеративний варіант [ред.]
Нарешті, у варіанті нижче ми виключимо рекурсію з визначення функції factorial , явно звівши її до ітерації.
На відміну від першого варіанта (але аналогічно варіанту з хвостовою рекурсією) у цьому прикладі нам знадобилася додаткова локальна змінна. У разі «нехвостової» рекурсії роль такої змінної фактично відіграє зростаючий стек повернення. Зазначимо, втім, що в даній конкретній задачі це не так важливо.
Варіант «довільний» [ред.]
Стандарт вимагає підтримки реалізацією числових типів розрядності 8, 16, 32 та 64 біт. [1] Неважко переконатися, що вже 21! = 51090942171709440000 - що перевищує граничні значення для 64-бітового числа - як зі знаком (9 223 372 036 854 775 807), так і без знака (18 446 744 055).
Якщо з яких-небудь причин потрібно обчислити точні значення факторіалу для чисел від 21 і вище, слід використовувати бібліотеки операцій з числами довільної розрядності, наприклад, GNU MP. [2]