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

Что такое рекурсия?

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

//Returns the sum of all numbers from 0 to a given integer
function sumRange(num){
    if (num === 0){
        return 0
    }
    
    return num + sumRange(num -1)
}

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

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

//Returns the sum of all numbers from 0 to a given integer
function sumRange(num){
    if (num === 0){
        return 0
    }
    
    return num + sumRange(num -1)
}

Я объясню образ мышления рекурсивно. Вернемся к коду.

Вы можете разделить код на 2 части:

if (num === 0){
    return 0
}

1- Базовый случай.

На этом ваш узор заканчивается. В этом случае мы сложили все числа от 0 до целого числа. Не имеет значения, является ли целое число 1, 10 или 100, мы всегда будем добавлять каждое число, останавливаясь, когда дойдем до 0.

return num + sumRange(num -1)

2- Основной узор

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

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

Первоначально опубликовано на https://kyoung90.github.io 5 сентября 2019 г.