лекцияВ этом мире есть мало людей, которые выучив "что такое рекурсия" остаются равнодушными к этому определению. Часть студентов, увидев впервые такую возможность - восторгаются, потому что такой подход дает возможность решать просто и элегантно задачи, которые были весьма сложными, без рекурсии, НО! Есть и другая часть, которая почему-то сразу решает, что "это я не пойму никогда, поэтому - нафик" и они действительно, дав себе такую установку, уже не способны понять эту тему. Вторым мне всегда хотелось задать вопрос: "насколько вы уверены, что выбрали тот факультет, который вам нужен?" Программист, который боится нового - это все равно, как скалолаз, который боится высоты.
Я помню себя, когда я учился. У меня был друг, он учился со мной, но отличался тем, что он уже был программистом, с опытом работы 3 года, а в универ пришел ради бумажки. Услышав слово "рекурсия", и увидев, как люди произносят с дрожащими коленками: "вот, скоро будем учить рекурсию" (при этом у них читался дикий ужас в глазах), я спросил у него: "а что такое рекурсия" и мой друг мне ответил: "это функция, которая вызывает саму себя".
Сейчас, по прошествии лет, я понимаю, что подобный ответ был очень простой и неточный, точно так же, как если меня спросят: "а что такое Мона Лиза", а я отвечу: "портрет улыбающейся бабы". Вроде и не соврал, да? Но..... насколько я точно описал то, что висит в Лувре, то, чем восторгаются миллионы, то, что считается основным шедевром живописи?....
Рекурсия - это функция, которая вызывает саму себя, это правда (точнее - частичная правда, потому что бывают "сложные рекурсии", в которых это не совсем так). НО! Это намного больше! Это умение "мыслить наоборот", "ездить задним ходом"... то есть - это почти искусство! Приведу классический пример: вычисление факториала.
Здесь стоит напомнить, что такое "факториал"? Возможно, что немногие это помнят. Факториал - это математическое действие, такое же, как извлечение корня, возведение в степень, умножение и пр. Записывается оно так: 5! - то есть "факториал из 5-ти". Ставится цифра, из которой надо вычислить факториал, а после нее - восклицательный знак. Чему оно равно?
5! = 5 * 4 * 3 * 2 * 1 // то есть: 120
еще пример - факториал из 4
4! = 4 * 3 * 2 * 1 // то есть: 24
Я специально записал одно под другим. Давайте взглянем внимательно на первый пример: что такое 5! ? Это по-сути 5 * 4! То есть, зная что 4! это 24, нам не нужно вычислять "весь путь", нам достаточно умножить 5 на 24. К чему я это веду? Да к тому, что это, в принципе, и есть определение факториала! Более "математическим" языком это выглядит так:
Для человека, не изучавшего серьезно математику, такое определение выглядит пугающим, но давайте попробуем разобрать эту запись, она не так страшна и если знать, как на нее смотреть - очень понятна.
Что мы видим? В начале написано, что n! (где n это число, из которого мы хотим вычислить факториал) равно: и вот тут теперь 2 возможности, чему равно n!: нас в начале "спрашивают", а чему равно n ? Если n равно нулю, тогда n! равно 1, а если n больше нуля, тогда n! равно нашему n умноженному, на факториал из числа, на один меньше, чем n.
То есть, предполагается такой способ вычисления. Давайте разберем на примере 3!
Мы подходим с 3! и спрашиваем чему оно равно? То есть, в нашем случае, n = 3. Нам говорят: n > 0, то есть: 3! = 3 * 2! (типа, что не понятно?) Отличненько, говорим мы... а чему же равно 2! ? И приходим к той же самой формуле (и это важно) - нам говорят: n > 0, то есть 2! = 2 * 1!.....
Ладно.... говорим мы.... а чему равно 1! ? Нам говорят: n > 0, то есть 1! = 1 * 0!..... да вы задолбали, долбанные математики! А чему равен 0! ? Вот! Отвечают они нам: в этом случае у нас есть сиюсекундный ответ! n = 0, то есть 0! = 1
Мы как бы спустились на самое дно, дорылись до однозначного ответа, и теперь надо "собрать" свои знания. У нас был вопрос чему равен 0! и мы теперь знаем, что это равно 1. Но откуда возник этот вопрос? А! Мы вроде хотели определить, чему равен 1! нам тогда сказали, что это равно 1 * 0!, но теперь мы знаем, что 0! это 1, то есть, 1! = 1 * 1
НО! Вопрос "чему равен 1!" возник потому, что мы спрашивали чему равен 2! и нам сказали, что 2! = 2 * 1! но мы то теперь знаем, чему равен 1! то есть, легко можно вычислить, чему равен 2! .... и так далее.... надеюсь понятно.
Давайте вглядимся, а чем мы собственно занимались? Мы как бы "вкапывались" сначала внутрь, а потом, там, на самом дне, получив однозначный ответ, возвращались с ним назад, по той же дороге, собирая по пути результаты предыдущих действий. И при этом - мы пользовались одной и той же функцией! То есть функция как бы "вызывала саму себя", не так ли? Опа.... знакомый звон))))
Как же вычисляется факториал в программном коде? Так же просто:
Результат:
Давайте разберем:
Пользователь ввел цифру 5.
вызов 1: Из функции main мы попадаем в функцию factorial, х = 5.
х == 0 ? - нет
тогда вычислим чему равен факториал х-1 и сохраним результат в у
вызов 2: Вызываем функцию factorial, х = 4.
х == 0 ? - нет
тогда вычислим чему равен факториал х-1 и сохраним результат в у
вызов 3: Вызываем функцию factorial, х = 3.
х == 0 ? - нет
тогда вычислим чему равен факториал х-1 и сохраним результат в у
вызов 4: Вызываем функцию factorial, х = 2.
х == 0 ? - нет
тогда вычислим чему равен факториал х-1 и сохраним результат в у
вызов 5: Вызываем функцию factorial, х = 1.
х == 0 ? - нет
тогда вычислим чему равен факториал х-1 и сохраним результат в у
вызов 6: Вызываем функцию factorial, х = 0.
х == 0 ? - да
вернем 1 в вызов 5. В итоге в у лежит 1
умножим х * у, то есть, (смотрим вызов 5) 1 * 1
и положим результат в ret. Вернем ret, который равен 1 в вызов 4
в итоге, в у от 4-го вызова мы положили 1
умножим х * у, то есть, (смотрим вызов 4) 2 * 1
и положим результат в ret. Вернем ret, который равен 2 в вызов 3
в итоге, в у от 3-го вызова мы положили 2
умножим х * у, то есть, (смотрим вызов 3) 3 * 2
и положим результат в ret. Вернем ret, который равен 6 в вызов 2
в итоге, в у от 2-го вызова мы положили 6
умножим х * у, то есть, (смотрим вызов 2) 4 * 6
и положим результат в ret. Вернем ret, который равен 24 в вызов 1
в итоге, в у от 2-го вызова мы положили 24
умножим х * у, то есть, (смотрим вызов 1) 5 * 24
и положим результат в ret. Вернем ret, который равен 120 в вызов main
в итоге, в x от вызова main мы получили конечный ответ: 120
Теперь немного о терминах:
В нашем примере, мы закончили "углубляться" в вызовы и начали возвращаться на условии х == 0. Это условие называется "условие остановки".
Нам пришлось сделать 6 вызовов рекурсивной функции. Это число называется "глубина рекурсии".
То есть, мы сейчас имплементировали функцию факториал точно по ее определению! Можно ли, в этом случае, заменить рекурсию циклом? Да, можно! Теория гласит, что ЛЮБУЮ рекурсию можно заменить циклом! Единственный вопрос: насколько это будет менее красиво и более сложно в понимании и обработке?
Чтобы понять, к чему я клоню, мы рассмотрим пример. Программа, которую мы напишем, получает число от пользователя и высвечивает на экран бинарный вид этого числа. Я не буду писать main, потому что там нет ничего интересного, я напишу саму функцию. Для начала, я имплементирую ее в цикле:
Что мы имеем? Мы имеем 3 цикла! И все это только потому, что нам нужно писать результат в обратном порядке.... а как бы эта же функция выглядела, если бы мы имплементировали ее в рекурсии? Вы будете смеяться......
Это всё! Согласитесь, что это намного проще, элегантней и понятней! Не нужно никаких "буферов", (которые тем более, в моем решении, почему-то предполагают, что число не будет содержать более 64 символов.... это конечно же можно переписать по-другому, заморачиваясь проверками "не вышли ли мы за границу буфера", и если да, то мы сделаем новую аллокацию....) не нужно 3 прохода по этому буферу, не нужно делать непонятных телодвижений.... Рекурсия, которая пришла нам на помощь, помогла решить задачу просто и элегантно!
Конечно же, рекурсия не панацея. Не стоит, каждый раз, что нам нужен цикл, писать рекурсию. Нужно выбирать между подходами и отдавать предпочтение тому, который более правильный в такой ситуации!
Сложная (косвенная) рекурсия
Сложная рекурсия, это несколько функций, которые вызывают друг друга "по кругу". То есть, если существует функция foo(), которая в своем коде зовет функцию bar(), а в функции bar(), в свою очередь вызывается foo(), то с одной стороны - это рекурсивное поведение, но с другой - прямого вызова foo() из самой foo() нет, она как бы "косвенно" вызывается через bar(). Такая рекурсия называется "сложной" или другое имя "косвенной".
То есть, происходит примерно следующее:
void foo ( ) {
// код
bar ( );
// код
}
void bar ( ) {
// код
foo ( );
// код
}
Для чего такое применяют? Ну, первый пример, который приходит мне в голову, это проход по папкам в компьютере, в которых лежат архивы (например rar). Я не буду имплементировать это, потому что не вижу в этом смысла: кода много, а ничего нового, в плане рекурсии, мы не увидим, чтобы не смогла показать моя схема выше, я лишь расскажу этот алгоритм в теории:
Представьте, что у вас есть папка, в которой лежат архивы, которые вам нужно распаковать. Функция foo() умеет зайти в папку и найти там файл архива, который она передаст в bar() для распаковки. bar() распаковывает архив в папку и в свою очередь зовет foo(), чтобы та проверила нет ли внутри еще одного архива. Естественно, foo(), найдя архив, вновь позовет bar()..... думаю - идея понятна.
Как правило, в такой игре участвуют две функции, но никто не запрещал создать такую тройку, четверку и так далее. Например, я недавно задался целью написать программу, которая умеет скачивать фотографии с галерей в инете. Мне очень хотелось скачать одну классную галерею с фотографиями Бритни и я начал писать. Строение галереи такое:
В категории фотографий (например - "Выступления") есть разделы по годам, в этих разделах по годам - есть альбомы конкретных выступлений. У меня было 3 функции, которые раскручивали эту карусель: manager(), download(), parser().
manager() получала ссылку, регистрировала ее (не важно по какой причине, скажем - для отчетности) и вызывала функцию download()
download(), в свою очередь умела по этой ссылке полезть, и если это был, к примеру, раздел, то она получала этот раздел к себе, в виде кода HTML, далее этот код она "скармливала" функции parser().
parser() умела понять код HTML, найти в нем ссылки на альбомы и передать их в функцию manager(), где карусель повторялась. И так, раскручивая, словно по спирали, я "докапывался" до ссылок на сами фотографии.
Не могу сказать, что это тривиальный алгоритм, но задача стояла так, что без косвенной рекурсии было бы ОЧЕНЬ сложно такое решить.
Опасность рекурсии
Рекурсивные функции - очень расточительная штука для памяти, потому что с каждым новым вызовом рекурсией "саму себя" происходит ПОЛНОЕ копирование всех переменных, и прочих вещей в стеке. Поэтому, в условиях программирования с ограниченным количеством памяти (например, программирование на каких-нибудь очень примитивных компьютерах, типа свичей и прочей ерунды, то, что называется "программирование низкого уровня"), рекурсию не используют.
Из-за этого постоянного копирования содержимого стека, если программист не правильно задал условие остановки, возможно переполнение стека и как следствие - падения программы. Такая ошибка так и называется "Переполнение стека" (англ. "Stack overflow"). Будьте внимательны!
Статические переменные
В принципе, нельзя сказать, что тема статических переменных тесно связана с рекурсией, но ее частенько используют в рекурсии, и все же надо рассказать про это, поэтому, сделаю это здесь.
Статическая переменная, это такая переменная, которая инициализируется всего один раз, тогда, когда алгоритм впервые ее встречает. Если глобальная переменная объявлена статической, то она будет инициализирована еще до начала программы. Чтобы объявить переменную статической, перед ней пишут ключевое слово "static". Теперь, я на примере объясню что я сейчас написал, так как это может быть не совсем понятно из теоретического объяснения.
int main(){
// код
foo(); // первый вызов foo
// код
foo(); // второй вызов foo
}
void foo(void){
int i = 0;
i ++;
cout << "the i: " << i << endl;
}
В функции foo есть переменная i, при каждом вызове она получает значение 0, потом его увеличивают на один, то есть каждый раз на экран будет выведено "the i: 1". Это поведение нам знакомо и оно логично. НО! Стоит изменить код и написать перед i слово static, как поведение поменяется! То есть:
int main(){
// код
foo(); // первый вызов foo
// код
foo(); // второй вызов foo
}
void foo(void){
static int i = 0; // теперь i - статическая переменная! Эта строка выполнится всего ОДИН раз! (первый раз)
i ++;
cout << "the i: " << i << endl;
}
Теперь, при первом вызове распечатается строка "the i: 1", при втором "the i: 2" и так далее. То есть, При выходе из функции переменная не умрет, а продолжит существовать. А значит, она "запомнит" свое значение для следующего раза. Если переменная объявлена в рекурсии, то, как я говорил выше, при рекурсивном вызове все содержимое функции копируется в стеке, то есть - все, КРОМЕ этой переменной!
Домашнее задание
Напишите функцию void print_arr(int *arr, unsigned int size), получающую массив и его размер, которая распечатывает массив на экран. Позовите функцию несколько раз. Если вызов четный, то массив распечатывается с начала, при нечетном вызове массив распечатается с конца.
Требования:
1. Запрещено менять описание функции, то есть добавлять/убирать параметры.
2. Запрещено внутри функции print_arr использовать цикл.
3. Счет вызовов начинается с 1
Пример (3 вызова):
Массив:
{0, 1, 2, 3, 4}
результат вызова 1:
4 3 2 1 0
результат вызова 2:
0 1 2 3 4
результат вызова 3:
4 3 2 1 0
Удачи!