На простом английском языке, что такое рекурсия?

Идея рекурсии не очень распространена в реальном мире. Таким образом, это кажется немного запутанным для начинающих программистов. Хотя, думаю, они постепенно привыкают к этой концепции. Итак, что может быть хорошим объяснением для них, чтобы легко понять идею?

Чтобы объяснить рекурсию , я использую комбинацию разных объяснений, обычно для того, чтобы попытаться:

• объяснить концепцию,
• объясните, почему это важно,
• объясните как это получить.

Для начала, Wolfram | Alpha определяет его в более простых терминах, чем Википедия :

Выражение такое, что каждый член генерируется путем повторения определенной математической операции.

математика

Если ваш ученик (или человек, которого вы тоже объясняете, отныне я буду говорить ученик) имеет хоть какое-то математическое образование, он, очевидно, уже сталкивался с рекурсией, изучая серии и свои представления о рекурсивности и их рекуррентных отношениях .

Очень хороший способ начать - это продемонстрировать серию и сказать, что речь идет просто о рекурсии:

• математическая функция ...
• ... который вызывает себя для вычисления значения, соответствующего n-му элементу ...
• ... и который определяет некоторые границы.

Обычно, вы либо получаете «да, ну, что угодно» в лучшем случае, потому что они все еще не используют его, или, скорее всего, просто очень глубокий храп.

Примеры кодирования

В остальном, это на самом деле подробная версия того, что я представил в Дополнении к моему ответу на вопрос, на который вы указали относительно указателей (плохой каламбур).

На этом этапе мои ученики обычно знают, как распечатать что-то на экране. Предполагая, что мы используем C, они знают, как напечатать один символ, используя writeили printf. Они также знают о контурах управления.

Я обычно прибегаю к нескольким повторяющимся и простым проблемам программирования, пока они не получат:

• факторные операции,
• алфавитный принтер,
• принтер с обратным алфавитом,
• возведения операции.

Факториал

Факториал - это очень простая математическая концепция для понимания, и реализация очень близка к ее математическому представлению. Однако, они могут не получить это сначала.

алфавиты

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

^{Поклонники FP, пропустите тот факт, что печать материала в выходной поток пока является побочным эффектом ... Давайте не будем слишком раздражать на фронте FP. (Но если вы используете язык с поддержкой списков, не стесняйтесь объединять список на каждой итерации и просто печатать конечный результат. Но обычно я начинаю их с C, который, к сожалению, не самый лучший для такого рода проблем и концепций) ,}

Возведение

Проблема возведения в степень немного сложнее ( на данном этапе обучения). Очевидно, что концепция точно такая же, как и для факториала, и здесь нет дополнительной сложности ... за исключением того, что у вас есть несколько параметров. И этого обычно достаточно, чтобы сбить с толку людей и отбросить их с самого начала.

Его простая форма:

можно выразить так повторением:

Сильнее

После того, как эти простые проблемы были показаны И повторно реализованы в руководствах, вы можете выполнить несколько более сложные (но очень классические) упражнения:

• В Фибоначчи числа,
• Наибольший общий делитель ,
• Проблема 8-Куинс ,
• Игра Башни Ханоя ,
• И если у вас есть графическое окружение (или вы можете предоставить заглушки для кода или для вывода терминала, или они уже могут управлять этим), такие вещи, как:
  • Фрактал Снежинка Коха ,
  • Треугольник Серпинского .
• А для практических примеров рассмотрим написание:
  • алгоритм обхода дерева,
  • простой математический синтаксический анализатор выражений,
  • тральщик

Примечание: Опять же, некоторые из них на самом деле не сложнее ... Они просто подходят к проблеме под точно таким же или немного другим углом. Но практика делает идеальным.

Помощники

Ссылка

Некоторое чтение никогда не повредит. Ну, это поначалу, и они будут чувствовать себя еще более потерянными. Это такая вещь, которая растет на тебе и сидит у тебя в голове, пока однажды ты не осознаешь, что наконец-то это понял. А потом вы вспоминаете эти вещи, которые вы прочитали. Рекурсии , рекурсии в области компьютерных наук и рекуррентное соотношение страниц в Википедии будет делать сейчас.

Уровень / Глубина

Предполагая, что ваши студенты не имеют большого опыта программирования, предоставьте заглушки кода. После первых попыток дайте им функцию печати, которая может отображать уровень рекурсии. Печать числового значения уровня помогает.

Диаграмма "Стек как ящики"

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

Рекурсивные Сокращения

Если ваш студент уже немного разбирается в компьютерной культуре, он может уже использовать некоторые проекты / программы с именами, использующими рекурсивные аббревиатуры . Это стало традицией в течение некоторого времени, особенно в проектах GNU. Вот некоторые примеры:

Рекурсивный:

• GNU - "GNU - это не Unix"
• Nagios - "Nagios не собирается настаивать на святости"
• PHP - «PHP Hypertext Preprocessor» (и оригинальная «Персональная домашняя страница»)
• Wine - "Вино не эмулятор"
• Zile - "Zile Is Lossy Emacs"

Взаимно рекурсивный:

• HURD - «HIRD демонов, заменяющих Unix» (где HIRD - «HURD интерфейсов, представляющих глубину»)

Пусть они попробуют придумать свое.

Точно так же, есть много случаев рекурсивного юмора, например , рекурсивная коррекция поиска Google . Для получения дополнительной информации о рекурсии, прочитайте этот ответ .

Подводные камни и дальнейшее обучение

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

Почему, о Боже, почему ???

Почему ты бы так поступил? Хорошая, но неочевидная причина заключается в том, что часто проще так выразить проблему. Не очень хорошая, но очевидная причина в том, что часто требуется меньше печатать (хотя не заставляйте их чувствовать себя слишком просто за использование рекурсии ...).

Некоторые проблемы определенно легче решить, используя рекурсивный подход. Как правило, любая проблема, которую вы можете решить с помощью парадигмы « Разделяй и властвуй», будет соответствовать разветвленному алгоритму рекурсии.

Что снова N?

Почему мой nили (независимо от имени вашей переменной) каждый раз разные? У новичков обычно возникают проблемы с пониманием, что такое переменная и параметр, и как вещи, названные nв вашей программе, могут иметь разные значения. Так что теперь, если это значение находится в цикле управления или рекурсии, это еще хуже! Будьте добры и не используйте одинаковые имена переменных везде, и дайте понять, что параметры - это просто переменные .

Конечные условия

Как мне определить мое конечное состояние? Это легко, просто попросите их произнести шаги вслух. Например, для факториала начните с 5, затем 4, затем ... до 0.

Дьявол кроется в деталях

Не говорите о таких ранних вещах, как оптимизация хвостовых вызовов . Я знаю, я знаю, ТШО хорош, но поначалу им все равно. Дайте им некоторое время, чтобы обернуть голову вокруг процесса так, чтобы он работал для них. Не стесняйтесь разрушить их мир позже, но дайте им отдохнуть.

Точно так же не говорите прямо из первой лекции о стеке вызовов и его потреблении памяти и ... ну ... переполнении стека . Я часто в частном порядке репетирую студентов, которые показывают мне лекции, где у них есть 50 слайдов обо всем, что можно знать о рекурсии, когда они едва могут правильно написать цикл на данном этапе. Это хороший пример того, как справка поможет позже, но сейчас просто глубоко смущает вас.

Но, пожалуйста, своевременно проясните, что есть причины идти итеративным или рекурсивным путем .

Взаимная рекурсия

Мы видели, что функции могут быть рекурсивными, и даже то, что они могут иметь несколько точек вызова (8 ферзей, Ханой, Фибоначчи или даже алгоритм разведки для тральщика). Но как насчет взаимно рекурсивных вызовов ? Начните с математики здесь. f(x) = g(x) + h(x)где g(x) = f(x) + l(x)и hи lпросто делать вещи.

Начиная только с математических рядов, легче писать и реализовывать, так как контракт четко определен выражениями. Например, женские и мужские последовательности Хофштадтера :

Однако с точки зрения кода следует отметить, что реализация взаимно рекурсивного решения часто приводит к дублированию кода и должна быть скорее сведена в единую рекурсивную форму (см. « Решение загадки каждого судоку» Питера Норвига ) .

Вызов функции из той же функции.

Рекурсия - это функция, которая вызывает сама себя.

Как это использовать, когда его использовать и как избежать плохого дизайна, важно знать, что требует от вас попробовать это сами и понять, что происходит.

Самое важное, что вам нужно знать, - это быть очень осторожным, чтобы не получить цикл, который никогда не заканчивается. Ответ pramodc84 на ваш вопрос имеет следующую ошибку: он никогда не заканчивается ...
Рекурсивная функция всегда должна проверять условие, чтобы определить, следует ли ей снова вызывать себя или нет.

Самый классический пример использования рекурсии - это работа с деревом без статических ограничений по глубине. Это задача, которую вы должны использовать рекурсии.

Рекурсивное программирование - это процесс постепенного сокращения проблемы до более простого решения ее версий.

Каждая рекурсивная функция стремится:

1. взять список для обработки, или какую-то другую структуру, или проблемную область
2. разобраться с текущей точкой / шагом
3. вызвать себя на остаток (ы) / поддомен (ы)
4. объединить или использовать результаты работы поддоменов

Когда шаг 2 предшествует 3, и когда шаг 4 тривиален (конкатенация, сумма или ничего), это включает хвостовую рекурсию . Шаг 2 часто должен идти после шага 3, так как для выполнения текущего шага могут потребоваться результаты из субдомена (-ов) проблемы.

Возьмите обход прямого двоичного дерева. Обход может быть выполнен в предзаказе, в порядке или после заказа, в зависимости от того, что требуется.

   B
A     C

Предварительный заказ: BAC

traverse(tree):
    visit the node
    traverse(left)
    traverse(right)

В заказе: ABC

traverse(tree):
    traverse(left)
    visit the node
    traverse(right)

После заказа: ACB

traverse(tree):
    traverse(left)
    traverse(right)
    visit the node

Очень много рекурсивных проблем являются конкретными случаями операции карты или сгибом - понимание только этих двух операций может привести к значительному пониманию хороших сценариев использования для рекурсии.

ОП сказал, что рекурсия не существует в реальном мире, но я позволю себе не согласиться.

Давайте возьмем реальную «операцию» по нарезке пиццы. Вы вытащили пиццу из духовки и, чтобы подать ее, нужно разрезать ее пополам, затем разрезать эти половинки пополам, а затем снова разрезать получившиеся половинки пополам.

Операцию нарезки пиццы вы выполняете снова и снова, пока не получите желаемый результат (количество ломтиков). И в качестве аргумента скажем, что неразрезанная пицца сама по себе является ломтиком.

Вот пример в Ruby:

def cut_pizza (существующие_срезы, нужные_срезы)
  если существующие_срезы! = требуемые_срезы
    # у нас пока недостаточно кусочков, чтобы накормить всех, поэтому
    # режем кусочки пиццы, удваивая их количество
    new_slices = существующие_слайсы * 2 
    # а это вот рекурсивный вызов
    cut_pizza (новые_срезы, нужные_срезы)
  еще
    # у нас есть желаемое количество ломтиков, поэтому мы возвращаем
    # здесь вместо продолжения рекурсии
    вернуть существующие_срезы
  конец
конец

пицца = 1 # целая пицца, один ломтик
cut_pizza (pizza, 8) # => мы получим 8

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

Вы обнаружите, что операции, которые вы можете реализовать с помощью рекурсивных функций:

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

Я рекомендую написать программу для поиска файла на основе его имени и попробуйте написать функцию, которая вызывает себя до тех пор, пока не будет найдена, подпись будет выглядеть так:

find_file_by_name(file_name_we_are_looking_for, path_to_look_in)

Так что вы можете назвать это так:

find_file_by_name('httpd.conf', '/etc') # damn it i can never find apache's conf

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

Дополнительные кредиты В cut_pizzaприведенном выше примере вы получите слишком большую ошибку на уровне стека, если вы попросите указать количество срезов, которое не является степенью 2 (т. Е. 2, 4, 8 или 16). Можете ли вы изменить его так, чтобы, если кто-то попросил 10 срезов, он не запустился навсегда?

Хорошо, я постараюсь сохранить это простым и лаконичным.

Рекурсивные функции - это функции, которые вызывают сами себя. Рекурсивная функция состоит из трех вещей:

1. логика
2. Зов к себе
3. Когда прекратить.

Лучший способ написания рекурсивных методов - это думать о методе, который вы пытаетесь написать, как простой пример, обрабатывающий только один цикл процесса, который вы хотите перебрать, затем добавьте вызов к самому методу и добавьте, когда вы хотите прекратить. Лучший способ учиться - это практиковать как все.

Так как это сайт программистов, я воздержусь от написания кода, но вот хорошая ссылка

если ты получил эту шутку, ты понял, что значит рекурсия.

Рекурсия - это инструмент, который программист может использовать для вызова самого вызова функции. Последовательность Фибоначчи - это учебный пример того, как используется рекурсия.

Большая часть рекурсивного кода, если не все, может быть выражена как итеративная функция, но обычно она грязная Хорошими примерами других рекурсивных программ являются структуры данных, такие как деревья, двоичное дерево поиска и даже быстрая сортировка.

Рекурсия используется, чтобы сделать код менее небрежным, имейте в виду, что он обычно медленнее и требует больше памяти.

Мне нравится использовать это:

Как вы ходите в магазин?

Если вы на входе в магазин, просто пройдите его. В противном случае сделайте один шаг, а затем пройдите до магазина.

Важно включить три аспекта:

• Тривиальный базовый случай
• Решение небольшой части проблемы
• Решение остальной части проблемы рекурсивно

На самом деле мы часто используем рекурсию в повседневной жизни; мы просто не думаем об этом таким образом.

Лучший пример, на который я бы вам указал, это язык программирования C от K & R. В этой книге (и я цитирую из памяти) запись на странице указателя для рекурсии (одна) показывает фактическую страницу, на которой они говорят о рекурсии и страница индекса также.

Джош К уже упоминал о матрешках кукол. Предположим, вы хотите научиться чему-то, что знает только самая короткая кукла. Проблема в том, что вы не можете по-настоящему поговорить с ней напрямую, потому что она изначально живет внутри более высокой куклы, которая на первой картинке расположена слева от нее. Эта структура выглядит следующим образом (кукла живет внутри более высокой куклы), пока не окажется только самой высокой.

Поэтому единственное, что вы можете сделать, это задать свой вопрос самой высокой кукле. Самая высокая кукла (которая не знает ответа) должна будет передать ваш вопрос более короткой кукле (которая на первой картинке справа от нее). Поскольку у нее также нет ответа, ей нужно спросить следующую более короткую куклу. Это будет продолжаться до тех пор, пока сообщение не достигнет самой короткой куклы. Самая короткая кукла (единственная, кто знает секретный ответ) передаст ответ следующей более высокой кукле (найденной слева), которая передаст ее следующей более высокой кукле ... и это будет продолжаться до тех пор, пока не будет получен ответ. достигает своего конечного пункта назначения, которая является самой высокой куклой и, наконец, вы :)

Это то, что действительно делает рекурсия. Функция / метод вызывает себя до получения ожидаемого ответа. Вот почему, когда вы пишете рекурсивный код, очень важно решить, когда рекурсия должна завершиться.

Не лучшее объяснение, но оно, надеюсь, поможет.

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

Классический пример - нахождение факториала числа n !. 0! = 1, а для любого другого натурального числа N факториал N является произведением всех натуральных чисел, меньших или равных N. Итак, 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720. Это базовое определение позволит вам создать простое итеративное решение:

int Fact(int degree)
{
    int result = 1;
    for(int i=degree; i>1; i--)
       result *= i;

    return result;
}

Тем не менее, проверьте операцию еще раз. 6! = 6 * 5 * 4 * 3 * 2 * 1. По тому же определению 5! = 5 * 4 * 3 * 2 * 1, что означает, что мы можем сказать 6! = 6 * (5!). В свою очередь 5! = 5 * (4!) И так далее. Делая это, мы уменьшаем проблему до операции, выполняемой в результате всех предыдущих операций. Это в конечном итоге сводится к точке, называемой базовым случаем, где результат известен по определению. В нашем случае 0! = 1 (в большинстве случаев мы также можем сказать, что 1! = 1). В вычислениях нам часто разрешают определять алгоритмы очень похожим образом, вызывая сам метод и передавая меньшие входные данные, тем самым уменьшая проблему посредством множества рекурсий в базовом случае:

int Fact(int degree)
{
    if(degree==0) return 1; //the base case; 0! = 1 by definition
    else return degree * Fact(degree -1); //the recursive case; N! = N*(N-1)!
}

Во многих языках это может быть дополнительно упрощено с помощью троичного оператора (иногда это рассматривается как функция Iif в языках, которые не предоставляют оператор как таковой):

int Fact(int degree)
{
    //reads equivalently to the above, but is concise and often optimizable
    return degree==0 ? 1: degree * Fact(degree -1);
}

Преимущества:

• Естественное выражение - для многих типов алгоритмов это очень естественный способ выражения функции.
• Сокращенный LOC - часто гораздо более кратко определить функцию рекурсивно.
• Скорость. В некоторых случаях, в зависимости от языка и архитектуры компьютера, рекурсия алгоритма выполняется быстрее, чем эквивалентное итеративное решение, обычно потому, что выполнение вызова функции является более быстрой операцией на аппаратном уровне, чем операции и доступ к памяти, необходимые для итеративного цикла.
• Делимость - Многие рекурсивные алгоритмы имеют менталитет «разделяй и властвуй»; результат операции является функцией результата той же операции, выполненной на каждой из двух половин ввода. Это позволяет вам разделить работу на две части на каждом уровне, и, если доступно, вы можете передать другую половину другому «исполнительному блоку» для обработки. Это обычно сложнее или невозможно с итеративным алгоритмом.

Недостатки:

• Требует понимания - вы просто должны «понять» концепцию рекурсии, чтобы понять, что происходит, и, следовательно, написать и поддерживать эффективные рекурсивные алгоритмы. В противном случае это просто выглядит как черная магия.
• Зависит от контекста - является ли рекурсия хорошей идеей или нет, зависит от того, насколько элегантно алгоритм может быть определен в терминах самого себя. Хотя возможно построить, например, рекурсивную SelectionSort, итерационный алгоритм обычно более понятен.
• Обменивает доступ к ОЗУ для стека вызовов. Как правило, вызовы функций дешевле, чем доступ к кэшу, что может сделать рекурсию быстрее, чем итерация. Но обычно есть предел глубины стека вызовов, который может вызвать рекурсию к ошибке, где будет работать итеративный алгоритм.
• Бесконечная рекурсия - Вы должны знать, когда остановиться. Бесконечная итерация также возможна, но используемые циклические конструкции обычно проще для понимания и, следовательно, для отладки.

Пример, который я использую, является проблемой, с которой я столкнулся в реальной жизни. У вас есть контейнер (например, большой рюкзак, который вы собираетесь взять в поездку), и вы хотите узнать общий вес. У вас в контейнере два или три незакрепленных предмета, и некоторые другие контейнеры (скажем, мешки с вещами). Вес всего контейнера, очевидно, равен весу пустого контейнера плюс вес всего в нем. Для незакрепленных предметов вы можете просто взвесить их, а для мешков с вещами вы можете просто взвесить их или сказать: «Ну, вес каждого мешка - это вес пустого контейнера плюс вес всего, что в нем». И затем вы продолжаете погружаться в контейнеры в контейнеры и так далее, пока не дойдете до точки, где в контейнере просто находятся незакрепленные предметы. Это рекурсия.

Вы можете подумать, что этого никогда не случится в реальной жизни, но представьте себе, что вы пытаетесь подсчитать или сложить зарплату людям в конкретной компании или подразделении, в котором есть люди, которые просто работают в компании, люди в подразделениях, а затем в в отделах есть отделы и тд. Или продажи в стране, в которой есть регионы, в некоторых из которых есть субрегионы и т. Д. Подобные проблемы постоянно возникают в бизнесе.

Рекурсия может быть использована для решения множества задач по подсчету. Например, скажем, у вас есть группа из n человек на вечеринке (n> 1), и все пожимают руку друг другу ровно один раз. Сколько рукопожатий происходит? Вы можете знать, что решение C (n, 2) = n (n-1) / 2, но вы можете решить рекурсивно следующим образом:

Предположим, есть только два человека. Тогда (осмотром) ответ, очевидно, равен 1.

Предположим, у вас есть три человека. Выделите одного человека и обратите внимание, что он / она пожимает руку двум другим людям. После этого вы должны считать только рукопожатия между двумя другими людьми. Мы уже сделали это только сейчас, и это 1. Таким образом, ответ 2 + 1 = 3.

Предположим, у вас есть n человек. Следуя той же логике, что и раньше, это (n-1) + (количество рукопожатий между n-1 человек). Расширяясь, мы получаем (n-1) + (n-2) + ... + 1.

Выражается как рекурсивная функция,

f (2) = 1
f (n) = n-1 + f (n-1), n> 2

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

Хотя рекурсия действительно происходит здесь, в мире. Много.

Хороший пример (упрощенная версия) круговорота воды:

• Солнце нагревает озеро
• Вода поднимается в небо и образует облака
• Облака спускаются к горе
• В горах воздух становится слишком холодным для удержания влаги.
• Идет дождь
• Река образует
• Вода в реке впадает в озеро

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

Еще одно место, где вы можете получить рекурсию - на английском (и на человеческом языке в целом). Сначала вы можете его не распознать, но способ, которым мы можем сгенерировать предложение, является рекурсивным, потому что правила позволяют нам встроить один экземпляр символа в сторону другого экземпляра того же символа.

От Стивена Пинкера «Языковой инстинкт»:

если девушка ест мороженое или девушка ест конфеты, то мальчик ест хот-доги

Это целое предложение, которое содержит другие целые предложения:

девушка ест мороженое

девушка ест конфеты

мальчик ест хот-доги

Понимание полного предложения включает в себя понимание более мелких предложений, которые используют тот же набор умственного обмана, который следует понимать как полное предложение.

Чтобы понять рекурсию с точки зрения программирования, проще всего взглянуть на проблему, которую можно решить с помощью рекурсии, и понять, почему она должна быть и что это означает, что вам нужно сделать.

В качестве примера я буду использовать функцию наибольших общих делителей или gcd для краткости.

У вас есть два номера aи b. Чтобы найти их gcd (при условии, что ни один из них не равен 0), вам нужно проверить, aделится ли на равномерно b. Если это тогда bgcd, в противном случае вам нужно проверить gcd bи остаток от a/b.

Вы уже должны видеть, что это рекурсивная функция, так как у вас есть функция gcd, вызывающая функцию gcd. Просто чтобы забить его домой, здесь он находится в c # (опять же, предполагая, что 0 никогда не передается в качестве параметра):

int gcd(int a, int b)
{   
    if (a % b == 0) //this is a stopping condition
    {
        return b;
    }

    return (gcd(b, a % b)); //the call to gcd here makes this function recursive
}

В программе важно иметь условие остановки, иначе ваша функция будет повторяться вечно, что в конечном итоге приведет к переполнению стека!

Причина использования рекурсии здесь, а не цикла while или какой-либо другой итеративной конструкции, заключается в том, что когда вы читаете код, он говорит вам, что он делает и что будет дальше, поэтому легче понять, работает ли он правильно. ,

Вот реальный пример рекурсии.

Пусть они представят, что у них есть коллекция комиксов, и вы собираетесь смешать все это в большую кучу. Осторожно - если у них действительно есть коллекция, они могут мгновенно убить вас, когда вы просто упомяните идею сделать это.

Теперь позвольте им отсортировать эту большую несортированную кучу комиксов с помощью этого руководства:

Manual: How to sort a pile of comics

Check the pile if it is already sorted. If it is, then done.

As long as there are comics in the pile, put each one on another pile, 
ordered from left to right in ascending order:

    If your current pile contains different comics, pile them by comic.
    If not and your current pile contains different years, pile them by year.
    If not and your current pile contains different tenth digits, pile them 
    by this digit: Issue 1 to 9, 10 to 19, and so on.
    If not then "pile" them by issue number.

Refer to the "Manual: How to sort a pile of comics" to separately sort each
of the new piles.

Collect the piles back to a big pile from left to right.

Done.

Хорошая вещь здесь: когда они дошли до отдельных проблем, у них есть полный «кадр стека» с локальными кучами, видимыми перед ними на земле. Дайте им несколько распечаток руководства и отложите по одному на каждом уровне стопки с отметкой, где вы находитесь на этом уровне (т. Е. Состояние локальных переменных), чтобы вы могли продолжить там на каждом Готово.

Вот в чем суть рекурсии: выполнение одного и того же процесса, просто на более высоком уровне детализации, чем больше вы углубляетесь в него.

• Завершить, если достигнуто условие выхода
• сделать что-нибудь, чтобы изменить положение вещей
• делать всю работу, начиная с нынешнего положения вещей

Рекурсия - это очень краткий способ выразить то, что должно повторяться до тех пор, пока что-то не будет достигнуто.

Не простой английский, не реальные примеры из жизни, но два способа изучения рекурсии, играя:

• Ханойская башня
• меледа

Хорошим объяснением рекурсии является буквально «действие, которое повторяется изнутри себя».

Представьте себе, что художник рисует стену, это рекурсивно, потому что действие "нарисовать полосу от потолка до пола, а затем подскочить немного вправо и (закрасить полосу от потолка до пола, затем немного переместиться вправо и (нарисовать раздеться от потолка до пола, затем немного подняться вправо и (и т. д.))).

Его функция paint () вызывает себя снова и снова, чтобы создать его большую функцию paint_wall ().

Надеюсь, у этого бедного художника какое-то состояние остановки :)