Прыжок веры: «акт веры или попытки чего-то, существование или результат которого не могут быть доказаны или известны». -Google
Когда я впервые столкнулся с идеей рекурсии, меня озадачило то, как функция может использовать себя для решения самой себя. Когда я пытаюсь решить сложную проблему с помощью рекурсии, мне до сих пор порой не удается решить эту проблему. Честно говоря, это не только меня. МНОГО людей борются с рекурсией и часто теряют мотивацию. И это потому, что иногда рекурсивная функция не имеет никакого смысла, или кажется, что она не имеет никакого смысла, или просто иногда ее сложно реализовать.
Даже если вы новичок, как вы поймете функцию, для которой вы должны сначала понять ту же функцию. Чтобы прояснить эту путаницу, я процитирую то, что однажды сказал мне мой наставник:
«Чтобы решить проблему с помощью рекурсии, вы должны верить в рекурсию. Вы должны сделать этот прыжок веры. И одна вещь, о которой вы всегда должны помнить, - это то, что для построения веры нужно время. Потратьте на это немного времени, ваша вера поможет вам пройти через это ».
Как бы банально эта цитата ни звучала, но это правда. И я вам это докажу на нескольких примерах. Прежде чем мы перейдем к некоторым примерам, есть несколько основных правил, которые следует иметь в виду, прежде чем определять рекурсивную функцию.
Правило # 1
Определите базовый вариант: когда функция обнаруживает базовый вариант, она выходит из рекурсивного цикла и немедленно предоставляет результат. Кроме того, его можно определить как наименьший возможный ввод для данной функции.
Правило # 2
Определите рекурсивный случай: в этом случае функция продолжает вызывать себя снова и снова, пока не достигнет базового условия. С каждым шагом задача становится меньше и проще.
Поиск пути с помощью рекурсии
Сначала прочтите формулировку проблемы здесь.
Предположим, что матрица равна nxm.
Прежде чем мы перейдем к коду, давайте разберемся с проблемой здесь.
Предположим, что есть только одна строка и n столбцов, чем сколько путей будет до n-го столбца? Очевидно, всего 1.
Точно так же, если есть m строк и только один столбец, будет только 1 путь.
Если это ясно, то мы можем сказать, что если я каким-то образом дойду до последнего столбца или последней строки, это будет считаться путем.
А вот и сложная часть. Я написал код, помня об этих двух вещах, и решил уверенно подсчитать все пути для заданного количества строк и столбцов, не задумываясь. о том, как это будет работать после каждой итерации.
int пути (int n, int m) // определение функции
{
if (n == 1 || m == 1) // базовое условие
возврат 1;
return пути (n, m-1) + пути (m, n-1); // рекурсивный вызов
}
Все, о чем я заботился, - это добраться до n-го столбца для данной строки и m-го ряда для данного столбца, а затем добавить результат. И после каждой рекурсии значение уменьшается на единицу, пока не достигнет базового случая.
Вы можете просмотреть весь код, нажав здесь.
Теперь вы можете не до конца разобраться в проблеме. Но я предлагаю вам снова и снова (рекурсивно) пытаться понять эту логику, пока вы не будете удовлетворены подходом. Потратьте некоторое время на эту проблему, и вы наверняка укрепите веру в рекурсию.
Честно говоря, рекурсия - это довольно простая тема, когда мы изучаем ее теоретически и используем ее только для решения старинного примера поиска факториала. Но по мере того, как мы переходим к немного сложным задачам, ее выполнение становится чрезвычайно трудным. Однако практика может немного облегчить вам задачу.
