Начну с классического примера о факториале. Факториалом целого положительного числа N называется произведение всех целых чисел от 1 до N. Например, факториал пяти равен 1*2*3*4*5, то есть 120. Факториал единицы считается равным 1.
Все понятно. Однако, существует еще один, совершенно ужасный способ объяснения, что такое факториал. Вот он:
“Факториал единицы равен 1. Факториал любого целого положительного числа N, большего единицы, равен числу N, умноженному на факториал числа N-1.”
Если вам уже все ясно, значит вы - математический талант. Для нормальных людей поясню. Чтобы последнее предложение было понятнее, возьмем какое-нибудь конкретное N, например, 100. Тогда это предложение будет звучать так: Факториал числа 100 равен числу 100, умноженному на факториал числа 99.
Ну и что? И как же отсюда узнать, чему равен какой-нибудь конкретный факториал, скажем, факториал трех? Будем рассуждать совершенно чудовищным образом:
Смотрю в определение: Факториал трех равен 3 умножить на факториал двух. Не знаю, сколько это. Спускаюсь на ступеньку ниже.
Смотрю в определение: Факториал двух равен 2 умножить на факториал единицы. Не знаю, сколько это. Спускаюсь еще на ступеньку.
Смотрю в определение: Факториал единицы равен 1. Вот - впервые конкретное число. Значит можно подниматься.
Поднимаюсь на одну ступеньку. Факториал двух равен 2 умножить на 1, то есть 2.
Поднимаюсь еще на ступеньку. Факториал трех равен 3 умножить на 2, то есть 6. Задача решена.
Рассуждая таким образом, можно вычислить факториал любого числа. Способ рассуждения называется рекурсивным, а способ объяснения называется индуктивным.
Какое отношение все это имеет к компьютерам? Дело в том, что рекурсивный способ рассуждений реализован во многих языках программирования, в том числе - и в Паскале. Значит, этим языкам должен быть понятен и индуктивный способ написания программ.
Обозначим кратко факториал числа N, как Factorial(N), и снова повторим наш индуктивный способ объяснения:
“Если N=1, то Factorial(N) = 1.
Если N>1, то Factorial(N) вычисляется умножением N на Factorial(N-1).”
В соответствии с этим объяснением напишем на Паскале функцию Factorial для вычисления факториала:
FUNCTION Factorial(N: Byte): LongInt;