Рекурсии

Рекурсия — это такой способ организации вычислительного процесса, при ко­тором процедура или функция в ходе выполнения составляющих ее операторов об­ращается сама к себе.

Примером программы с использованием рекурсии может быть программа вы­числения факториала числа. (Факториалом натурального числа п называют произ­ведение чисел 1*2*...*п.)

После запуска программы на экран выводится запрос "Введите число N >", за­тем с клавиатуры считывается значение целого числа N и в выражении F:=Fakt(N) вызывается функция Fakt с параметром—значением N. В подпрограмме-функции вычисления факториала проверяется условие N=1. Если оно выполняется, то функ­ции Fakt присваивается значение 1, на этом выполнение подпрограммы-функции завершается. Если условие N=1 не соблюдается, то выполняется вычисление произ­ведения N*Fakt(N—1). Вычисление произведения носит рекурсивный характер, так как при этом осуществляется вызов функции Fakt(N—1), значение которой вычис­ляется, в свою очередь, через вызов функции Fakt, параметром которой также бу­дет функция Fakt, и т. д., до тех пор пока значение формального параметра N=1. Так как базовая часть описания рекурсивной функции Fakt определяет значение Fakt для N=1-, равным единице, то рекурсивные вызовы функции Fakt больше не выполняются, а наоборот, выполняется вычисление функции Fakt для чисел, воз­растающих от 1 до N, причем функция Fakt всякий раз возвращает значение, равное произведению очередного k-ro числа на факториал от k—1-го числа. Последнее возвращение результата вычисления функции Fakt присвоит переменной F значе­ние произведения всех чисел от 1 до N, т. е. факториал числа N.

Итак, при выполнении рекурсивной подпрограммы осуществляется многократ­ный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В нашем примере решение при N=1 тривиально, т. е. Fakt=l. Затем осуществляется возврат на верхний уровень с последовательным вычислением значения функции Fakt.

Упражнение 7. Запустите интегрированную среду программирования. Введите текст
программы Demo_Rekurs и запишите файл на диск под соответствующим именем, а затем
откомпилируйте его. После того как компиляция выполнится успешно, задайте для просмот­
ра в окне отладчика переменные N, F. Установите видимыми одновременно окна редактора
с текстом программы и окно просмотра. Исполните программу в пошаговом режиме с захо­
дом в функцию и пронаблюдайте за изменением значения переменной N при рекурсивных
вызовах функции Fakt. •

Следует учитывать, что использование рекурсивной формы организации алго­ритма обычно выглядит изящнее итерационной и дает более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать перепол­нение стека. Это объясняется тем, что при каждом входе в подпрограмму ее ло­кальные переменные размещаются в особым образом организованной области па­мяти, называемой программным стеком.

Дата добавления: 2015-05-09