Паскаль. Основы программирования


Повторение


О рекурсии

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

О подпрограмме, которая вызывает саму себя, говорят, что она рекурсивна.

Многие математические функции и алгоритмы, будучи запрограммированы на Паскале, наиболее естественно выражаются именно в рекурсивной форме. В большинстве случаев рекурсивное решение задачи получается достаточно простым, но в то же время оказывается крайне неэффективным в сравнении с итеративной реализацией этого алгоритма.

2. Рекурсивное определение какого-либо понятия или процесса должно содержать два обязательных элемента: 1) условие прекращения рекурсии, задающее некоторое фиксированное значение для одного или нескольких простых этапов вычисления; 2) выражение более сложного этапа вычислений в терминах менее сложного. Правильно организованный рекурсивный процесс развивается таким образом, что любая сколь угодно сложная ситуация в конце концов сводится к условию прекращения рекурсии.

3. В качестве примера, демонстрирующего рекурсию, часто используют функцию факториала, определяемую как произведение всех натуральных чисел от 1 до n (в математической нотации n!). Например, 4! = 1 . 2 . 3 .

4 = 24. Этому вычислительному процессу можно придать и рекурсивную трактовку. Роль условия выхода из рекурсии здесь играет равенство 0! = 1 или 1! = 1. Выражение сложного этапа через более простой имеет вид n! = (n - 1)!

n.

4. В подпрограмме на Паскале рекурсивный вызов внешне выглядит точно так же, как и вызов любой другой подпрограммы. Так, в функции fac, вычисляющей значение "n-факториал", ее тело имеет следующий вид:

if (n = 0) or (n = 1) then

fac := 1 {завершение рекурсии}

                               {иначе - рекурсивный вызов}

                               else fac := fac(n - 1)*n

Имя функции fac получает значение 1, если n равно 0 или 1; если же n больше единицы, то значение fac определяется как произведение n и значения, полученного от рекурсивного обращения к fac(n - 1).




- Начало -  - Назад -  - Вперед -



Книжный магазин