адача 1. Составить рекурсивную программу-функцию вычисления факториала целого неотрицательного числа n.

Решение. Для целых неотрицательных чисел n факториал n обозначается через n! и определяется так:

В данном случае параметризация задачи осуществлена в её постановке. Остается лишь ввести более приемлемое для нас обозначение искомой функции. Пусть это будет facto(n). Тривиальные случаи, для которых задача решается без рекурсивных вызовов, также очевидны: facto(0)=1, facto(1)=1. Они и составляют базу рекурсии. Декомпозиция по параметру n реализуется по формуле: facto(n) = n× facto(n–1) (n=1, 2, …). Поэтому вычисления facto(n) можно организовать так:

Контрольные примеры:

Понять процесс реализации рекурсивных вызовов, то есть декомпозицию, и возвратов управления при организации отложенных вычислений можно из схемы, представленной на рис.3 (n=3). Там около стрелок в круглых скобках жирными цифрами указаны номера последовательных шагов вычислений: (1), (2), (3) - декомпозиция; (4), (5), (6) - отложенные вычисления.

Замечание. С помощью встроенной функции if() предложенный алгоритм удается записать ещё короче. Это же касается и многих других примеров.

Рис. 3. Схематическое изображение рекурсивных вызовов и отложенных вычислений при нахождении facto(3) = 3!

Для решения конкретной задачи иногда удается построить несколько различных рекурсивных алгоритмов. Например, функцию facto(n) можно было бы определить и так:

По сравнению с прежней реализацией facto() здесь количество рекурсивных вызовов уменьшается практически в 2 раза. В реальных ситуациях подобный фактор может оказаться решающим при выборе того или иного алгоритма.

Используем теперь для вычисления n! сформулированную выше схему 3 (обобщить). Если вместо исходной функции facto(n)=n! ввести в рассмотрение функцию двух переменных fa(n,l)=l × n! (n=0,1,…), то получим равенства:

Первое из этих соотношений может служить правилом декомпозиции, второе - определять рекурсивную базу, а третье показывает, как вычислять n!. Соответствующая рекурсивная программа-функция могла бы выглядеть так:

В чем же отличие этой функции от первого варианта функции facto(n)? Дело в том, в facto(n) формирование n! реализуется при проведении отложенных вычислений, в то же время нахождение fa(n, l) проводится вообще без отложенных вычислений. Особенно наглядно это видно на рисунках 3 и 4. На шагах 4, 5 и 6, отмеченных на рис. 4 жирными цифрами в круглых скобках, происходит лишь передача значений. Иными словами, здесь мы имеем повторительную рекурсию.

Рис. 4. Схематическое изображение рекурсивных вызовов и отложенных вычислений при нахождении fa(3,l)=l×3!

Еще один вариант вычисления n! можно реализовать с помощью рассмотренной ниже функции Кадью.