Смекни!
smekni.com

Основы программирования на языке Си (стр. 21 из 27)

и рекурсивная часть. Согласно определению, факториал 6 вычисляется следующим

образом:

6! = 6*5! = 6*5*4! = 6*5*4*3! = 6*5*4*3*2! = 6*5*4*3*2*1! = 6*5*4*3*2*1*1 = 720

2. Простой пример рекурсии

Рассмотрим рекурсивную функцию "print_backwards()" из программы 2.1. Эта

функция предназначена для ввода с клавиатуры последовательности символов. Для

прекращения ввода пользователь должен напечатать специальный символ (точку).

После этого функция печатает введенные символы в обратном порядке.

#include<iostream.h>

void print_backwards();

int main()

{

print_backwards();

cout << "&bsol;n";

return 0;

}

void print_backwards()

{

char character;

cout << "Введите символ (или '.' для завершения ввода): ";

cin >> character;

if ( character != '.' )

{

90

print_backwards();

cout << character;

}

}

Программа 2.1.

Программа 2.1 печатает на экране подобные сообщения:

Введите символ (или '.' для завершения ввода): H

Введите символ (или '.' для завершения ввода): i

Введите символ (или '.' для завершения ввода): .

iH

Порядок выполнения функции "print_backwards()" подробно описан в сле-

дующем параграфе. Пока обратите внимание на то, что вызов "print_backwards()" (в

ее собственном определении) находится внутри оператора "if".

В определениях рекурсивных функций обычно есть некоторый оператор ветв-

ления, у которого, как минимум, одна нерекурсивная ветвь, реализующая "базовое

утверждение" определения функции. Если такой ветви нет, то функция будет вызы-

вать себя бесконечно (в действительности, до тех пор, пока не будет занята вся па-

мять).

В программе 2.1 базовое утверждение реализовано неявно это возврат из

функции, если был введен символ "." (точка).

3. Как выполняется рекурсивный вызов

Порядок выполнения программы 2.1 легко понять с помощью нескольких схем.

Главная функция начинается с вызова "print_backwards()". Для выполнения вы-

зова функции в памяти компьютера выделяется некоторое количество памяти (необ-

ходимое для запоминания адреса возврата, для создания копий параметров по значе-

нию и для передачи параметров-указателей). Свободная область памяти в момент

первого вызова "print_backwards()" на рис. 1 изображена в виде пустого прямо-

угольника. Внутри прямоугольника показано содержимое экрана в соответствующие

моменты времени (на схемах считается, что направление "сверху-вниз" соответствует

увеличению времени, прошедшему с момента запуска программы).

Рис. 1.. Свободная область памяти перед

первым вызовом "print_backwards()"

Рис. 2. Свободная область памяти перед

вторым вызовом "print_backwards()".

Выполнение функции "print_backwards()" начинается со ввода символа, а за-

тем происходит второй вызов "print_backwards()" (в этот момент программа еще не

91

начинала обратную печать символов). Для второго вызова также выделяется некото-

рое количество памяти, поэтому объем свободной памяти уменьшается (рис. 2).

Далее процесс повторяется, но, допустим, при третьем вызове

"print_backwards()" пользователь ввел завершающий символ (точку). Поэтому после

третьего вызова происходит возврат в вызывающую функцию (т.е. во второй экземп-

ляр "print_backwards()"), см. рис. 3.

Рис. 3. Возврат из 3-го экземпляра функции

"print_backwards()" во второй.

Рис. 4.. Завершение выполнения программы.

Второй экземпляр "print_backwards()" завершается, но перед завершением вы-

водит на экран символ "i". В свою очередь, первый экземпляр функции перед завер-

шением работы напечатает на экране символ "H" (рис. 4).

Для организации вызовов функций и создания автоматических переменных в

программах на Си++ отводится специальная область памяти стек. Память, необхо-

димая для очередного вызова функции, выделяется в верхней части стека (в старших

адресах). При завершении функции размер стека уменьшается на соответствующую

величину. Изменение состояния программного стека для рассмотренного выше при-

мера показано на рис. 5.

Рис. 5.. Последовательность состояний стека программы 2.1 применительно к

тестовому примеру.

Стек в программах на Си++ используется при вызове всех функций, а не только

рекурсивных. Стек, как и связный список, является одной из разновидностей абст-

рактных типов данных. Характерная особенность стека соответствие принципу "по-

следним прибыл первым обслужен" (в отличие от стека, очередь является примером

абстрактного типа данных, действующего по принципу "последним прибыл послед-

ним обслужен").

92

4. Еще три примера рекурсии

В этом параграфе приводятся три примера рекурсивных функций. В 3-й лекции

рассматривалась функция для вычисления факториала целого положительного числа

(лекция 3, программа 3.1). Ниже приведен рекурсивный аналог этой функции:

int factorial( int number )

{

if ( number < 0 )

{

cout << "&bsol;nОшибка - отрицательный аргумент факториала&bsol;n";

exit(1);

}

else if ( number == 0 )

return 1;

return number*factorial( number - 1 );

}

Фрагмент программы 4.1.

В качестве второго примера (фрагмент программы 4.2) дана функция, возводя-

щая свой первый параметр (типа "double") в степень с показателем, который переда-

ется в качестве второго параметра (неотрицательное целое число).

double raised_to_power( double number, int power )

{

if ( power < 0 )

{

cout << "&bsol;nОшибка - отрицательный показатель степени&bsol;n";

exit(1);

}

else if ( power == 0 )

return 1.0;

return number*raised_to_power( number, power - 1 );

}

Фрагмент программы 4.2.

В рекурсивных функциях из программ 4.1 и 4.2 особое внимание уделено за-

щите от "бесконечного вызова ". Эта защита основана на проверке параметров, обес-

печивающей выполнение вычислений только для корректных значений переданных

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

конечном счете произойдет возврат из функции. При недопустимых значениях пара-

метров выдается сообщение об ошибке и выполняется возврат из функций или завер-

шение работы программы.

Третий пример (фрагмент программы 4.3) это рекурсивная функция для вы-

числения суммы первых n элементов целочисленного массива "a[]".

int sum_of( int a[], int n )

{

if ( n < 1 || n > MAXIMUM_NO_OF_ELEMENTS )

{

93

cout << "&bsol;nОшибка - допускается суммирование от 1 до ";

cout << MAXIMUM_NO_OF_ELEMENTS << " элементов&bsol;n";

exit(1);

}

else if ( n == 1 )

return a[0];

return a[n-1]+sum_of( a, n-1 );

}

Фрагмент программы 4.3.

5. Рекурсия и циклы

При программировании на Си++ рекурсию применять совсем не обязательно, и

на практике она используется довольно редко. Любую рекурсивную функцию можно

реализовать итеративно, т.е. с помощью циклов "for", "while" или "do...while". В

некотором смысле, какое определение функции выбрать (рекурсивное или итераци-

онное) вопрос пристрастий программиста. Исходный текст рекурсивных функций

иногда легче для понимания, но итерационные функции практически всегда работают

быстрее. Далее приводятся итерационные аналоги двух рекурсивных функций, кото-

рые ранее рассматривались в данной лекции.

void print_backwards()

{

char chars[MAX_ARRAY_LENGTH];

int no_of_chars_input = 0;

do {

cout << "Введите символ (или '.' для завершения ввода): ";

cin >> chars[no_of_chars_input];

no_of_chars_input++;

} while ( chars[no_of_chars_input - 1] != '.'

&& no_of_chars_input < MAX_ARRAY_LENGTH );

for ( int count = no_of_chars_input - 2; count >= 0; count-- )

cout << chars[count];

}

Фрагмент программы 2.1b.

int factorial( int number )

{

int product = 1;

if ( number < 0 )

{

cout << "&bsol;nОшибка - отрицательный аргумент факториала&bsol;n";

exit(1);

}