Этот шаг будет посвящен рекурсии.
Под рекурсией будем понимать обращение функции при вычислении ее значения к себе самой. Использование рекурсивного метода вычисления нужно избегать, когда есть очевидное итерационное решение. Рекурсивные алгоритмы эффективны в тех задачах, где рекурсия использована в определении обрабатываемых данных. Поэтому изучение рекурсивных методов нужно проводить, вводя такие динамические структуры данных, как стеки, деревья, списки, очереди и, в особенности, данные с рекурсивной структурой. Здесь же рассмотрим только основные возможности использования рекурсии.
Различают прямую и косвенную рекурсии. Функция называется косвенно рекурсивной в том случае, если она содержит обращение к другой функции, содержащей прямой или косвенный вызов определяемой (первой) функции. В этом случае по тексту определения функции ее рекурсивность (косвенная) может быть не видна. Если в теле функции явно используется вызов этой функции, то имеет место прямая рекурсия.
Пример 1.
#include<iostream.h> void main () { void f1(); /* ----------------------------------- */ f1(); } void f1() { char ch; /* ----------------------------------- */ cout << "Укажите произвольный символ. "; cout << "Q - признак конца работы.\n"; cin >> ch; cout << " Так! Вы указали " << ch << "! \n"; if (ch!='Q') f1(); }
Результат работы программы:
Укажите произвольный символ. Q - признак конца работы. p Так! Вы указали p! Укажите произвольный символ. Q - признак конца работы. ! Так! Вы указали !! Укажите произвольный символ. Q - признак конца работы. Q Так! Вы указали Q!
Замечание. Функция main() не может вызываться не только рекурсивно, но также из других функций.
Цикл, который мы создали, используя рекурсию, отличается от циклов while и do...while. Когда функция f1() вызывает сама себя, не происходит передачи управления на ее начало. Вместо этого в памяти машины создаются копии всего набора переменных функции f1(). Если вывести на печать адреса переменных в обычном цикле, то можно заметить, что эти адреса не изменяются от итерации к итерации. Что же касается рассматриваемого здесь цикла, то в нем адрес используемой переменной меняется, поскольку при каждом выполнении тела цикла создается новая копия переменной ch. Если программа циклически выполняется 20 раз, то будет создано 20 различных копий переменной, каждая из которых носит имя ch, но имеет свой собственный адрес.
Пример 2.
Программа 1.
#include<iostream.h> void main () { void f1(); /* ----------------------------------- */ f1(); } void f1() { char ch; /* ----------------------------------- */ cout << "Укажите произвольный символ. "; cout << "Q - признак конца работы.\n"; cin >> ch; cout << " Aдрес ch=" << ch << " равен " << (void*)&ch << endl; if (ch!='Q') f1(); }
Результат работы программы:
Укажите произвольный символ. Q - признак концa работы. p Aдрес ch=A равен 0x55d72361 Укажите произвольный символ. Q - признак концa работы. a Aдрес ch=a равен 0x55d7234f Укажите произвольный символ. Q - признак концa работы. Q Aдрес ch=Q равен 0x55d7233d
#include<iostream.h> void main () { char ch; while (ch!='Q') { cout << "Укажите произвольный символ. "; cout << "Q - признак конца работы.\n"; cin >> ch; cout << " Aдрес ch=" << ch << " равен " << (void*)&ch << endl; } }
Результат работы программы:
Укажите произвольный символ. Q - признак концa работы. p Aдрес ch=p равен 0x562f2369 Укажите произвольный символ. Q - признак концa работы. a Aдрес ch=a равен 0x562f2369 Укажите произвольный символ. Q - признак концa работы. i Aдрес ch=i равен 0x562f2369 Укажите произвольный символ. Q - признак концa работы. Q Aдрес ch=Q равен 0x562f2369
Мы закончили изложение материала, связанного с рекурсией.
На следующем шаге мы приведем несколько примеров, иллюстрирующих
изученный на
этих шагах материал.
