Рекурсия
Обновлен: Ноябрь 2007
Рекурсия — это важный метод программирования, позволяющий функции вызывать саму себя. В качестве одного из примеров можно привести расчет факториалов. Факториалом 0 является именно 1. Факториал n (целого числа больше 0) является произведением всех целых чисел в диапазоне от 1 до n.
Использование рекурсии
В следующем абзаце в текстовой форме представлена функция, рассчитывающая факториал.
"Если число меньше нуля — оно пропускается. Если число не является целым числом — оно пропускается. Если число равно нулю, то его факториалом будет единица. Если число больше нуля, оно умножается на факториал следующего меньшего числа".
Для вычисления факториала любого числа, которое больше нуля, необходимо вычислить факториал, по меньшей мере, одного другого числа. Функция должна вызывать саму себя для следующего меньшего числа, прежде чем будет выполнена для текущего числа. Далее приведен пример рекурсии.
Рекурсия и итерация (цикл) тесно связаны — функция может возвращать те же результаты при рекурсии или итерации. Обычно, конкретное вычисление выполняется по тому или иному способу, и нужно просто выбрать наиболее естественный или предпочтительный подход.
Несмотря на полезность рекурсии можно просто создать рекурсивную функцию, которая никогда не возвращает результата и не достигает конечной точки. Такая рекурсия заставляет компьютер выполнять бесконечный цикл. Приведем пример. Пропустим первое правило (об отрицательных числах) из словесного описания вычисления факториала и попытаемся вычислить факториал любого отрицательного числа. Вычисление выполнить не удастся, поскольку для расчета факториала, например числа -24, сначала необходимо вычислить факториал числа -25. Для вычисления факториала -25 сначала необходимо вычислить факториал числа -26, и так далее. Очевидно, что вычисление никогда не будет закончено.
Другая проблема, которая может быть связана с рекурсией заключается в том, что рекурсивная функция использует все доступные ресурсы (такие как системная память и пространство стека). Каждый раз, когда рекурсивная функция вызывает саму себя (или вызывает другую функцию, которая в свою очередь вызывает исходную функцию) используются некоторые ресурсы. Эти ресурсы высвобождаются при завершении рекурсивной функции, но если в функции слишком много уровней рекурсии, то существует вероятность расходования всех доступных ресурсов. Когда это происходит, возникает исключение.
Поэтому следует с осторожностью составлять рекурсивные функции. Если существует вероятность избыточной (или бесконечной) рекурсии, следует построить функцию таким образом, чтобы она учитывала количество вызовов, и затем ограничить число вызовов. По достижении порогового значения вызовов функции, выполнение функции автоматически прекращается. Оптимальное максимальное число итераций зависит от рекурсивной функции.
Далее еще раз показана рекурсивная функция — на этот раз в коде JScript. Используется аннотирование типа, так что функция принимает только целые числа. При подстановке недопустимого числа (то есть, числа меньше нуля) оператор throw создает ошибку. В противном случае рекурсивная функция используется для вычисления факториала. Рекурсивная функция принимает два аргумента: один — аргумент факториала, а второй — счетчик, учитывающий текущий уровень рекурсии. Если счетчик не достигает максимального уровня рекурсии, возвращается факториал исходного числа.
function factorialWork(aNumber : int, recursNumber : int ) : double {
// recursNumber keeps track of the number of iterations so far.
if (aNumber == 0) { // If the number is 0, its factorial is 1.
return 1.;
} else {
if(recursNumber > 100) {
throw("Too many levels of recursion.");
} else { // Otherwise, recurse again.
return (aNumber * factorialWork(aNumber - 1, recursNumber + 1));
}
}
}
function factorial(aNumber : int) : double {
// Use type annotation to only accept numbers coercible to integers.
// double is used for the return type to allow very large numbers to be returned.
if(aNumber < 0) {
throw("Cannot take the factorial of a negative number.");
} else { // Call the recursive function.
return factorialWork(aNumber, 0);
}
}
// Call the factorial function for two values.
print(factorial(5));
print(factorial(80));
После выполнения этой программы выводится следующий результат:
120
7.156945704626378e+118