не впадать в рекурсию что это значит
Как работает рекурсия – объяснение в блок-схемах и видео
Представляю вашему вниманию перевод статьи Beau Carnes How Recursion Works — explained with flowcharts and a video.
«Для того чтобы понять рекурсию, надо сначала понять рекурсию»
Рекурсию порой сложно понять, особенно новичкам в программировании. Если говорить просто, то рекурсия – это функция, которая сама вызывает себя. Но давайте попробую объяснить на примере.
Представьте, что вы пытаетесь открыть дверь в спальню, а она закрыта. Ваш трехлетний сынок появляется из-за угла и говорит, что единственный ключ спрятан в коробке. Вы опаздываете на работу и Вам действительно нужно попасть в комнату и взять вашу рубашку.
Вы открываете коробку только чтобы найти… еще больше коробок. Коробки внутри коробок и вы не знаете, в какой из них Ваш ключ. Вам срочно нужна рубашка, так что вам надо придумать хороший алгоритм и найти ключ.
Есть два основных подхода в создании алгоритма для решения данной проблемы: итеративный и рекурсивный. Вот блок-схемы этих подходов:
Какой подход для Вас проще?
В первом подходе используется цикл while. Т.е. пока стопка коробок полная, хватай следующую коробку и смотри внутрь нее. Ниже немного псевдокода на Javascript, который отражает то, что происходит (Псевдокод написан как код, но больше похожий на человеческий язык).
В другом подходе используется рекурсия. Помните, рекурсия – это когда функция вызывает саму себя. Вот второй вариант в псевдокоде:
Оба подхода выполняют одно и тоже. Основный смысл в использовании рекурсивного подхода в том, что однажды поняв, вы сможете легко его читать. В действительности нет никакого выигрыша в производительности от использования рекурсии. Порой итеративный подход с циклами будет работать быстрее, но простота рекурсии иногда предпочтительнее.
Поскольку рекурсия используется во многих алгоритмах, очень важно понять как она работает. Если рекурсия до сих пор не кажется Вам простой, не беспокойтесь: Я собираюсь пройтись еще по нескольким примерам.
Граничный и рекурсивный случай
То, что Вам необходимо принять во внимание при написании рекурсивной функции – это бесконечный цикл, т.е. когда функция вызывает саму себя… и никогда не может остановиться.
Допустим, Вы хотите написать функцию подсчета. Вы можете написать ее рекурсивно на Javascript, к примеру:
Эта функция будет считать до бесконечности. Так что, если Вы вдруг запустили код с бесконечным циклом, остановите его сочетанием клавиш «Ctrl-C». (Или, работая к примеру в CodePen, это можно сделать, добавив “?turn_off_js=true” в конце URL.)
Рекурсивная функция всегда должна знать, когда ей нужно остановиться. В рекурсивной функции всегда есть два случая: рекурсивный и граничный случаи. Рекурсивный случай – когда функция вызывает саму себя, а граничный – когда функция перестает себя вызывать. Наличие граничного случая и предотвращает зацикливание.
И снова функция подсчета, только уже с граничным случаем:
То, что происходит в этой функции может и не быть абсолютно очевидным. Я поясню, что произойдет, когда вы вызовете функцию и передадите в нее цифру 5.
Сначала мы выведем цифру 5, используя команду Console.Log. Т.к. 5 не меньше или равно 1, то мы перейдем в блок else. Здесь мы снова вызовем функцию и передадим в нее цифру 4 (т.к. 5 – 1 = 4).
Мы выведем цифру 4. И снова i не меньше или равно 1, так что мы переходим в блок else и передаем цифру 3. Это продолжается, пока i не станет равным 1. И когда это случится мы выведем в консоль 1 и i станет меньше или равно 1. Наконец мы зайдем в блок с ключевым словом return и выйдем из функции.
Стек вызовов
Рекурсивные функции используют так называемый «Стек вызовов». Когда программа вызывает функцию, функция отправляется на верх стека вызовов. Это похоже на стопку книг, вы добавляете одну вещь за одни раз. Затем, когда вы готовы снять что-то обратно, вы всегда снимаете верхний элемент.
Я продемонстрирую Вам стек вызовов в действии, используя функцию подсчета факториала. Factorial(5) пишется как 5! и рассчитывается как 5! = 5*4*3*2*1. Вот рекурсивная функция для подсчета факториала числа:
Теперь, давайте посмотрим что же происходит, когда вы вызываете fact(3). Ниже приведена иллюстрация в которой шаг за шагом показано, что происходит в стеке. Самая верхняя коробка в стеке говорит Вам, что вызывать функции fact, на которой вы остановились в данный момент:
Заметили, как каждое обращение к функции fact содержит свою собственную копию x. Это очень важное условие для работы рекурсии. Вы не можете получить доступ к другой копии функции от x.
Нашли уже ключ?
Давайте кратенько вернемся к первоначальному примеру поиска ключа в коробках. Помните, что первым был итеративный подход с использованием циклов? Согласно этому подходу Вы создаете стопку коробок для поиска, поэтому всегда знаете в каких коробках вы еще не искали.
Но в рекурсивном подходе нет стопки. Так как тогда алгоритм понимает в какой коробке следует искать? Ответ: «Стопка коробок» сохраняется в стеке. Формируется стек из наполовину выполненных обращений к функции, каждое из которых содержит свой наполовину выполненный список из коробок для просмотра. Стек следит за стопкой коробок для Вас!
И так, спасибо рекурсии, Вы наконец смогли найти свой ключ и взять рубашку!
Вы также можете посмотреть мое пятиминутное видео про рекурсию. Оно должно усилить понимание, приведенных здесь концепций.
Заключение от автора
Надеюсь, что статья внесла немного больше ясности в Ваше понимание рекурсии в программировании. Основой для статьи послужил урок в моем новом видео курсе от Manning Publications под названием «Algorithms in Motion». И курс и статься написаны по замечательной книге «Grokking Algorithms», автором которой является Adit Bhargava, кем и были нарисованы все эти замечательные иллюстрации.
И наконец, чтобы действительно закрепить свои знания о рекурсии, Вы должны прочитать эту статью, как минимум, еще раз.
От себя хочу добавить, что с интересом наблюдаю за статьями и видеоуроками Beau Carnes, и надеюсь что Вам тоже понравилась статья и в особенности эти действительно замечательные иллюстрации из книги A. Bhargav «Grokking Algorithms».
Почему рекурсия — это все-таки зло? И как не нужно писать программки на собеседовании в Google?
Недавно столкнулся с интересной ситуацией, связанной с тем в какие неприятности можно попасть, написав совсем простой, маленький код, использующий рекурсию.
Классическим примером рекурсии является определение чисел Фибоначчи. N-е число Фибоначчи определяется как сумма (N-1)-го и (N-2)-го числа Фибоначчи. Исключение составляют первые два числа Фибоначчи — по определению первое равно 0, а второе равно 1.
F[0] = 0,
F[1] = 1,
F[n] = F[n-2]+F[n-1], для n >= 2.
Итак, два следующих алгоритма (код написан на языке Java) для нахождения n-го числа Фибоначчи являются очевидными. Первый из них рекурсивный и второй нерекурсивный.
long recursivefib(int n) <
if (n
Предположим, что индекс n не превышает 161 004 — это максимальное число Фибоначчи, помещающееся в 63 старших бита (не считая 0-го знакового) типа long и равное 7 829 159 639 441 890 064.
Далее если вы попробуете посчитать 5-е число Фибоначчи:
void main(String[] args) <
System.out.println(recursivefib(5));
System.out.println(nonrecursivefib(5));
>
void main(String[] args) <
System.out.println(recursivefib(8));
System.out.println(nonrecursivefib(8));
>
void main(String[] args) <
System.out.println(recursivefib(13));
System.out.println(nonrecursivefib(13));
>
то скорее всего не увидите разницы.
Но если вы попробуете посчитать 43-е число Фибоначчи:
void main(String[] args) <
System.out.println(recursivefib(43));
System.out.println(nonrecursivefib(43));
>
то наверное что-то заподозрите, а когда вы попробуете посчитать 65-е число Фибоначчи:
void main(String[] args) <
System.out.println(recursivefib(65));
System.out.println(nonrecursivefib(65));
>
то поймете в чем проблема, и что проблема не в переполнении стека, а программа просто зависла и зависла так где-то лет на 200. Мы в своей собственной жизни не увидим 65-е число Фибоначчи, его увидят наши далекие пра пра пра… правнуки.
Оказывается, что если, очевидно, порядок сложности второго нерекурсивного алгоритма равен O(n), где n-номер искомого числа Фибоначчи, то порядок сложности рекурсивного алгоритма, неочевидно, равен O(2^n) два в степени n.
Почему в рекурсивном алгоритме выполняется порядка 2^n операций — вам предлагается разобраться самостоятельно.
Наверное полностью отказываться от рекурсии не нужно, потому что самые эффективные алгоритмы часто используют рекурсию, например быстрая сортировка, сортировка слиянием, алгоритмы для работы с деревьями и графами, но то, что с рекурсией нужно быть осторожным, так это точно.
Кстати, есть и более быстрые громоздкие алгоритмы для вычисления чисел Фибоначчи, имеющие порядок сложности O(log2(n)).
И последнее, что хочется сказать, так это то, что никогда! никогда! не нужно писать такие «эффективные» рекурсивные программки на собеседовании в Google.
Рекурсия. Беглый взгляд
Ниже речь пойдёт о старушке рекурсии, которую неплохо бы представлять, понимать и применять.
Примечание: Данная небольшая статья написана для беглого ознакомления с рекурсией, некоторыми примерами её применения и опасностями.
Определение
Для начала стоит сказать, что рекурсия относится не только к программированию. Рекурсия — это общее понятие, которое может быть присуще чему угодно и встречаться в повседневной жизни, но больше всего она распространена в информатике и математике. Для программистов же умение применять рекурсию — большой плюс в коллекцию полезных навыков.
Самая большая глупость — это делать то же самое и надеяться на другой результат.
Под рекурсией понимают процесс повторения элементов самоподобным образом. Объект обладает рекурсией, если он является частью самого себя.
Частным случаем рекурсии является хвостовая рекурсия. Если любой рекурсивный вызов является последней операцией перед возвратом из функции, то это оно.
Некоторые примеры
Рекурсию надо бы понять, а определение для этого подходит хуже, чем наглядные примеры. Для лучшего понимания, конечно, всё же следует прочитать определение, посмотреть на пример, снова прочитать определение и снова посмотреть на пример… Повторять, пока не придёт осознание.
Отличный пример вы можете найти тут.
Самое известное программисту применение рекурсии — задачи на вычисление чисел Фибоначчи или факториала. Давайте покажем, как это реализовать на языке C:
Тут же стоит отметить, что декларативная парадигма, в частности парадигма логического программирования, намного лучше позволяет понять рекурсию, так как там это обычное дело.
Fork-бомба
Примечание: Рекурсивное создание процессов крайне быстро (из-за экспоненциального роста их количества) заполняет таблицу процессов, что достаточно опасно для системы.
Reboot кнопкой после такого делать немного не приятно.
Для математика первой ассоциацией, скорее всего, будет фрактал. Фракталы прекрасны и приятно для глаза показывают свойства самоподобия.
Самые известные фракталы:
Ну и в повседневной жизни классическим примером являются два зеркала, поставленных друг напротив друга.
Углубимся глубже
Проста ли рекурсия? Однозначно нет. На вид кажется, что всё просто, однако рекурсия таит в себе опасности (А иногда она просто не понятна).
Вернёмся к примеру с вычислением чисел Фибоначчи. Сразу заметим, что возвращаемым результатом функции является вызов этой же функции, а если быть точнее, то сумма результатов вызова двух функций (именно поэтому рекурсия не хвостовая). Становится понятно, что второй вызов не произойдёт, пока не завершится первый (в котором также будет вызов двух функций). Тут же пытливый ум заметит, что из рекурсивной функции должен существовать «нормальный» выход, без самовызова, иначе мы познакомимся с переполнением стека вызовов — это один из ключевых моментов, который стоит держать в голове при работе с функциями вызывающими сами себя.
Заметим, что дерево вызовов получится большим, но максимальное количество вызовов в стеке будет заметно меньше (N-1 при N > 2, соответственно).
Рекурсивные алгоритмы довольно-таки часто встречаются при работе с деревьями, сортировками и задачами на графах. Так что, чтобы лучше вникнуть нужна практика и для этого не плохо подходит вышеупомянутое (в частности, бинарные или общие деревья. Их реализация не так сложна, а опыт работы с рекурсией получится не плохой).
Помимо этого хотелось бы упомянуть Ханойские башни, которые также отлично подойдут для ознакомления с рекурсивными задачами. На Хабре также был отличный разбор этой игры.
Для полноты картины обязательно надо упомянуть о борьбе с рекурсией.
Повышается производительность. Но это не значит, что с ней просто необходимо бороться, ведь применение рекурсии очевиднее, проще и приятнее, чем итерационные варианты.
Под силу ли побороть любую рекурсию?
Однозначно да. Любой рекурсивный алгоритм можно переписать без использования рекурсии, а хвостовую рекурсию же очень легко перевести на итерацию (чем и занимаются некоторые компиляторы для оптимизации). Это также относится и к итерационным алгоритмам.
Самый известный способ — это использование стека. Здесь подробнее, для интересующихся.
Заключение
Спасибо за прочтение статьи. Надеюсь, что большинство не знакомых с рекурсией получили базовое представление о ней, а от знающих людей, конечно, хочется услышать дополнения и замечания в комментариях. Не бойтесь рекурсии и не переполняйте стек!
UPD: Добавлен корректный пример хвостовой рекурсии.
Рекурсия сознания — ловушка мышления и барьер прогрессу. Исторический очерк
С момента появления языка как второй сигнальной системы — инструмента для мышления и общения, человечество получило критическое преимущество перед всеми другими живыми существами, поведение которых управляется системами первого уровня и поэтому принципиально ограничено в уровнях абстрагирования.
Но, давая человеку инструмент огромной силы, язык и абстрактное мышления в то же время создают ограничения и ловушки, ведущие к проблемам, конфликтам и деструктивному поведению. Чем человечество последние 5000 лет в основном и занимается. (Может и 500 000, но нет письменных свидетельств).
Большинство войн, конфликтов, ссор и убийств происходят или оправдываются идейнымы, идеологическими, религиозными, политическими и другим абстрактными причинами, лежащими в сфере идей и информации, а не материального мира. И прежде чем война, конфликт, ссора приводит к реальным действиям, ей всегда предшествует этап намерения, замысла, подготовки, планирования, нагнетания, организации, проходящий на уровне слов и информации.
Источник и инструмент всех войн, убийств, дискриминации, инквизиции, угнетения — язык.
Но он же — инструмент науки, культуры, прогресса, развития, цивилизации.
И виноват в проблемах не инструмент, а незрелое мышление, сознание и культура тех, кто его использует.
Еще с античных времен лучшие умы это понимали и пытались исправить.
Наибольший вклад в развитие цивилизации внес, конечно, Аристотель. Разработка формальной логики дала хоть и простой, но все-же общепризнанный и легко применимый инструмент разрешения споров и поиска истины. По сути, это создало основу, фундамент всей Западной цивилизации.
Хотя до сих пор формальную логику понимает и умеет пользоваться, по разным оценкам, не более 1-10% населения планеты.
И уже в те времена философы и мыслители, используя этот инструмент, натолкнулись на ловушку рекурсии, лежащую в основе значительной части парадоксов, апорий и логических противоречий.
Парадокс лжеца, апории Зенона, множество других парадоксов — в основе всех одна и та же мыслительная ошибка. Считать, что высказывание, направленное само на себя, ничем не отличается от высказываний, имеющих другое основание.
«Это высказывание написано на русском языке», «Это высказывание истинное» — рекурсивные высказывания без парадокса.
«Это высказывание ложное» — пример парадоксальной рекурсии.
Но выхода так и не нашли.
Философы средневековья и Возрождения потратили тысячи часов на решения подобных и еще более схоластических вопросов, но единственным продуктом были все более и более абстрактные теории, в которых авторы избретали новые названия для старых категорий и все больше в них запутывались.
Как ехидно заметил Пуанкаре,
«…все, что ученый на самом деле создает — это язык, которым он это возвещает.»
Выходы из логического тупика начали находить только по мере развития естественных и точных наук где-то к началу XX века. Нашлись они, как и можно было ожидать, представителями самой формальной и точной науки — математики.
Б. Рассел в своих «Основаниях математики» (1903) показал, что класс не может включать сам себя в виде элемента класса, а тип не может быть сам себе подтипом. Аналогично множество, включающее само себя в качестве подмножества, обладает особыми свойствами и не может рассматриваться в ряду обычных множеств, не приводя к логическим ошибкам указанного типа.
Наиболее полно и красиво разобрался с этой проблемой Курт Гёдель, опубликовавший в 1931 году свои знаменитые теоремы о неполноте:
«Любая формальная система аксиом содержит неразрешенные предположения»
«Логическая полнота (или неполнота) любой системы аксиом не может быть доказана в рамках этой системы. Для ее доказательства или опровержения требуются дополнительные аксиомы (усиление системы)».
Доказательство этой вроде бы простой истины, с которой философы не могли справиться тысячелетиями, не прошло даром для ученого — в этой борьбе он подорвал свой разум, поймал серьезную паранойю и умер от голода и истощения, всеми забытый и оставленный.
Так что будьте осторожны с рекурсией, это отражение отражений, из которого можно и не вернуться!
Работы Гёделя оказали серьезное влияние на все точные науки, не только математику.
«…невозможно решить проблему на том же уровне, на котором она возникла. Нужно стать выше этой проблемы, поднявшись на следующий уровень».
По сути, это та же теорема о неполноте, выраженная в более абстрактной форме.
Не обошли вниманием эту тему и отечественные исследователи.
«…действительность, понять которую ставит своей задачей ум, эта действительность является в значительной степени скрытой от него. Она, как говорится, спрятана за семью замками. Между действительностью и умом стоит и должен стоять целый ряд сигналов, которые совершенно заслоняют эту действительность.»
«…Что такое наши слова, которыми мы описываем факты, как не новые сигналы, которые могут, в свою очередь, затемнить, исказить истину.»
«…словесная передача этим другим обстановки всего его дела не соответствует, не воспроизводит точно и полно действительности.»
«…когда вы начнете оперировать с теми словесными сигналами ― этикетками, которые вы поставили на место фактов, ― то здесь фальсификация действительности может достигать огромнейших размеров.»
Это описание тех же уровней абстрагирования, и принципов отношения реальности, языка и сознания, что показаны А. Коржибским на его Структурном Дифференциале в книге «Science and Sanity» в 1933 году, и даже почти теми же самыми словами.
Но, благодаря картинкам и материальной модели, идеи Коржибского все-таки поняли в тот момент несколько человек, (как, впрочем, и Эйнштейна сразу после публикации Теории Относительности) и в результате этого появились и НЛП, и Дианетика с Сайентологией, и некоторые направления позитивной психологии, маркетинга, рекламы, политтехнологий, пропаганды и других инструментов работы с сознанием. К сожалению, на первоисточник авторы этих разработок предпочитают не ссылаться, чтобы «не палить тему».
Но, по крайней мере, идея «Карта — не территория» вышла за рамки научных статей и стала достоянием широкого круга людей и достаточно общепринятым фактом.
А И. Павлов опередил эпоху, и в то непростое время, его глубоко не понял, наверное, вообще никто.
И даже сейчас, через почти 100 лет после этих исследований, публикаций и выступлений, контролировать свое абстрагирование, отслеживать уровни, избегать рекурсии и не попадать в уровневые ловушки умеет не так много людей, на порядки меньше, чем владеют формальной логикой.
Хорошо, что на этом ресурсе собираются люди, близкие к ИТ и программированию, которых с первых шагов в профессии обучают логике, структуре и строгости мышления и которые знают, что программа не должна вызывать сама себя в качестве подпрограммы, массив не может включать сам себя в качестве элемента массива, а переменная не может принимать в качестве значения сама себя.
Но то, что для программистов самоочевидно, совсем не так в других областях науки и деятельности.
Миллионы людей продолжают пытаться выучить язык с помощью языкового описания языка (грамматики), не замечая, что они попадают в логическую ловушку рекурсии без шанса выбраться оттуда.
Когда вы не знаете, как построить предложение на другом языке, чтобы выразить нужную вам мысль, вы сказать этого не можете.
Но когда вы выучили правило и знаете, как построить это предложение, вы все равно сказать это не сможете.
Потому что та зона мозга, которая должна управлять этим действием, занята мыслями о том, как это сделать (правилами).
Рекурсия в чистом виде.
Но этого почти никто не замечает, кроме психологов-физиологов, которые давно используют такой механизм блокировки речи для исследований языка и мышления.
Психолингвист и методист Стивен Крашен сформулировал эту идею в виде «Гипотезы грамматического монитора». Он утверждает, что грамматика не может служить инструментом для порождения устной речи, а только как монитор для последующего контроля и коррекции. Но, исходя из фактов, полученных другими науками, это никакая не гипотеза, а аксиома, следующая из законов логики, математики, психологии, физиологии. И только фрагментация и сегментация наук и все более узкая специализация ученых не позволяет это заметить.
Аналогичные проблемы с бесконтрольным абстрагированием и злоупотреблением рекурсией можно найти в сфере психологии, когда начинают исследовать мышление с помощью мышления, в методологии, когда пытаются управлять управлением с помощью управления, в философии, которая множит абстрактные сущности без всякого страха перед Оккамом, и во многих других сферах человеческой деятельности.
И задача технарей, айтишников, представителей точных наук — помочь выбраться из рекурсивной ловушки, дать инструменты структурирования мышления, научить избегать рекурсии и совместно с гуманитариями разработать новые продукты и инструменты, решающие насущные задачи и лишенные рекурсивных замыканий.
Одним из таких инструментов может быть Структурно-Визуальный метод, разработанный автором этой статьи. Он предлагает для структурирования знаний в некоторой предметной области использовать визуальное представление структуры с использованием цвета для кодирования ограниченного количества смыслов самого верхнего уровня абстракции.
С помощью этого метода были получены некоторые интересные схемы и модели для разных предметных областей — ИТ, управления, психологии, лингвистики, педагогики, изучения иностранных языков, а их практическое применение оказалось довольно результативным и перспективным.
Но об этом в следующих статьях, если это будет интересно читателям Хабра.
Успехов вам в любой деятельности и осознанного абстрагирования!