локальная х во внешней области действия main = 5 локёшьная X во внутренней области действия main = 7 яокёшьная X во внешней области действия main = 5

локгихьная переменная х в а = 25 после входа в а локгшьная переменная х в а = 26 перед выходом из а

локальная статическая переменная х = 50 при входе в Ь локальная статическая переменная х = 51 при выходе из Ь

глобальная переменная х = 1 при входе в с глобёшьная переменная х = 10 при выходе из с

локальная переменная х в а = 25 после входа в а локальная переменная х в а = 26 перед выходом из а

локальная статическая переменная х = 51 при входе в Ь локгшьная статическая переменная х = 52 при выходе из Ь

глобальная переменная х = 10 при входе в с глобальная переменная х = 100 при выходе из с

локальная х в main = 5

void а(void) {

int X = 25; каждый раз а присваивается начальное значение

cout << endl локальная переменная х в а = << х << после входа в а << endl;

++х;

cout << локальная переменная х в а = << х << перед выходом из а << endl;

void b(void) {

static int X = 50; Начальное значение присваивается только

при первом вызове b

cout << endl << локальная статическая переменная х = << х << при входе в Ь endl;

++х;

cout локальная статическая переменная х = х << при выходе из Ь endl;

void с(void) {

cout << endl << глобальная переменная х = << х

<< при входе в с << endl; X *= 10;

cout глобальная переменная х = х при выходе из с endl; }

3.12 Рекурсия

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

Сначала мы рассмотрим понятие рекурсии, а затем проанализируем несколько программ, содержащих рекурсивные функции. Рекурсивная задача в общем случае разбивается на ряд этапов. Для решения задачи вызывается рекурсивная функция. Эта функция знает, как решать только простейшую часть задачи - так называемую базовую задачу (или несколько таких задач). Если эта функция вызывается для решения базовой задачи, она просто возвращает результат. Если функция вызывается для решения более сложной задачи, она делит эту задачу на две части: одну часть, которую функция умеет решать, и другую, которую функция решать не умеет. Чтобы сделать рекурсию выполнимой, последняя часть должна быть похожа на исходную задачу, но быть по сравнению с ней несколько проще или несколько меньше. Поскольку эта новая задача подобна исходной, функция вызывает новую копию самой себя, чтобы начать работать над меньшей проблемой - это называется рекурсивным вызовом, или шагом рекурсии. Шаг рекурсии включает ключевое слово return, так как в дальнейшем его результат будет объединен с той частью задачи, которую функция умеет решать, и сформируется конечный результат, который будет передан обратно в исходное место вызова, возможно, в main.

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

Факториал неотрицательного целого числа п, записываемый как п!, равен

nx(n-l)x(n-2)x...xl

причем считается, что 1! = 1 и 01 = 1. Например, 5! вычисляется как 5x4x3x2x1 и равен 120

Факториал целого числа, number, большего или равного О, может быть вычислен итеративно (нерекурсивно) с помощью оператора for следующим образом:

factorial = 1;

for (int counter = number; counter >=1; counter-) factorial *= counter;

Рекурсивное определение функции факториал дается следующим соотношением:

/11=ях(я-1)1

Например, факториал 5! очевидно равен 5x4!. В самом деле:

51=5x4x3x2x1

5!=5х(4хЗх2х1)

51-5x41

Вычисление 51 должно происходить в соответствии с рис. 3.13. Рис. 3.13а показывает, как протекает последовательность рекурсивных вызовов до тех пор, пока не будет вычислен 1! = 1, что приведет к завершению рекурсии. Рис. 3.136 показывает значения, возвращаемые из каждого рекурсивного вызова оператору вызова до тех пор, нока не будет вычислено и возвращено окончательное значение.

5*4!

5 . 4!

4*3!

5! = 5 * 24 = 120 возвращается

4*3!

3 2!

4! = 4 6 = 24 возвращается

3! = 3 * 2 = б возвращается

3*2!

2 1!

2*1!

2! = 2 * 1 = 2 возвращается

1 возвращено

а) Процесс рекурсивных вызовов

6) Значения, возвращаемые после каждого рекурсивного вызова

Рис. 3.13. Рекурсивное вычисление 5!

Программа на рис. 3.14 использует рекурсию для вычисления и печати факториалов целых чисел от О до 10 (выбор типа данных unsigned long будет вскоре объяснен). Рекурсивная функция factorial сначала проверяет, истинно ли условие завершения рекурсии, т.е. меньше или равно 1 значение number. Если действительно number меньше или равно 1, factorial возвращает 1, никаких дальнейших рекурсий не нужно и программа завершает свою работу. Если number больше 1, оператор

return number * factorial (number - 1);